Почему время меняется?

Question

Так вот что я и сделал. Сначала у нас есть мой простой код сортировки вставки. Я решил рассчитать это. Вот как выглядит код:

#include<stdio.h>
#include<time.h>

int insertion_sort(int arr[], int len){
    int i;
    int key;
    for(i = 1; i < len; i++){
        key = arr[i];
        int j = i - 1;
        while(arr[j] >= key && j >= 0){
            arr[j + 1] = arr[j];
            j--;
        }
    arr[j + 1] = key;
    }
}


int main(){
    int arr[5] = {3, 2, 5, 1, 4};
    clock_t beg = clock();
    insertion_sort(arr, 5);
    clock_t end = clock();
    int i;
    for(i = 0; i < 5; i++)
    {
        printf("%d\n", arr[i]);
    }
    double deltaT = (double)(end - beg)/CLOCKS_PER_SEC;
    printf("Time take is: %lf seconds\n", deltaT); 
}

Итак, затем я компилирую и запускаю свой код. Выход:

1
2
3
4
5
Time take is: 0.000002 seconds

Тогда я решил, что таймер секунд слишком мал, и вместо этого нам нужно использовать миллисекунды. Поэтому я умножаю расчет на тысячу, как:

deltaT = (end - beg) * 1000 / CLOCKS_PER_SEC

, а затем изменил соответствующий printf. Время считывания остается неизменным при 2 мкс. Настоящая магия случается, когда я повторно удаляю 1000 и возвращаю код обратно к старой форме.

На этот раз время чудесным образом меняется на довольно медленные 3 мкс. В чем причина этого резкого изменения. Мы ожидаем, что наши машины будут работать одинаково при одинаковых входах, но почему производительность меняется на одном и том же входе, когда я пробую это?

Answer 1

Расчет, который вы пытаетесь измерить, слишком быстр, чтобы вы могли получить какие-либо значимые измерения времени таким образом.

Попробуйте это:

#include<stdio.h>
#include<time.h>

int main(){
    clock_t beg = clock();
    clock_t end = clock();
    double deltaT = (double)(end - beg)/CLOCKS_PER_SEC;
    printf("Time take is: %lf seconds\n", deltaT); 
}

Тогда вы, вероятно, обнаружите, что вы получаете похожий вывод "Время потрачено", даже если между двумя clock() вызовами ничего не делается. То, что вы видите, является лишь результатом значительных накладных расходов при вызове функции clock().

Чтобы получить значимые измерения производительности вашей функции сортировки, либо сортируйте намного больший список, либо повторяйте сортировку много раз в цикле, чтобы у вас было достаточно времени для измерения.

Чтобы ответить на вопрос о том, почему время менялось, я думаю, что ответ на него заключается в том, что оно изменилось немного случайным образом, запустите еще несколько раз, и вы можете получить другое значение снова.

Answer 2

Подумайте дважды, когда вы пытаетесь измерить время в тактах.Ответ - целое число тактов, которые зависят от архитектуры.Это означает, что иногда вы можете получить один такт (который переводится в микросекунды, может что-то значить), а иногда два (удваивая исходное время).

лучше использовать clock_gettime(2) или gettimeofday(2) (первый имеет разрешение наносекунды, хотя точность может быть ниже, а последняя имеет микросекундное разрешение) В любом случае у вас нет 10000 * или 1.0E9 тиков в секунду.