정렬 된 정수 배열 키를 사용하여 정수 인덱스 값을 빠르게 조회

Question

정렬 된 정수 배열 키를 사용하여 정수 값을 찾는 가장 빠른 솔루션을 찾고 있습니다.

키는 정수 배열이며 고정 길이가 3이며 각 배열이 정렬됩니다.
값은 정수입니다.

내 데이터는 동일한 내용을 가진 하나 또는 두 개의 정렬 된 배열 만 존재한다는 것을 보증합니다. 각 배열에는 고유 색인이 있습니다.

일치하는 배열 쌍을 찾으려고합니다.

나의 생각은 내가 사전에보고 이미이 있는지 보자, 각 배열의 경우 사전 (나는 C#에서 프로토 타이핑하고있어 C로 이동합니다 ++)

을 사용하는 것입니다. 그렇다면 사전에서 제거합니다. 사전에서 찾지 못하면 싱글 톤이거나 일치하는 쌍 중 첫 번째이므로 사전에 추가합니다.

내 질문은 - 데이터에 대한 확실한 보증을 제공하고, 최고의 컨테이너는 무엇입니까? 또한 정렬 된 정수 배열에 대한 적절한 (빠른) 해싱 함수 또는 비교 함수에 대한 권장 사항을 이해할 수 있습니다. 당신이 C++에 도착하면

Answer 1

이

http://sparsehash.googlecode.com/svn/trunk/doc/dense_hash_map.html로 마이그레이션 (프로젝트 here.)

그것은 내가로 실행 한 가장 빠른 해시 맵 구현 중 하나입니다.

한편, C#의 경우 이와 동일한 내용이 표시됩니다. http://msdn.microsoft.com/en-us/library/xfhwa508.aspx 더 빠른 사전 구현이 가능하지만 C#은 최종 컨테이너가 아니므로 잘 수행해야합니다.

프로젝트에 berkeleydb를 포함하는 것에 대해 생각해보십시오. 매우 빠르며 데이터 세트가 커지면 스토리지를 관리합니다. 또한 다양한 플랫폼에서 지원됩니다.