'key mod table_size'와 같은 해시 함수를 사용하는 동안 발생하는 충돌을 상당히 줄일 수있는 프로그램을 작성하고 있습니다. 이를 위해 유전 프로그래밍/알고리즘을 사용하고 싶습니다. 그러나 나는 그것에 대해 많이 모른다. 많은 기사와 예제를 읽은 후에도 필자는 (프로그램 정의에서와 같이) 피트니스 기능, 대상 (일반적으로 목표는 필수 결과 임), 인구/개인 및 부모로 나타나는 것,유전 프로그래밍/알고리즘을 사용하여 해싱 개선
가능한 경우 위 코드와 의사 코드 스 니펫을 식별하는 데 도움이되도록 제 프로젝트를 진행하십시오.
유전 프로그래밍/알고리즘을 사용할 필요는 없지만 진화 프로그래밍/알고리즘을 사용하는 모든 것일 수 있습니다.
감사합니다.
제 조언은 다음과 같습니다. 이렇게하지 마세요. 해시 함수에 대한 문헌은 방대하며, 좋은 해시 함수를 만드는 이유를 더 많이 또는 덜 이해합니다. 우리는 그들을 맹목적으로 찾지 않기에 충분한 수학을 알고 있습니다. 사용할 해시 함수가 필요한 경우 선택할 수있는 항목이 충분합니다.
그러나이 프로젝트가 유니 프로젝트이고 주제를 변경하거나 조정할 수없는 방향으로 조정할 수 없다면주의해야 할 것은 피트니스 기능 및 돌연변이 연산자를 올바르게 가져 오는 복잡한 문제가있을 것입니다. 내 머리 꼭대기에서 말할 수있는 한 확실한 후보자는 없습니다.
'엄격한 애벌란치 기준'을 준수하고 체력과 돌연변이의 관점에서 당신이 그것에 대해 판단 할 수 있는지 알아 봅니다.
또 다른 질문은 어떻게 기능을 표현 하시겠습니까? 부울 표현식인가요? AND, XOR, NOT, ROT와 같은 단어 연산으로 만들어진 것입니까? 제약 조건 (또는 가정)에 따라 적합성 및 돌연변이 문제가 달라집니다.
일반적으로 피트니스는 '해시 모듈러스 테이블 크기'모델에서 충돌 횟수를 최소화합니다. 명백한 부분은 적절하게 크고 중요한 (매우 중요한) 키 분배를 가져 와서 '후보'기능을 통해 척하는 것입니다.
그런 다음 하나 이상의 테이블 크기 값에 대해 'hash modulo table-size'를 통해 전달하고 발생 분포의 'niceness'에 대한 측정을 평가할 수 있습니다.
그래서 무엇을 시도 할 테이블 크기와 적용 할 niceness 측정 값입니다. Niceness는 상황에 따라 다릅니다. '최악의 경우'삽입/찾기 시간의 척도로 'full bucket'을 측정 할 수 있습니다. 키 찾아보기 사이에 균일 한 분포를 기반으로 '평균'삽입/찾기 시간의 척도로 버킷 크기의 제곱합을 측정 할 수 있습니다.
마지막으로 테스트 할 테이블 크기 (또는 크기)를 결정해야합니다. 해시 모듈로 프라임은 해시의 모든 비트에 적절하게 변동하는 경향이 있으므로 해시 모듈로 2^n과 같은 것은 하위 n-1 비트 만 포함하므로 일반적으로 소수를 사용합니다. 계산량을 줄이려면 다음 소수의 시리즈를 각 2의 거듭 제곱보다 더 크게 고려할 수 있습니다. 17 (> 2^2) 11 (> 2^3), 17 (> 2^4) 등이 '샘플'크기보다 큰 2의 제곱을 포함합니다.
피트니스를 고려하는 다른 방법이 있지만 실용적인 응용 프로그램없이 질문은 (물론) 잘못 정의되어 있습니다.
잠재적 인 해시 함수의 '공간'이 모두 동일한 실행 시간을 갖는 것이 아니라면 '비용'도 고려해야합니다. 아주 좋은 해시 함수를 정의하는 것은 상당히 쉽지만 실행 시간은 중요한 요소가 될 수 있습니다.