1

並べ替えられたインデックス付きのコンテナーが必要です。std:set または std::vector に基づいてビルドしたい。set を使用すると、その要素のインデックスを計算するために高価な std::distance が必要になります。ベクトルを使用することで、要素の追加または削除にはコストがかかることがわかっています。私の要素がポインタ（小さなオブジェクト）であるとしましょう。2 つの操作の複雑さが同じであることはわかっています。しかし、どちらが速いですか？ありがとう。

4

3 に答える 3

3

並べ替え順序とインデックスによる検索をサポートするデータ構造が必要な場合は、これらの操作を正確にサポートするように特別に設計されたデータ構造である順序統計ツリーを確認する必要があります。O(log n) 時間での挿入と削除、O(log n) 時間での要素のインデックスのルックアップ、O(log n) 時間での値またはインデックスによるルックアップもサポートしているため、ベクトルまたはセットのいずれかが近づきます。

残念ながら、STL には順序統計ツリーが構築されていないため、サード パーティのライブラリを検索する必要があります (この前の質問と回答はその例です)。とはいえ、注文統計ツリーから期待できるスピードアップは、投資に見合うだけの価値があるはずです。

お役に立てれば！

于 2013-01-02T18:41:53.173 に答える
2

皆さんの提案に従って、私はそれをボトムコードとして測定しました（flat_setが追加されました）。デバッグバージョンの結果は

セットの場合: 4.720976 秒の壁、4.711230 秒のユーザー + 0.000000 秒のシステム = 4.711230 秒の CPU (99.8%) (ほとんど時間がかからない set::insert もテスト済み)

ベクトルの場合: 1.407571 秒の壁、1.404009 秒のユーザー + 0.000000 秒のシステム = 1.404009 秒の CPU (99.7%)

flat_set の場合: 0.327714 秒の壁、0.327602 秒のユーザー + 0.000000 秒のシステム = 0.327602 秒の CPU (100.0%)

また、リリース バージョン (コンパイラの最適化でコードが過剰に処理されないように、結果を書き出す必要があります) では、それぞれ約 10 倍の速度向上が得られます。

そして私の結論は、ベクターは 2 ～ 3 倍高速であり、ブースト flat_set が最適であるということです。また、エントリ数が数百未満 (200 など) の場合、flat_set 挿入は std::set (インデックス計算なし) より遅くはありません。

int N = 10000;
{
    boost::timer::auto_cpu_timer t;
    std::set<int> s;
    for (int i = 0; i < N; ++i)
    {
        auto it = s.insert(i);
        int index = std::distance(s.begin(), it.first);
    }
}

{
    boost::timer::auto_cpu_timer t;
    std::vector<int> v;
    for (int i = 0; i < N; ++i)
    {
        v.insert(v.begin(), i);
    }
}

{
    boost::timer::auto_cpu_timer t;
    boost::container::flat_set<int> s;
    for (int i = 0; i < N; ++i)
    {
        auto it = s.insert(-i); // negative sign is used to make insertion
                                // (at the beginning) expensive
        int index = std::distance(s.begin(), it.first);
    }
}
于 2013-01-02T18:39:10.523 に答える
0

ストレージとインデックスを分離します。

オブジェクトタイプ{T}のストレージベクトルにインデックスを付ける整数のベクトル{I}を持っています。

{I}は、{T}で指すオブジェクト間の比較によってソートされます。{I}への挿入/削除は{T}への挿入/削除よりも安価です。

{T}ベクトルに新しいアイテムを追加するときはいつでも、そのインデックスをソートされた{I}に挿入します。

アイテムを削除するときは、{I}のインデックスを削除しますが、{T}のオブジェクトはそのままにして、削除したばかりのインデックスを再利用ベクトル{I'}にプッシュバックするだけです。次回新しいアイテムを追加するときに、{I'}のインデックスをpop_backして、ストレージを再利用できます。

これまでに使用されたアイテムの数がわかっている場合は、起動時に{T}でresize（）を呼び出して、実行時の（再）割り当てを回避できます。

この方法は、ポインタのベクトルを使用する場合と似ています。オブジェクトストレージが連続したメモリにあるため、動的な割り当てが少なく、キャッシュに適しているという利点があります。

于 2013-01-02T19:13:03.247 に答える