5

我的程序将在时间和空间上相互竞争不同的排序算法。我已经占满了空间,但是测量时间给我带来了一些麻烦。这是运行排序的代码:

void test(short* n, short len) {
  short i, j, a[1024];

  for(i=0; i<2; i++) {         // Loop over each sort algo
    memused = 0;               // Initialize memory marker
    for(j=0; j<len; j++)       // Copy scrambled list into fresh array
      a[j] = n[j];             // (Sorting algos are in-place)
                               // ***Point A***
    switch(i) {                // Pick sorting algo
    case 0:
      selectionSort(a, len);
    case 1:
      quicksort(a, len);
    }
                               // ***Point B***    
    spc[i][len] = memused;     // Record how much mem was used
  }
}

(为简单起见,我删除了一些排序算法)

现在,我需要测量排序算法需要多少时间。最明显的方法是记录 (a) 点的时间,然后从 (b) 点的时间中减去该时间。但是没有一个 C 时间函数足够好:

time()以秒为单位给我时间,但算法比这更快,所以我需要更准确的东西。

自程序启动以来, clock()给了我 CPU 滴答声,但似乎四舍五入到最接近的 10,000;还不够小

time shell 命令运行良好,除了我需要为每个算法运行超过 1,000 次测试,而且我需要为每个算法设置单独的时间。

我不知道getrusage()返回什么,但它也太长了。

我需要的是时间单位(如果可能的话,显着)小于排序函数的运行时间:大约 2 毫秒。所以我的问题是:我在哪里可以得到它?

4

4 回答 4

13

gettimeofday()具有微秒级分辨率,易于使用。

一对有用的定时器函数是:

static struct timeval tm1;

static inline void start()
{
    gettimeofday(&tm1, NULL);
}

static inline void stop()
{
    struct timeval tm2;
    gettimeofday(&tm2, NULL);

    unsigned long long t = 1000 * (tm2.tv_sec - tm1.tv_sec) + (tm2.tv_usec - tm1.tv_usec) / 1000;
    printf("%llu ms\n", t);
}
于 2013-05-26T22:29:31.533 回答
10

要测量时间,请使用clock_gettimewith CLOCK_MONOTONIC(或CLOCK_MONOTONIC_RAW如果可用)。尽可能避免使用gettimeofday. 它特别不赞成使用clock_gettime,并且从它返回的时间会受到时间服务器的调整,这可能会影响您的测量。

于 2013-05-26T23:13:02.930 回答
3

您可以使用以下方法获得总用户 + 内核时间(或仅选择一个)getrusage

#include <sys/time.h>
#include <sys/resource.h>

double get_process_time() {
    struct rusage usage;
    if( 0 == getrusage(RUSAGE_SELF, &usage) ) {
        return (double)(usage.ru_utime.tv_sec + usage.ru_stime.tv_sec) +
               (double)(usage.ru_utime.tv_usec + usage.ru_stime.tv_usec) / 1.0e6;
    }
    return 0;
}

我选择创建一个double包含小数秒的...

double t_begin, t_end;

t_begin = get_process_time();
// Do some operation...
t_end = get_process_time();

printf( "Elapsed time: %.6f seconds\n", t_end - t_begin );
于 2013-05-26T22:40:16.493 回答
2

时间戳计数器在这里可能会有所帮助:

static unsigned long long rdtsctime() {
    unsigned int eax, edx;
    unsigned long long val;
    __asm__ __volatile__("rdtsc":"=a"(eax), "=d"(edx));
    val = edx;
    val = val << 32;
    val += eax;
    return val;
}

尽管对此有一些警告。不同处理器内核的时间戳可能不同,并且更改时钟速度(由于省电功能等)可能会导致错误结果。

于 2013-05-26T22:32:23.233 回答