c - 为什么当经过的时间很短时，clock() 函数有时不准确？

Question

我正在对两个简单的排序算法进行基准测试：选择和插入排序。我使用 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.

标签： ctimeclock