메모리 풋 프린트를 최소화하는 "드문 드문 한"룩업 어레이 만들기

Question

이더넷 프로토콜과 같은 네트워크 프로토콜을 구문 분석하기 위해 룩업을 수행 할 배열을 만들고 싶다고 가정 해 봅시다. 이러한 식별자는 2 바이트 길이이기 때문에 직접 인덱싱을 사용하면 2^16 셀 배열로 끝납니다. 배열이 희박하다는 가능성이 매우 높으므로 이것은 실제 낭비입니다. 즉 정렬.

메모리 사용량을 최대로 줄이기 위해 CMPH과 같은 완벽한 해싱 함수 생성기를 사용하여 임의의 충돌없이 n 크기의 식별자를 "n"식별자에 매핑 할 수 있습니다. 이 접근법의 단점은 외부 "외래 (exoteric)"라이브러리에 의존해야한다는 것입니다.

제 경우에는 베이 메모리 사용을 유지하면서 일정한 시간 조회를하는 더 똑똑한 방법이 있는지 궁금합니다. 16 비트 부호없는 numbers의 색인 생성에 관심이 있으며 설정 크기가 상당히 제한되어 있음을 명심하십시오.

감사

Answer 1

당신이 16 비트 값을 처리하고 있다는 사실만을 O (1) 다른 가능한 값이 있기 때문에, 어떤 검색 알고리즘은, 일정한 시간 알고리즘이 될 것입니다 알고 있기 때문에 . 결과적으로, 표면에서 더 느릴 수있는 알고리즘 (예 : n 요소에 대해 O (n)에서 실행되는 선형 검색)이 여기에서 실제로 유용 할 수 있습니다.

빠른 검색을 보장하려면 cuckoo hashing을 살펴볼 것을 권장합니다. 최악의 경우 O (1) 조회 시간을 보장하고 O (1) 시간 삽입을 예상합니다. 해시 함수로 약간 영리한). 16 비트 값에 대한 해시 함수를 생성하는 것은 정말 쉽습니다. 두 개의 16 비트 승수를 계산하고 16 비트 값의 상위 및 하위 비트에이 값을 곱한 다음 이들을 더 합치면 좋은 해시 함수 모 드를 소수로 얻을 수 있다고 생각합니다. 당신이 절대적으로 O (1) 조회가 있어야 좋은 예상 조회 시간이 괜찮하지 않는 경우

또는, 당신은 또한 개방은 linear probing hash table 또는 double hashing hash table A와, 주소와 표준 해시 테이블을 사용할 수 있습니다. 이런 종류의 해시 구성표와 함께 더 작은 배열을 사용하는 것은 매우 빠르며 구현이 매우 간단해야합니다.

완전히 다른 접근 방식으로, 스파 스 데이터를 저장하고 빠른 검색 시간을 원할 경우 간단한 균형 이진 검색 트리를 사용하는 것이 좋습니다. 예를 들어 treap 데이터 구조는 구현하기 쉽고 값에 대해 예상되는 O (log n) 룩업을 제공합니다. 16 비트 값을 다루고 있기 때문에 여기 log n은 약 16입니다. 로그의 기저가 실제로는 조금 다르다고 생각합니다. 따라서 조회가 아주 빨라야합니다. 이것은 요소 당 약간의 오버 헤드를 가져 오지만, 요소가 적다면 구현이 간단해야합니다. 오버 헤드를 줄이려면 요소 당 포인터가 두 개만 필요한 splay trees을 조사하는 것이 좋습니다.

희망이 도움이됩니다.