Длительность алгоритмов сортировки C++

Question

Я работал над вычислением продолжительности этих алгоритмов сортировки. Я зацикливал все методы сортировки в 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; 
} 

Answer 1

Ошибка в вашей программе заключается в том, что вы возвращаете продолжительность по всему циклу. Более чистым способом обработки времени было бы поставить переменную модификацию duration вне цикла for. Например:

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

EDIT: забыли удалить часть внутри петли. Исправлено.

Answer 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 должны быть увеличены до двойника для деления с плавающей запятой к 2000 году.

И, наконец, было бы лучше рассмотреть предельные затраты на петлю, пренебрежимо малые по сравнению с одной итерацией сортировки, и выполнять только два вызова функции clock() для 2000-титераций.

Например:

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() и «суженное» (downcast) в 32-разрядное целое число int. Используйте clock_t.