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

숫자 1, 다른 종류의 실행간에 duration을 다시 설정하지 않는 것 같습니다. 즉, 개별 반복 기간의 합계가 각 정렬 단계를 통해 아래로 전파됩니다 (다음 지점도 문제가 아닌 경우).

다음으로 별도의 변수를 설정해야합니다 (durationSum). 반복 후 요약 단계에서 현재 duration을 사용하고 있습니다. 현재, 당신은 매 반복마다 당신의 돈을 날려 버리고 있습니다. 예를 들어

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

다음, 당신은 유형의 오류를 만들고있어. 당신은이 : 최소한의 편집으로

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

, 이것은 더 정확하게 작동합니다 (그러나 durationSum를 사용한다) :

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

을하기 전에, 당신이 사용하는 정수 부문은 2000 duration을 분할하는 "말을했다, THEN 촉진 그것을 double으로 나누고 CLOCKS_PER_SEC으로 나눕니다 (피연산자 중 하나가 double이고 하나는 정수이므로 부동 소수점 나누기가 있음) 2000.0을 사용하면 duration을 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; 

, 현실에서 그것은 clock_t 반면 당신이 int으로 duration를 사용하고 있습니다, 당신은 64 비트 시스템에있는 경우,이 가능성이 높다 clock()에 의해 반환되는 64 비트 숫자이며 32 비트 정수 int에 "좁혀진"(다운 캐스트)입니다. clock_t을 사용하십시오.