2

我有一个代码,我想在其中计算两种排序算法合并排序和快速排序以微秒或更精确地对 N 个数字进行排序所花费的时间。这样计算出来的两次,然后我们将输出到终端。代码(部分代码):

printf("THE LIST BEFORE SORTING IS(UNSORTED LIST):\n");
printlist(arr,n);
mergesort(extarr,0,n-1);
printf("THE LIST AFTER SORTING BY MERGE SORT IS(SORTED LIST):\n");
printlist(extarr,n);
quicksort(arr,0,n-1);
printf("THE LIST AFTER SORTING BY QUICK SORT IS(SORTED LIST):\n");
printlist(arr,n);

通过提供如何完成来帮助我。我已经尝试通过将两个变量作为开始停止并将它们分别保持在函数调用的上方和下方来尝试clock_t,但这根本没有帮助,并且总是将其差异打印为零。请建议一些其他方法或功能,记住它在任何类型的操作系统中运行都没有问题。感谢您提前提供任何帮助。

4

5 回答 5

2

方法:1

计算程序花费的总时间您可以使用 linux 实用程序“时间”。

    Lets your program name is test.cpp.
    $g++ -o test test.cpp
    $time ./test

    Output will be like :
    real    0m11.418s
    user    0m0.004s
    sys 0m0.004s

方法:2

您还可以使用 linux 分析方法“gprof”通过不同的函数来查找时间。

首先,您必须使用“-pg”标志编译程序。

    $g++ -pg -o test test.cpp
    $./test
    $gprof test gmon.out

PS:gmon.out 是 gprof 创建的默认文件

于 2015-03-11T07:08:05.623 回答
1

您可以在 Linux 中调用gettimeofday函数,在 Windows 中调用timeGetTime。在调用排序函数之前和调用排序函数之后调用这些函数并获取差异。

请查看手册页以获取更多详细信息。如果您仍然无法获得一些有形数据(由于较小的数据集,所花费的时间可能太小),最好尝试一起测量“n”次迭代的时间,然后推断单次运行的时间或增加要排序的数据集的大小。

于 2012-10-09T01:36:02.567 回答
1

不确定您是否尝试过以下操作。我知道您的原始帖子说您已尝试使用CLOCKS_PER_SEC. 使用CLOCKS_PER_SEC和做(stop-start)/CLOCKS_PER_SEC会让你得到秒。双精度将提供更高的精度。

#include <time.h>

main()
{
clock_t launch = clock();
//do work
clock_t done = clock();
double diff = (done - launch) / CLOCKS_PER_SEC;
}
于 2012-10-09T01:44:16.763 回答
1

得到Zero结果的原因可能是您使用的时间源的分辨率很差。这些时间源通常以大约 10 到 20 ms 递增。这很糟糕,但这就是他们的工作方式。当您的排序完成时间少于此时间增量时,结果将为zero. 您可以通过增加系统中断频率将此结果增加到 1 ms 状态。对于 Windows andLinux,没有标准的方法来实现这一点。他们有自己的方式。通过高频计数器可以获得更高的分辨率。Windows 和 Linux 确实提供了对此类计数器的访问,但同样,代码看起来可能略有不同。

如果您值得one piece of code继续运行windows and linux,我建议您在循环中执行时间测量。运行代码以在循环中测量数百次甚至更多次,并捕获循环外的时间。将捕获的时间除以循环周期数并得到结果。

当然:这仅用于评估。您不想在最终代码中使用它。 并且:考虑到时间分辨率在 1 到 20 毫秒之间,您应该对总时间做出一个很好的选择,以获得良好的测量分辨率。(提示:调整循环计数,让它至少持续一秒钟左右。)

例子:

clock_t start, end;

printf("THE LIST BEFORE SORTING IS(UNSORTED LIST):\n");
printlist(arr,n);

start = clock();
for(int i = 0; i < 100; i++){ 
  mergesort(extarr,0,n-1);
}
end   = clock();
double diff = (end - start) / CLOCKS_PER_SEC;

// and so on...

printf("THE LIST AFTER SORTING BY MERGE SORT IS(SORTED LIST):\n");
printlist(extarr,n);
quicksort(arr,0,n-1);
printf("THE LIST AFTER SORTING BY QUICK SORT IS(SORTED LIST):\n");
printlist(arr,n);
于 2012-10-09T07:13:53.693 回答
0

如果您使用的是 Linux 2.6.26 或更高版本,那么 getrusage(2) 是最准确的方法:

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

// since Linux 2.6.26
// The macro is not defined in all headers, but supported if your Linux version matches
#ifndef RUSAGE_THREAD
#define RUSAGE_THREAD 1
#endif
// If you are single-threaded then RUSAGE_SELF is POSIX compliant 
// http://linux.die.net/man/2/getrusage

struct rusage rusage_start, rusage_stop;

getrusage(RUSAGE_THREAD, &rusage_start);

...

getrusage(RUSAGE_THREAD, &rusage_stop);

// amount of microseconds spent in user space
size_t user_time = ((rusage_stop.ru_utime.tv_sec - rusage_start.ru_stime.tv_sec) * 1000000) + rusage_stop.ru_utime.tv_usec - rusage_start.ru_stime.tv_usec;
// amount of microseconds spent in kernel space
size_t system_time = ((rusage_stop.ru_stime.tv_sec - rusage_start.ru_stime.tv_sec) * 1000000) + rusage_stop.ru_stime.tv_usec - rusage_start.ru_stime.tv_usec;
于 2012-10-09T06:49:43.853 回答