C++排序算法持续时间

Question

C++排序算法持续时间

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;
}

- burakongun

请注意，原始数据的顺序也会影响排序性能。你不仅需要在一个数据集上多次执行排序，还需要在许多数据集上执行排序，以获得更准确或整体的性能评级。此外，请注意运行在计算机上的其他应用程序可能会影响计时。 - Thomas Matthews

2个回答

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;
}

接下来，当你对 duration 进行摊销时，你犯了一种类型错误。你的代码如下：

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

只需进行最小的编辑，这个方法将更加精确（但应该使用durationSum）：

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

之前，你说过“使用整数除法将duration除以2000，然后将其提升为double并除以CLOCKS_PER_SEC（这次使用浮点除法，因为其中一个操作数是double而一个是整数）。使用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 作为一个 int，但实际上它是一个 clock_t 类型，如果您在一个64位系统上，那么很可能这是一个由 clock() 返回的64位数字，并且被 "缩小"（向下转换）为32位整数int。应该使用 clock_t。

- Matthew Hall

另外，与您直接问题无关的一点小事：为什么要分配 a1、a2 和 a3？因为当前你只是重新分配它们指向 a4（并且失去了对其分配的内存引用，导致泄露）。你可以只声明它们为 int*，不用使用 new 来初始化它们。 - Matthew Hall

谢谢您提供的所有技巧。我仍然是一个新手，需要不断学习和进步 :) - burakongun

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jma127 · Accepted Answer

您程序中的错误在于您在循环中重置了duration。更好的处理时间的方式是将duration变量的修改放在for循环之外。例如：

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

编辑：忘记删除循环内的部分。现已修复。

此处内容与IT技术无关，仅为补充说明。