4

我一直在计算这些排序算法的持续时间。我将所有排序方法循环了 2000 次，然后将总持续时间除以 2000 以获得适当的持续时间值。问题是; 它没有显示排序方法的特定代码部分所花费的确切时间值。我的意思是duration变量显示通过程序流增加的值。例如，对于N = 10000，insertionSort()给出 0.000635，mergeSort()给出 0.00836 并heapSort()给出 0.018485，当我改变这些的顺序时，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;

之前，您说“使用整数除法除以duration2000，然后将其提升为 adouble并除以CLOCKS_PER_SEC（这次使用浮点除法，因为操作数之一是 adouble和一个整数）。使用2000.0强制duration提升为 double用于除以 2000 的浮点除法。

最后，与单次排序迭代相比，最好考虑循环开销可以忽略不计，并且每 2000 次排序迭代只调用两次clock()。

例如：

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的是 as ，而int实际上它clock_t是clock()一个 32 位整数int。使用clock_t.

于 2012-11-16T01:11:53.477 回答