5

次のように、ブーストベクターと標準ベクターについて興味深いテストを行いました

int N = 10000;
{
    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::vector<int> v;
    for (int i = 0; i < N; ++i)
    {
        v.insert(v.begin(), i);
    }
}

win32 リリース、vc2010 でコンパイル、/O2 /Oy-

N = 10000 の場合

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

f ブースト ベクトル: 0.056174 秒の壁、0.062400 秒のユーザー + 0.000000 秒のシステム = 0.062400 秒の CPU (111.1%)

N = 100,000 の場合

標準: 14.050757 秒の壁、14.055690 秒のユーザー + 0.000000 秒のシステム = 14.055690 秒の CPU (100.0%)

ブースト: 5.585048 秒の壁、5.584836 秒のユーザー + 0.000000 秒のシステム = 5.584836 秒の CPU (100.0%)

両方に reserve(N) を追加すると、CPU 時間はほとんど変わりません。

それらの間に違いはありますか？Boost は std よりもはるかに高速ですが、なぜですか? ありがとう。

sizeof()、std::vector 16、boost::container::vector 12 を確認します。

4

2 に答える 2

6

すべてのコードの速度は、コンパイラごと、およびそのコンパイラのバージョン間で異なることに注意してください。標準ライブラリは、プラットフォーム間で移植可能に動作するコードを提供しますが、速度を保証することは困難です。

このコードを自分のマシンでのみ実行している場合は、より高速なオプションを選択する必要があります。普遍的に高速な選択をしたいという理由でこの質問をしているのであれば、それをテストする以外に何が足りないのかを知る方法はないと思います。

当然のことながら、一般的な方法で速度について疑問に思っている場合は、さまざまな数のオブジェクトを挿入して評価し、多くの反復テストを実行し、さまざまなオブジェクト (クラス、ダブル、文字など）。また、さまざまな量の空きスタック スペースを使用して、これらすべてを実行することもできます。すべての要因を考慮しない場合、デフォルトの質問は、「なぜ、私の特定のケースでは、速度に違いがあるのですか?」になります。とは言いにくいのが普通です。

より適切な質問は、「さまざまなテスト条件下で、同様に機能するこれら 2 つのコードの速度の違いを観察しました。これを説明できるアーキテクチャ上の違いはありますか?」答えは多分です。

std::vector の cplusplus.com

内部的に、ベクトルは動的に割り当てられた配列を使用して要素を格納します。この配列は、新しい要素が挿入されたときにサイズが大きくなるように再割り当てする必要がある場合があります。これは、新しい配列を割り当てて、すべての要素をそこに移動することを意味します。これは、処理時間の点で比較的高価なタスクであるため、要素がコンテナに追加されるたびにベクトルが再割り当てされることはありません。

代わりに、ベクトル コンテナーは、拡張の可能性に対応するために追加のストレージを割り当てる場合があります。そのため、コンテナーは、その要素を格納するために厳密に必要なストレージ (つまり、そのサイズ) よりも大きな実際の容量を持つ場合があります。ライブラリは、メモリ使用量と再割り当ての間でバランスをとるために、成長のためのさまざまな戦略を実装できますが、いずれの場合でも、再割り当ては対数的に増加するサイズの間隔でのみ発生する必要があるため、ベクトルの最後に個々の要素を挿入すると、償却された一定の時間が提供されます。複雑さ (push_back を参照)。

このことから、表示されている動作は使用している STL ライブラリの特定のバージョンに依存し、増加は対数的であり、増加には通常多くのコピーが必要であることがわかります。両端キューは多くのコピーを必要としないため、テストでのスケーリングが向上する可能性があります。

おそらく、boost::container同様に機能します。書き込みが見当たらないのでわかりません。しかし、私はこれを見つけました:

Boost.Container が提供するすべてのコンテナーは配置挿入を実装します。つまり、一時オブジェクトを作成することなく、ユーザーの引数からオブジェクトをコンテナーに直接構築できます。可変個引数テンプレートをサポートしないコンパイラの場合、配置挿入は有限 (10) 個の引数までエミュレートされます。

std::vector が同様のアーキテクチャを使用せず、代わりに一時オブジェクトを作成する場合、実行時間に違いが生じる可能性があります。しかし、おそらくこれは型には当てはまりませんint。おそらく、他の誰かが異なるアーキテクチャの違いを見つけることができます。

于 2013-01-02T20:08:32.853 に答える