4

私は、これらの並べ替えアルゴリズムにかかる時間を計算することに取り組んできました。すべてのソート方法を 2000 回ループし、合計期間を 2000 に分割して、期間の適切な値を取得しました。問題は; 並べ替えメソッドの特定のコード部分にかかる時間の正確な値は示していません。つまり、duration変数は、プログラム フローを通じて増加する値を示します。たとえば、 forは 0.000635 をN = 10000与え、 0.00836 を与え、0.018485 を与え、これらの順序を変更すると、アルゴリズムの種類に関係なく、プログラムを介して上がります。プロセスごとに異なる期間の値を指定しようとしましたが、うまくいきませんでした。誰かがこの問題を理解するのを手伝ってくれますか、それとも他の時間測定スタイルはありますか?insertionSort()mergeSort()heapSort()duration

これがばかげた問題であり、私の文法が悪い場合は申し訳ありません。

int main(){

    srand(time(NULL));

    int N, duration;

    cout << endl << "N : ";
    cin >> N; // N is array sze.
    cout << endl;

    // a4 would be the buffer array (for calculating proper duration).
    int *a1 = new int[N];
    int *a2 = new int[N];
    int *a3 = new int[N];
    int *a4 = new int[N];

    cout << endl << "Unsorted array : " << endl;

    for (int i = 0; i < N; i++){

        a4[i] = rand() % 100;
        cout << a4[i] << " ";
    }

/*------------------------------------------------------------------------------*/

    cout << endl << endl <<"Sorting with Insertion Sort, please wait..." << endl;

    for(int i = 0; i < 2000; i++){

        a1 = a4;

        duration = clock();
        insertionSort(a1, N - 1);
        duration += clock() - duration;
    }

    cout << endl << "Insertion sort : " << endl;

    print(a1, N);

    cout << endl << endl << "Approximate duration for Insertion Sort : ";
    cout << (double) (duration / 2000) / CLOCKS_PER_SEC;
    cout << " s." << endl;

/*------------------------------------------------------------------------------*/

    cout << endl << endl << "Sorting with Merge Sort, please wait..." << endl;

    for(int i = 0; i < 2000; i++){

        a2 = a4;

        duration = clock();
        mergeSort(a2, 0, N - 1);
        duration += clock() - duration;
    }

    cout << endl << "Merge sort : " << endl;

    print(a2, N);

    cout << endl << endl << "Approximate duration for Merge Sort : ";
    cout << (double) (duration / 2000) / CLOCKS_PER_SEC;
    cout << " s."<< endl << endl;

/*------------------------------------------------------------------------------*/

    cout << endl << endl << "Sorting with Heap Sort, please wait..." << endl;

    for(int i = 0; i < 2000; i++){

        a3 = a4;
        duration = clock();
        heapSort(a3, N);
        duration += clock() - duration;
    }

    cout << endl << "Heap sort : " << endl;

    print(a3, N);

    cout << endl << endl << "Approximate duration for Heap Sort : ";
    cout << (double) (duration / 2000) / CLOCKS_PER_SEC;
    cout << " s."<< endl << endl;

    return 0;
}
4

2 に答える 2

7

プログラムのエラーは、ループ全体で期間をリセットすることです。時間を処理するためのよりクリーンな方法は、duration変数の変更をforループの外側に配置することです。例えば：

duration = clock();
for(int i = 0; i < 2000; i++){
    a2 = a4;
    mergeSort(a2, 0, N - 1);
}
duration = clock() - duration

編集：ループ内の部分を削除するのを忘れました。修正されました。

于 2012-11-16T00:49:19.877 に答える
2

duration第一に、さまざまな種類の実行間でリセットされないようです。これは、個々の反復期間の合計が、各並べ替えフェーズを介して伝播することを意味します (次のポイントも問題にならない場合)。

次に、別の変数をセットアップし、それを呼び出して、反復後の要約フェーズでdurationSum現在使用しているように使用する必要があります。duration現在、反復ごとに合計を吹き飛ばしています。

例えば：

clock_t durationSum = 0;
clock_t duration = 0;

for(int i = 0; i < 2000; i++){

    a1 = a4;

    duration = clock();
    insertionSort(a1, N - 1);
    durationSum += clock() - duration;
}

次に、 amortizing 時に型エラーを起こしていますduration。あなたが持っている：

cout << (double) (duration / 2000) / CLOCKS_PER_SEC;

最小限の編集で、これはより正確に機能します (ただし、 を使用する必要がありますdurationSum):

cout << (double) (duration / 2000.0) / CLOCKS_PER_SEC;

以前は、「整数除算を使用durationして 2000 で除算し、次にそれを a に昇格させて除算doubleします (オペランドの 1 つが aで 1 つの整数CLOCKS_PER_SECであるため、今回は浮動小数点除算を使用します)」と言っていた。 2000 による浮動小数点除算の場合。double2000.0duration

最後に、1 回の並べ替えの反復に比べてループ オーバーヘッドを無視できると考えて、2000 回の並べ替えの反復ごとに clock() の呼び出しを 2 回だけ行う方がよいでしょう。

例えば：

clock_t insert_sort_start = clock();

for(int i = 0; i < 2000; i++){
    a1 = a4;
    insertionSort(a1, N - 1);
}

double duration_sec = (clock() - insert_sort_start) / 2000.0 / CLOCKS_PER_SEC;

duration最後に、 をとして使用しているのintに対し、実際にはを使用していることに注意してくださいclock_t。64 ビット システムを使用している場合、64 ビットの数値が によって返されclock()、「ナロー化」(ダウンキャスト) される可能性が非常に高くなります。 32 ビット整数int。を使用しclock_tます。

于 2012-11-16T01:11:53.477 に答える