전역 배열의 인덱스에 max에서 1에서 4까지의 길이를 갖는 정렬 된 정수 배열을 매핑해야합니다. 마찬가지로 [13,24,32]는 0..n 범위의 숫자가되고, 같은 번호로 매핑되는 다른 배열은 없습니다. 배열의 수는 수백만 개이며 매핑은 항목 집합을 나타내며 k-1 개의 작은 항목 집합을 사용하여 하나의 항목 집합을 사용하기 때문에 매핑이 "고유"(또는 더 작은 배열의 경우 최소한 충돌이 거의 발생)해야합니다. 크기 k의int의 고유 배열을 범위 인덱스 0..n에 매핑하는 해시 함수.
현재 구현은 효율적인 해시 함수를 사용하여 배열에 대해 0..1 사이의 double을 생성하고 STL Map에 항목 집합을 키로 저장합니다. 그래서, 내가 CUDA이의 병렬 버전을 구현하는거야
ND Atreas, C. Karanikas "소수와 해시 근사 기반으로 빠른 패턴 매칭 알고리즘", 2007
:이 문서에서있어 나는 STL Map과 같은 것을 사용할 수 없다. 나는 스스로를 GPU 전역 메모리의 맵으로 쉽게 밸런싱 바이너리 검색 트리를 만들 수는 있지만 실제로는 느릴 것이다. 따라서 전역 메모리 액세스를 최소한으로 줄이기 위해서는 항목 세트를 전역 메모리의 거대한 배열에 매핑해야합니다.
double을 long 형으로 캐스팅하고 64 비트 해시 함수로 해시하려했지만 예상대로 충돌이 발생합니다. 0..1 사이 두 배에 대해 "독특한"해시 함수가 있다면
그래서, 질문, 또는 크기 1..4의 정수의 배열, 그 크기 N.의 테이블에 대한 고유 인덱스를 제공
나는이 당신의 배열에 대한 가정 한 경우
[최소 완벽한 해시 기능] (http://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function)을 찾고 있습니다. –
그러나 최소 해시 함수를 작성하기 위해 입력을 제공 할 필요가 없습니까? 내 배열은 다양 할 수 있으며 크기가 다를 수있는 단일 항목의 배열에서 크기가 1에서 4까지입니다. – liwing
나는 그들보다 이름에 대해 많이 모른다. 나는 두렵다. 내가 틀릴 수는 있어도 수백만 개의 요소에 대해 이러한 기능을 구축하는 것은 매우 시간 소모적 일 것입니다 (아마도 불가능할 수도 있습니다). –