16

入力が1TB近くと非常に大きいデータ構造に取り組んでいます。データを連想コンテナにロードする必要があります。

データの全体が重複しているため、マルチマップを使用していますが、誰かがこれを使用する代わりにベクトルのマップを使用するように提案しました。パフォーマンスの違いは何ですか？

 map<const char*, const char*, cmptr> mulmap;

 map <const char*, vector <const char*> ,cmptr> mmap;
4

2 に答える 2

22

map対について考えるのは時間を無駄にしていますmultimap。ビンの数が N で、ビンごとのアイテムの平均数が M であるとします。

Astd::multimap<Key, Val>は通常、重複キーを持つ RB ツリーを使用します。

  • フェッチは O(log N + log M)
  • 挿入は O(log N + log M)
  • 削除は O(log N + log M)
  • 反復は O(1)

はstd::map<Key, std::vector<Val>>通常、一意のキーを持つ RB ツリーを使用します。

  • フェッチは O(log N)
  • 挿入は O(log N)
  • 削除は O(log N)
  • 反復は O(1)

ご覧のとおり、M が非常に大きくない限り、違いについて話す価値はありません。

ただし、両方のストレージは RAM によって制限されます。1 TB はほとんどのシステムで実現不可能であり、私が聞いた限りではそれをサポートしているマザーボードはありません。

1 TB のデータにはデータベースを使用することをお勧めします。このタスクには、ほぼすべてのデータベースを選択できます。 Kyoto Cabinetはシンプルで、やりたいことができますが、PostgreSQL、MySQL、Sqlite、Dynamo、Redis、MongoDB、Cassandra、Voldemort なども使用できます。

于 2013-02-18T08:29:13.737 に答える
5

1 TBの入力では、どちらも使用しません。ほとんどの場合、十分なRAMがありません。Bツリーのようなディスク上のデータ構造を使用します。

于 2013-02-18T08:31:35.233 に答える