multimap<int,string> を使用して数十万のアイテム (>300K) を格納していたときに、分析のためにさらにデータを追加する必要があることに気付きました。そのため、stl に必要ないくつかの項目とオーバーライドされた演算子を保持するクラスを作成し、multimap<ourStruct,String> を使用しました。これは問題なく機能し、(いくつかのテスト データを使用して) 以前よりもそれほど時間はかかりませんでした。その後、すべての項目を追加し終わった後に並べ替えさえすれば、 stl <list> が問題なく動作することに気付きました。驚いたことに、すべてのアイテムをマルチマップに追加すると、すべてのアイテムをリストに追加して並べ替える合計時間よりも簡単に勝ることがわかりました。
これは私たち EE タイプには意味がありません。私たちの考えでは、マルチマップへのすべての挿入はリストをトラバースして最後に追加する必要があり、リストと同様に (プッシュバックを介して) 最後に追加するだけです。 、うまくいけば、並べ替えにそれほど時間がかかりません。
もう 1 つの事実: 私たちは最初にリストをソートせずに比較テストを行い、リストを使用して速度が大幅に向上したことに感激しました。次に、並べ替えを追加し、少し唖然としました...
そこにいるCSの専門家の中で、検討したいと思っている人はいますか?
2 に答える
0
ハッシュへの参照を削除.. バランスのとれたツリーは、n2 トラバースのみが必要な理由です。
于 2011-04-21T23:17:17.290 に答える
0
std::multimapバランス ツリー1を使用するため、アイテムを挿入するときにリスト全体をトラバースしません。挿入のためにトラバースされるアイテムの数は、コレクション内のアイテム数の 2 を底とする対数にほぼ等しくなります。
あなたが言ったことに基づいて、あなたの最善の策は、おそらくデータをベクトルに入れてからソートすることでしょう。
1技術的には、標準はバランスの取れたツリーを直接要求するものではありませんが、ソートされた順序でトラバースする機能と、最悪の場合の挿入と削除の対数的複雑性を必要とし、満たすことができる他の多くのデータ構造を認識していません。その要件。
于 2011-04-21T23:17:32.980 に答える