メモリ効率の良いマップ<pair <int,int>、set <int>>代替

Question

私は膨大な量（1500万）の整数ペアを持ち、それぞれがドキュメントIDに関連付けられています。私の目標は、同じペアを持つドキュメントを検索することです。

私の最初のアイデアは、すなわちmap<pair<int,int>, unordered_set<int>>

例えば、関連する値としてキーと対値と文書IDを使用してハッシュマップ（std::map）を使用することであった。

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) 

が生じます

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

私の問題は、これが私の利用可能な24 GBのRAMを超える膨大な量のメモリを必要とすることです。したがって、私はメモリに収まるような挿入と検索のための良いパフォーマンスを持つ代替手段が必要です。理論的には、オーバーヘッドコストが考慮されていないときは1500 Million * 3 (PairVal1, PairVal2, Document-ID) * 4 (bytes per Integer) = 18GBを使用しています。だから私の問題のための良い選択肢はありますか？

Answer 1

ファイルシステムを使用できますか？

最初の整数の後に名前を付け、2番目の整数のそれぞれの名前付きテキストファイルを作成します。テキストファイルの各行はドキュメント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

明らか

あなたがこれらに限定されていますあなたのペアで小さい数字を使用してください。

2つの最大16ビット符号付き整数（32767,32767）のマッピングは、符号付き32ビット整数の最大値にちょうど足りない2147418112になります。

他のオプションはBツリーに基づいて独自のインデクサを作成、またはxapianのようなオープンソースの検索エンジンライブラリを使用して、それはC++で書かれており、高速で使いやすいですしています。

Xapianは高度に適応可能なツールキットで、開発者は高度なインデックス作成機能と検索機能をそれぞれのアプリケーションに簡単に追加できます。

Answer 3

これは、SQLiteやBerkeleyDB、Tokyo Cabinetなどの組み込みデータベースの仕事かもしれません。

使用しているデータ量がRAMを超える場合は、実際にディスクから作業できるものが必要です。