Почему функция clock () иногда не точна, когда истекшее время очень мало? - PullRequest
Новая
       19

Почему функция clock () иногда не точна, когда истекшее время очень мало?

0 голосов
/ 27 мая 2019

Я тестировал два простых алгоритма сортировки: выбор и вставка.Я использую функцию clock (), чтобы измерить, сколько времени использует каждая функция.Однако есть интересное явление: когда размер случайного массива равен 1000, время выполнения иногда будет составлять 0,0000 с.Когда размер увеличился до 10000, все вернулось к норме. 

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>
#include <time.h>
#include <string.h>
#include <sys/types.h>

static inline void swap(int *restrict const a, int *restrict const b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

static void selection(int *restrict const array, size_t size) {
    for (size_t i = 0; i < size; i++) {
        int min_index = i;
        for (size_t j = i+1; j < size; j++) {
            if (array[j] < array[min_index]) {
                min_index = j;
            }
        }
        swap(&array[min_index], &array[i]);
    }
}

static void insertion(int *restrict const array, size_t size) {
    for (size_t i = 1; i < size; i++) {
        for (size_t j = i; j > 0; j--) {
            if (array[j] < array[j-1]) {
                swap(&array[j], &array[j-1]);
            } else {
                break;
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    int rand_array1[10000];
    int rand_array2[10000];
    srand(time(NULL));
    for (size_t i = 0; i < 10000; i++) {
        rand_array1[i] = rand();
    }
    memcpy(rand_array2, rand_array1, sizeof(rand_array1));
    clock_t start = clock();
    insertion(rand_array1, 10000);
    clock_t stop = clock();
    printf("Insertion use %lf sec.\n", (double)(stop - start) / CLOCKS_PER_SEC);
    start = clock();
    selection(rand_array2, 10000);
    stop = clock();
    printf("Selection use %lf sec.\n", (double)(stop - start) / CLOCKS_PER_SEC);
        return 0;
}

Вывод (размер массива 1000): 

[william@Notebook Sort]$ ./a.out 
Insertion use 0.002276 sec.
Selection use 0.006772 sec.

[william@Notebook Sort]$ ./a.out 
Insertion use 0.001282 sec.
Selection use 0.000000 sec.

Вывод (размер массива 10000): 

[william@Notebook Sort]$ ./a.out 
Insertion use 0.153155 sec.
Selection use 0.102534 sec.

[william@Notebook Sort]$ ./a.out 
Insertion use 0.161796 sec.
Selection use 0.141816 sec.
...