3

我有一个C程序,它在以下时间内执行以下数量的输入:

23           0.001s            
100          0.001s          

我试图为此找到一个公式,但没有成功。据我所知,时间有时会加倍,有时不会,这就是为什么我找不到这个公式的原因。

有什么想法吗?

笔记

1)我在 CPU 时间(用户+系统)中测量这个。

2)我的程序使用快速排序

2) 我的程序的渐近运行时分析/复杂度是 O(NlogN)

4

2 回答 2

2

绘制这个看起来很像你正在触及“缓存悬崖” - 你的数据足够大,以至于它并不完全适合 cpu 缓存级别,因此必须在更便宜和更昂贵的级别之间交换数据

较低级别的差异可能是由于精度 - 如果您增加计时器块内的循环 - 这可能会平滑

通常,当遇到缓存悬崖时,eprformace 类似于绘制 O*Q

其中 O 是平均运行时间——在你的情况下是 Nlog(N)

Q 是一个阶跃函数,随着您传递每个缓存的分配大小而增加。所以 Q=1 低于 L1 尺寸,10 高于 L1 尺寸,100 高于 L2 尺寸等(仅以数字为例)

事实上,有些人通过绘制 O(1) 函数并寻找性能悬崖峭壁时使用的内存来验证他们的缓存大小:

           ___
 _____-----
  L1 | L2 | L3
于 2013-11-14T20:39:08.930 回答
0

我总是用它来获得精确的运行时间..

#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;

}

于 2014-01-12T08:23:57.227 回答