11

我试图找出一种方法来编写一些代码，该代码可以准确地计算出在 BST 上执行搜索所需的时间。目前我正在使用时间，元素总数为 10^5。它看起来像下面这样：-

clock_t begin, end;
begin = clock();
...
...
...
end = clock();
difference = (end-begin)/CLOCKS_PER_SECOND;

但是，这并没有给我我正在寻找的精度。还有其他我可以使用的 libc 函数吗？

4

6 回答 6

3

如果您的库支持它，C11timespec_get()可以测量到纳秒，具体取决于您的系统时钟分辨率。

于 2013-08-24T12:43:12.347 回答
2

如果您使用 Intel CPU 运行基准测试。也许你可以试试 RDTSC 和 RDTSCP 指令。

这是有关说明的文件

于 2014-06-06T05:31:58.777 回答
2

要对您的算法进行基准测试，您需要进行一些重复以进入至少数百毫秒的范围。（这是标准做法）。要对仅在用户空间中发生的算法（无线程、系统调用等）进行基准测试，您需要使用getrusage(RUSAGE_SELF, &r)包含r.ru_utime秒和微秒的值。

于 2013-08-24T09:57:27.287 回答
0

你所做的与我最近所做的非常相似。

我确实认为该int gettimeofday(struct timeval *tv, struct timezone *tz);功能适合您的需求。时间信息将被放入struct timeval tv，它以秒和微秒为单位获取时间。来自struct timeval手册页：

struct timeval {
               time_t      tv_sec;     /* seconds */
               suseconds_t tv_usec;    /* microseconds */
};

时间测量的简短示例gettimeofday：

struct timeval time;
if(gettimeofday( &time, 0 )) return -1;

long cur_time = 1000000 * time.tv_sec + time.tv_usec;
double sec = cur_time / 1000000.0;

为了方便使用，一个较长的示例已被简化并轻松包装为 c++ 类。代码已放在我的 github 上：https ://github.com/lulyon/LinuxTimeCounter ，用于实际项目。

于 2013-08-24T12:47:13.860 回答
0

QtQElapsedTimer支持高达纳秒的测量。我无法证明它有多准确，IIRC 它在不同平台上使用不同的实现。可悲的是它是 C++，它可能不适合你。还：

在不提供纳秒分辨率的平台上，返回的值将是可用的最佳估计值。

该clock()功能适用​​于粗略测量，但它在毫秒范围内有效。与它的名字相反，我不认为它以 CPU 时钟为单位进行测量，因为现代处理器的时钟频率可能会有很大差异，因此无法仅依靠 CPU 时钟准确地确定实际时间。IMO 这个概念可以追溯到 CPU 频率恒定、没有电源管理、没有“涡轮增压”自动超频或其他任何东西的时代。

编辑：还发现了这个（time.h）：

    int clock_gettime(clockid_t clk_id, struct timespec *tp);

    ... and the target struct...

    struct timespec {
            time_t   tv_sec;        /* seconds */
            long     tv_nsec;       /* nanoseconds */
    };

... and the clock options...


CLOCK_REALTIME
    System-wide realtime clock. Setting this clock requires appropriate privileges. 
CLOCK_MONOTONIC
    Clock that cannot be set and represents monotonic time since some unspecified starting point. 
CLOCK_PROCESS_CPUTIME_ID
    High-resolution per-process timer from the CPU. 
CLOCK_THREAD_CPUTIME_ID
    Thread-specific CPU-time clock.
于 2013-08-24T12:20:25.500 回答
0

英国夏令时？你想要什么样的精度？在 32 位系统上除以 CLOCKS_PER_SECOND 为 10^6 应该得到 6 位精度？

你把结果加倍吗？

尝试

difference = (double)(end-begin)/CLOCKS_PER_SECOND;

请注意，差异应该能够保持双倍。

于 2013-08-24T09:49:08.173 回答