3

そのため、C++ でいくつかの並べ替えアルゴリズムを実装して遊んでいますが、アルゴリズムを実行せずに入力データを作成するのに時間がかかるため、現時点でそれらをベンチマークするのは面倒です。現在、入力の各長さ (1000、2000、...) を 10 回テストして、ある程度平均的な時間を取得しています。これらの 10 回ごとに、次のようにしvectorて、正しい長さの新しい乱数を作成します。

    // Each of the 10 times.
    for(int j = 0; j < 10; j++) {

        A.clear();

        // 'i' is the current input size.
        for(int k = 0; k < i; k++) {
            A.push_back(rand() % 10000);
        }

        // Other stuff
    }

これを行うより良い方法はありますか？rand() を 10000 に制限することを気にする必要がありますか、それとも私の OCD 脳がラウンド数を好むだけですか? (つまり、モジュロ演算は、10 のループごとに最大で - 現在 - 10,000 まで実行されていると考えると、実際にはかなりの時間がかかっている可能性があります。) または、実行するたびに新しいベクトルを本当に作成する必要があります選別？作成されたベクトルが偏っている可能性があると感じたため、そうしてきました。そのベクトルを生成してから10回使用すると、答えがかなりずれてしまう可能性があります...

4

3 に答える 3

1

非常に役立つヒントを提供するcplusplus.com ( http://www.cplusplus.com/reference/stl/vector/ ) からの引用:

「再割り当ては、通常、ベクターが使用するストレージ領域全体を新しい場所にコピーする必要があるため、パフォーマンスの点でコストのかかる操作になる可能性があります。したがって、ベクターのサイズの大幅な増加が計画されているときはいつでも、明示的にメンバ関数 を使用してベクトルの容量を示しますvector::reserve。"

を使用vector::reserveすると、ほぼ確実にパフォーマンスが向上します。

編集:( http://www.cplusplus.com/reference/algorithm/random_shuffle/ )を使用して、作成されたベクトルをシャッフルすることができrandom_shuffleます(明らかに、random_shuffle要素の数が線形です)。

于 2010-07-24T15:59:51.947 に答える
1

これを行うより良い方法はありますか？

うん、スピードアップのためにここでやりたいことがいくつかあります。前述のように、std::vector にスペースを確保してから、既知の要素に値を代入する方が高速です。また、事前インクリメント ( var++ ではなく ++var ) は、最適化されていないコンパイラを使用する場合により高速です。誰がそれをビルドしても、コードを高速に保つためだけに、今後はそれを行うことを検討することをお勧めします。メモリに関する限り、些細なことだと思うかもしれませんが、符号なしで不当に大きくない既知のサイズを使用するときは、for ループに unsigned short を使用します。

ただし、モジュロについて。必要がない場合は、使用しないことをお勧めします。ベクターに保持されているデータ型によっては、その型の最大ストレージ容量を超えた場合、結果が折り返されます。

変数のラップでより多くの処理能力を消費するかどうかはわかりません。もしそうなら、モジュロを実行するよりも安価な操作であるかどうかはまだわかりません。rand を使用する前に、既知のサイズでいくつかの速度テストを実行することをお勧めします。

    A.reserve(i * i);
    for(unsigned short j = 0; j < 10; ++j) {            
        for(unsigned short k = 0; k < i; ++k) 
            A[k + (i*10)] = rand();                
        // Other stuff
    }

編集

注意すべき非常に小さな変更: ループは 10 回しか実行されないため、short ではなく unsigned char を使用することもできます。少なくとも Win32 では、半分のメモリが必要です。

    A.reserve(i * i);
    for(unsigned char j = 0; j < 10; ++j) {            
        for(unsigned char k = 0; k < i; ++k) 
            A[k + (i*10)] = rand();                
        // Other stuff
    }
于 2010-07-24T17:09:27.743 に答える
-1

私はそれを作成します。見てみましょう：

#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <sstream>

int main(int argc, char* argv[]){
    if (argc < 2){
        printf("No arguments found\n");
        exit(1);
    }
    int maxi;
    maxi = atoi(argv[1]);
    int * a;
    a = new int [5];

    std::stringstream ss;
    ss << maxi;
    printf(ss.str());
    printf("\n");
}
于 2011-12-28T18:53:07.550 に答える