我有一个C程序,它在以下时间内执行以下数量的输入:
23 0.001s
100 0.001s
我试图为此找到一个公式,但没有成功。据我所知,时间有时会加倍,有时不会,这就是为什么我找不到这个公式的原因。
有什么想法吗?
笔记
1)我在 CPU 时间(用户+系统)中测量这个。
2)我的程序使用快速排序
2) 我的程序的渐近运行时分析/复杂度是 O(NlogN)
绘制这个看起来很像你正在触及“缓存悬崖” - 你的数据足够大,以至于它并不完全适合 cpu 缓存级别,因此必须在更便宜和更昂贵的级别之间交换数据
较低级别的差异可能是由于精度 - 如果您增加计时器块内的循环 - 这可能会平滑
通常,当遇到缓存悬崖时,eprformace 类似于绘制 O*Q
其中 O 是平均运行时间——在你的情况下是 Nlog(N)
Q 是一个阶跃函数,随着您传递每个缓存的分配大小而增加。所以 Q=1 低于 L1 尺寸,10 高于 L1 尺寸,100 高于 L2 尺寸等(仅以数字为例)
事实上,有些人通过绘制 O(1) 函数并寻找性能悬崖峭壁时使用的内存来验证他们的缓存大小:
___
_____-----
L1 | L2 | L3
我总是用它来获得精确的运行时间..
#include<stdio.h>
#include <time.h>
#include <stdlib.h>
`clock_t 开始,停止;
`#define START if ( (startm = clock()) == -1) {printf("错误调用时钟");exit(1);}
`#define STOP if ( (stopm = clock()) == -1) {printf("错误调用时钟");exit(1);}
#define PRINTTIME printf( "%6.3f seconds used by the processor.", ((double)stopm-
startm)/CLOCKS_PER_SEC);
`int main() {
诠释 i, x; 开始;
scanf("%d",&x);
for(i=0;i<10000;i++){
printf("%d\n",i);
}
STOP;
PRINTTIME;
}