2013-02-18 6 views
12

私は入力が非常に1 TB近い非常に大きいデータ構造に取り組んでいます。私は連想コンテナにデータをロードする必要があります。map対C++(パフォーマンス)のマルチマップ

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

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

map <const char*, vector <const char*> ,cmptr> mmap; 
+5

なぜあなたはそれらの両方を試してみませんか? –

+7

実際には、どちらの場合も、1TBのRAMを搭載したシステムを使用している場合を除き、パフォーマンスはディスク速度に左右される可能性があります。 –

+1

'const char * 'をキーとして使用する場合は、比較述部これが機能するには代わりに、 'std :: map 'を使う方が簡単です。 –

答えて

17

あなたはおよそmapmultimap対を考えてあなたの時間を無駄にしています。ビンの数がNであり、1ビンあたりのアイテムの平均数がMであると仮定する。

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

  • フェッチするO(Mログ+ Nログ)
  • 反復はO(1である
  • 挿入はO(Mログ+ Nログ)
  • 削除である(Mログ+ Nログ)Oであります)

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

  • はO(Nを記録)
  • 挿入はO(Nを記録)
  • 削除されているフェッチ・O(Nを記録)
  • 反復はあなたとして(1)

OですMが非常に大きい場合を除いて、その違いは話す価値がありません。

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

1 TBのデータにデータベースを使用する方がよい場合があります。このタスクのほとんどすべてのデータベースを選択できます。 Kyoto Cabinetはシンプルで、あなたが望むことをしますが、PostgreSQL、MySQL、Sqlite、Dynamo、Redis、MongoDB、Cassandra、Voldemortも使用できます。

+2

「1 TBのデータ」については、実際にはどのデータベースにどのように注意する必要がありますかデータにアクセスします。制限などがあります。 –

+1

私はスーパーコンピュータで作業しています。 – Manish

+2

@ user15662:このような仕事のために、 'std ::'以上に京都内閣を推奨します。 –

5

1 TBの入力では、どちらも使用しません。ほとんどの場合、RAMが不足している可能性があります。 B-treeのようなディスクデータ構造上のものを使用してください。

関連する問題