0

ほぼ10億（または1兆）のレコードを持つ1つのファイルを解析しています。私は使用しています

 struct ltstr
 {
    bool operator()(const char* s1, const char* s2) const
    {
        return strcmp(s1, s2) < 0;
    }
 };

 multimap<char*, map<char*, char*, ltsr>,ltstr > m;

これは、C ++で上記のデータ構造を使用するための効率的な方法ですか？

よろしく

4

1 に答える 1

1

いいえ、ちがいます。数十億のレコードは言うまでもなく、今日のコンピュータのオペレーティングメモリには収まりません。10億レコードは、マップのオーバーヘッドだけで32 GBを消費し、さらにキーと値へのポインターに16 GBを消費し、明らかにn個以上のGBを消費します。ここで、nは実際のデータのキーと値の平均長です（64ビットを想定）システム。32ビットシステムでは半分になりますが、3 GBのアドレス空間の制限には収まりません）。このような量のメモリを搭載している大規模なサーバーは、世界中にほとんどありません。

このような大量のデータを処理するための唯一のオプションは、それらを小さなバッチで処理することです。各要素で個別に処理できる場合は、一度に1つの要素をロードし、処理して破棄するだけです。データのサイズに関係なく、ストリーミング処理は常に高速です。これは、必要なメモリ量が固定されているだけであり、CPUキャッシュを効率的に利用できるためです。

そのように処理できない場合は、特定の順序が必要であるか、エントリなどを検索する必要があるため、適切な外部（ディスク上の）構造にデータを準備する必要があります。つまり、外部マージソート（パーティションを一時ファイルに書き込む）でそれらをソートし、Bツリーやハッシュなどでインデックスを付けます。大変な作業です。しかし幸いなことに、これらのアルゴリズムを実装するライブラリがいくつかあります。私はどちらかを提案します：

  • * DMB 、 GDBM、Berkeley DB、ndbmなどの外部ハッシュライブラリ。これらは、最も単純なマップの外部アナログを提供しますが、APIはCベースです。
  • stxxlは、それらで動作するいくつかの外部コンテナーとアルゴリズムの外部バリアントを提供します。大きな利点は、APIが標準ライブラリコレクションと同じであることです。
  • より複雑なデータ操作については、sqliteを選択してください。それは同じように高速で、より複雑なデータ処理はSQLで表現するのが簡単です。
于 2013-01-10T08:26:48.677 に答える