unordered_mapへの挿入に時間がかかりすぎる

Question

ファイル（約50万件）から数字を読み込んでデータ構造に挿入するプログラムを作成しました。数字は区別されます。 私は。std::make_pair(myNumber, emptyStruct))を使用して別の構造体（と

をunordered_mapに数字を挿入していますそして、すべての数字を挿入した後、私は数百の時間を検索し、それを使用しています。私は、までDSを削除することはありませんプログラムの実行が終了しました

プロファイリング後、挿入操作に実行時間の約50％がかかることに気付きました（挿入の回数だけ実行される他のコードもありますが、時間がかかる）

リサイズに時間がかかると思ったので、私は500,000でリザーブ機能を使用しましたが、結果は同じです。

私の知る限り、このDSはO（1）の挿入と検索でなければならず（トレードオフは大きなメモリです）、挿入に時間がかかる理由はわかりません。結果を改善するにはどうすればよいですか？

Answer 1

具体的には値を使用せず、単に存在を検索するので、std :: unordered_setを参照してください。マップ内のすべてのキーにダミー値を渡したときに望むことを実行します。

最初に、私は誰もが言ったことを繰り返してみたいと思います：それを使用するために500,000個のアイテムを数百回挿入することは、かなりの時間を費やすことになります。それを回して、あなたが探しているもののセットを作り、それから50万回を探します。

私は、アカウントにハッシュテーブルの性質を取ることによって、テストアプリで50万項目の挿入時にいくつかの改善を得ることができた、と述べているすべて：

がhttp://en.cppreference.com/w/cpp/container/unordered_mapの確認は、私はこれらを見つけた：

[挿入]の複雑さ：平均の場合：O（1）、最悪の場合O（サイズ（））

デフォルトで、unordered_map容器は、1.0のmax_load_factorを有します。

500000アイテムのスペースを予約すると、500000個のバケットが取得されます。 500000個のバケットに500,000個のデータを置くと、多くの衝突が発生します。私は余分なスペースを予約し、それはより速かった。

スピードが本当に必要で、何らかのエラーが発生する場合は、ブルームフィルタを調べてください。

Answer 2

無秩序マップは、ハッシュテーブルで実装されています。それは一定の挿入時間を償却しました。マップのサイズを予約することは助けになりますが、あまりにも多くのことではありません。あなたがそれに挿入するという点でそれほど良いことはありません。

これは、時間を節約できる可能性があることを意味しますが、それはわずかなものに過ぎません。例えば、ベクトルへの挿入はわずかに高速ですが、一定時間の償却も行われます。だから、あなたは検索のコストで挿入に数秒を節約します。

これは、データベースが役立つところです。代わりにsqliteデータベースにデータがあるとします。データベースを作成し、検索値を主キーとして、データ値を他の属性として作成し、その値を一度テーブルに挿入します。今、プログラムは単に実行し、データベースに照会します。最低限必要なものだけが読み込まれます。この場合、sqliteデータベースは使用している順序付けられていないマップの役割を持ちます。