메모리 효율적인 맵 <pair <int,int>, 세트 <int>> 대체

Question

저는 각각 하나가 문서 ID와 관련되어있는 엄청난 양의 정수 쌍을 가지고 있습니다. 내 목표는 이제 같은 쌍을 가진 문서를 검색하는 것입니다.

Document1 

- pair1: (3, 9) 
- pair2: (5,13) 

Document2 

- pair1: (4234, 13) 
- pair2: (5,13) 

map<pair<int,int>, unordered_set<int>> hashMap 
hashMap[{3, 9}].insert(1) 
hashMap[{5, 13}].insert(1) 

hashMap[{4234, 13}].insert(2) 
hashMap[{5, 13}].insert(2) 

하는 것이 될 것입니다 :

내 첫번째 생각은 예를 들어, 즉 map<pair<int,int>, unordered_set<int>>

, 관련된 값으로 키와 쌍 값과 문서 ID를 사용하여 해시 맵 (std::map)를 사용하는 것이 었습니다 에

Key(3,9) = Documents(1) 
Key(5,13) = Documents(1,2) 
Key(4234,13) = Documents(2) 

내 문제는 이제 내 사용 가능한 24GB RAM을 초과하는 엄청난 양의 메모리가 필요하다는 것입니다. 따라서 삽입물과 조회에 좋은 성능을 제공하는 대안이 필요합니다. 이론적으로 저는 오버 헤드 비용이 고려되지 않을 때 1500 Million * 3 (PairVal1, PairVal2, Document-ID) * 4 (bytes per Integer) = 18GB을 사용하고 있습니다. 그래서 내 문제에 대한 좋은 대안이 있습니까?

Answer 1

파일 시스템을 사용할 수 있습니까?

첫 번째 정수 다음에 오는 이름 지정 디렉토리는 두 번째 정수에 대해 각각의 이름이 지정된 텍스트 파일을 만듭니다. 텍스트 파일의 각 줄은 문서 ID가 될 수 있습니다.

모든 I/O에서 속도가 크게 저하 될 수 있습니다. 가능한 빨리 디스크를 확보하십시오. 디렉터리 이름, 파일 이름 및 파일 내용이 이진 정수 대신 ASCII 텍스트가되기 때문에 저장소 요구 사항도 상당히 증가합니다.

Answer 2

공간을 줄이기위한 하나의 해결책은 예를 들어, 대신 당신이 페어링 기능을 사용해야합니다 int에 std::map<std::pair<int,int>, std::unordered_set<int>> 사용 변환 std::pair<int, int>를 들어 std::unordered_map<int, std::unordered_set<int>>

이다 :

Cantor’s Pairing Function

분명히

당신이 제한된다 당신의 쌍에서 더 작은 숫자를 사용하십시오.

최대 두 개의 16 비트 부호있는 정수 (32767, 32767)에 대한 매핑은 부호가있는 32 비트 정수의 최대 값보다 약간 큰 2147418112가됩니다.

다른 옵션은 생성, 그것은 C++로 작성된 자신의 A B 트리에 기반을 둔 인덱서, 또는 xapian 같은 오픈 소스 검색 엔진 라이브러리를 사용하고 빠르고 사용하기 쉽습니다.

Xapian은 개발자가 고급 색인 생성 및 검색 기능을 자신의 응용 프로그램에 쉽게 추가 할 수있게 해주는 고도로 적응 가능한 툴킷입니다.

Answer 3

SQLite 나 BerkeleyDB 또는 Tokyo Cabinet과 같은 내장 데이터베이스의 작업 일 수 있습니다.

사용중인 데이터의 양이 RAM을 초과하는 경우 실제로 디스크에서 작동 할 수있는 것이 필요합니다.