2

サイズ 100 の配列とベクトルを作成し、ランダムな値を生成して、配列とベクトルの両方をソート済みとして維持しようとしています。これが私のコードです

vector<int> myVector;
int arr[SIZE];
clock_t start, finish;
int random;
for(int i=0; i<SIZE;i++)
{
    myVector.push_back(0);
    arr[i] = 0;
}
    //testing for Array
start = clock(); 
for(int i=0; i<MAX;++i)
{
    random = getRandom(); //returns rand() % 100
    for(int j=0; j<SIZE;++j){
        if(random > arr[j])
        {
            for(int k = SIZE - 1; k > j ; --k)
            {
                arr[k] = arr[k-1];
            }
            arr[j] = random;
            break;
        }
    }
}
finish = clock();
cout << "Array Time " << finish - start << endl;

//Vector Processing
start = clock();
for(int i=0; i<MAX;++i)
{
    random = getRandom(); //returns rand() % 100
    for(int j=0; j<SIZE;++j){
        if(random > myVector[j])
        {
            for(int k = SIZE - 1; k > j ; --k)
            {
                myVector[k] = myVector[k-1];
            }
            myVector[j] = random;
            break;
        }
    }
}
finish = clock();
cout << "Vector Time " << finish - start << endl;

出力は次のとおりです。

配列時間 : 5

ベクトル時間: 83

この場合、ベクトルが配列に比べて非常に遅い理由を理解できませんか? これは、配列よりもベクトルを優先するという経験則と矛盾しませんか。

助けてください ！

4

3 に答える 3

4

まず第一に、プログラミングの多くの経験則は、数ミリ秒のパフォーマンスを向上させることではなく、複雑さを管理してバグを回避することです。この場合、ほとんどのベクトル実装がデバッグ モードで実行し、配列では実行しない範囲チェックを実行します。また、動的配列のメモリ管理についても説明します。ベクトルはメモリ自体を管理しますが、メモリ リークが発生するリスクがあるため、配列で手動で管理する必要があります (a を忘れdelete[]たり、代わりに使用したりしたdeleteことがありますか? 私はあなたが持っているでしょう!)。そして、使いやすさについてです。たとえば、ベクトルのサイズを変更したり、要素を途中に挿入したりします。これは、手動で管理された配列では面倒な作業です。
つまり、パフォーマンスの測定値が経験則に反することは決してありません。経験則では決してパフォーマンスを目標にしないからです。パフォーマンス測定は、コーディング ガイドラインに従わない数少ない理由の 1 つにすぎません。

一見すると、最適化が有効になっていないと思います。ベクターのパフォーマンス低下の主な原因は、多くのベクター実装でデバッグ ビルドが有効になっているインデックス チェックです。これらは最適化されたビルドでは機能しないため、最初に考慮する必要があります。経験則: 最適化を有効にしないパフォーマンス測定は意味がありません

最適化を有効にしてもアレイのパフォーマンスが向上する場合は、別の違いがあります。

配列はスタックに格納されるため、コンパイラはアドレスを直接使用してコンパイル時にアドレス オフセットを計算できますが、ベクトル要素はヒープに格納され、コンパイラはベクトルに格納されたポインタを逆参照する必要があります。オプティマイザーがポインターを一度逆参照し、その時点からアドレスオフセットを計算することを期待しています。それでも、特にオプティマイザーがループを少し展開できる場合は、コンパイル時に計算されたアドレス オフセットと比較してパフォーマンスがわずかに低下する可能性があります。ここではリンゴとナシを比較しているため、これは経験則と矛盾しません。経験則によると、

動的配列よりも優先しstd::vector、固定配列よりも優先します。std::array

したがって、動的に割り当てられた配列 (ある種の を含むdelete[]) を使用するか、固定サイズの配列をstd::array. C++14 では、ゲーム内の新しい候補、つまりstd::dynarray、C の VLA に匹敵するサイズ変更不可のランタイム長配列である C++14 VLA を考慮する必要があります。

更新: コメントで指摘されたように、オプティマイザーは、読み取ったことのない配列に対する操作など、副作用のないコードを特定するのに優れています。std::vector実装は非常に複雑であるため、オプティマイザーは通常、これらのいくつかのレイヤーの間接化を認識せず、すべての挿入を最適化することができないため、ベクトルの時間と比較して、配列の時間はゼロになります。ループの後に配列内容を読み取ると、そのような無作法な最適化が無効になります。

于 2013-07-03T15:34:27.943 に答える
-1

vector クラスはメモリを動的に拡張する必要があり、時々全体をコピーする必要があります。また、再割り当てなど、多くの操作のために内部関数を呼び出す必要があります。また、境界チェックなどのセキュリティ機能を備えている場合もあります。

一方、配列は事前に割り当てられており、すべての操作はおそらく内部関数を呼び出しません。

これは、機能を追加するための間接費です。

そして、すべての場合においてベクトルは配列よりも高速であるべきだと誰が言いましたか? 配列を大きくする必要はありません。これは、配列が実際に高速になる特殊なケースです。

于 2013-07-03T15:42:12.910 に答える