我不能用time(NULL)函数检查数组排序的时间。

Question

我需要用堆叠算法检查数组排序的时间，我必须在时间至少为1秒时找到数组中的元素数量。为了检查它，我必须使用time.h库中的time()函数。但是，当我计算排序结束和开始排序之间的时间差时，对于有500 000个元素的数组来说，我得到的时间是0秒，我错在哪里？

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

#define TAB_MAX 500000
#define RANDOM_MAX 10

int parent(int i){
    return i/2;
}

int left(int i){
    return 2*i;
}

int right(int i){
    return 2*i+1;
}

void heapify(int t[], int i, int size)
{
    int largest, l, r;
    int tmp;
    l = left(i);
    r = right(i);
    largest = i;
    if ((l <= size) && (t[l] > t[i]))
        largest = l;
    if ((r <= size) && (t[r] > t[largest]))
        largest = r;
    if (largest != i)
    {
        tmp = t[i];
        t[i] = t[largest];
        t[largest] = tmp;
        heapify(t, largest, size);
    }
}

void build_heap(int t[], int size){
    int i;
    for (i=size/2; i>0; i--)
        heapify(t, i, size);
}

void heap_sort(int t[], int size){
    int i, tmp, s;
    build_heap(t, size);
    for (i=size; i>1; i--)
    {
        tmp = t[1];
        t[1] = t[i];
        t[i] = tmp;
        --size;
        heapify(t, 1, size);
    }
}

void print(int T[]){
    int i;
    printf("\n[");
    for (i=0; i<TAB_MAX; i++)
        printf("%d ", T[i]);
    printf("]\n\n");
}

void tab_random(int T[]){
    int i;
    for (i=0; i<TAB_MAX; i++)
        T[i] = rand()%RANDOM_MAX;
}

int main()
{
    srand(time(NULL));
    int tab[TAB_MAX];
    tab_random(tab);
    //print(tab);

    int startTime = time(0);
    heap_sort(tab, TAB_MAX-1);
    int endtime = time(0);
    int diff = endtime - startTime;

    printf("Time of sorting: %ds", diff); // <- 0 sec.

    //print(tab);
    return 0;
}

Answer 1

所以数组排序的时间小于1秒。

建议调用time()函数。clock() 因为这将导致CPU周期的统计。

Answer 2

这里有一个适用于windows和linux的函数。

#ifdef WIN32
    time_t getmsec()
    {
        timeb tb;
        ftime( &tb );
        time_t nCount = tb.millitm + (tb.time & 0xfffff) * 1000;
        return nCount;
    }
#else
    time_t getmsec()
    {
        struct timeval te; 
        gettimeofday(&te, NULL); // get current time
        long long milliseconds = te.tv_sec*1000LL + te.tv_usec/1000; // calculate milliseconds
        return (time_t)milliseconds;
    }
#endif

Answer 3

除了时间上的问题，代码也是破绽百出。

注意到这段代码从未使用过 t[0].

for (i=size; i>1; i--)
{
    tmp = t[1];
    t[1] = t[i];
    t[i] = tmp;
    --size;
    heapify(t, 1, size);
}