我必须创建一个排序算法函数,该函数返回比较次数、拷贝数和用于完成排序的 MICROSECONDS 数。
我已经看到,要使用微秒,我必须使用函数 QueryPerformance 计数器,因为它是准确的(注意,我知道它不能在操作系统之间移植)
所以我已经做到了:
void Exchange_sort(int vect[], int dim, int &countconf, int &countcopy, double &time)
{
LARGE_INTEGER a, b, oh, freq;
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&a);
QueryPerformanceCounter(&b);
oh.QuadPart = b.QuadPart - a.QuadPart; //Saves in oh the overhead time (?) accuracy
QueryPerformanceCounter(&a);
int i=0,j=0; // The sorting algorithm starts
for (i=0 ; i<dim-1 ; i++)
{ for(j=i+1 ; j<dim; j++ )
{
countconf++; // +1 Comparisons
if (vect[i]>vect[j])
{
scambio ( vect[i],vect[j] ); // It is a function that swaps 2 integers
countcopy=countcopy+3; // +3 copies
}
}
}
QueryPerformanceCounter(&b); // Ends timer
time = ( ( (double)(b.QuadPart - a.QuadPart - oh.QuadPart) /freq.QuadPart )
*1000000 ) ;
}
*1000000其实就是给微秒...
我认为它应该可以正常工作,但每次我调用函数给它相同的数组维度时,它返回不同的时间...我该如何解决?
非常感谢,抱歉我的编码不好
最佳答案
首先,性能计数器频率可能不是那么好。它通常是几十万或更多,这提供了微秒或几十微秒的分辨率,但您应该意识到它可能更糟。
其次,如果您的数组大小很小,您的排序可能会在纳秒或微秒内完成,您将无法使用 QueryPerformanceCounter
准确测量。
第三,当您的基准测试进程正在运行时,Windows 可能会占用 CPU 一段(相对)较长的时间,几毫秒甚至数百毫秒。这将导致高度不规则且看似不稳定的计时。
我有两个建议,您可以相互独立地追求:
我建议您研究使用
RDTSC
指令(使用内联汇编或编译器内部函数,甚至是现有库。)这很可能会以更少的开销为您提供更好的解决方案。但我必须警告你,它有自己的问题包。对于此类基准测试,您必须使用完全相同的输入多次(数十次或数百次)运行排序例程,然后进行最小时间测量。您应该采用此策略的原因是,有一些现象会干扰您的时间安排并使其更长,但是没有什么可以使您的排序比纸上的更快。所以,你需要跑很多次测试,希望各位大神,你测出的最快时间就是没有干扰,没有噪音的实际运行时间。
更新:通读关于这个问题的评论,您似乎正在尝试使用没有足够分辨率的计时器为一段运行时间非常短的代码计时。要么增加输入大小,要么使用 RDTSC。
关于c++ - 正确的 QueryPerformanceCounter 函数实现/时间每次都改变,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23569661/