编程宝库 - 技术改变世界

编程宝库

Search

C语言编程技术

C语言深入探究冒泡排序与堆排序使用案例讲解

C语言深入探究直接插入排序与希尔排序使用案例讲解

C++算法计时器的实现示例

有时为了检测和比较算法效率和复杂度，需要一个计时器，而这个计时器往往需要精确到毫秒ms、微秒μs甚至纳秒ns，不太常用的库或api就不放上来了。

1.毫秒级精度

1.1 CLOCKS_PER_SEC

在头文件time.h或ctime中，clock()函数返回从“开启这个程序进程”到“程序中调用clock()函数”时之间的CPU时钟计时单元（clock tick）数，在MSDN中称之为挂钟时间（wal-clock），常量CLOCKS_PER_SEC，它用来表示一秒钟会有多少个时钟计时单元，精确到毫秒，其使用方法如下:

精华代码：

#include <iostream>
#include<vector>
#include <algorithm>
#include <ctime>
using namespace std;
int main()
{
  
  clock_t begin, end;
  begin = clock();
  for (int i = 1; i <= 100; ++i)
  {
     
  }
  end = clock();
  cout << "100次循环所用时间：" << double(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
     
  return 0;
}

示例为检测二叉堆不同输入一个一个插入所用时间（不能直接跑）：

#include <iostream>
#include<vector>
#include <algorithm>
#include <ctime>
using namespace std;

int main()
{
  int num, mode;
  cout << "输入大小和模式，其中模式1为正序，2为倒序，3位随机" << endl;
  cout << "示例：1000 2" << endl;
  cin >> num >> mode;//输入大小和模式，其中模式1为正序，2为倒序，3位随机
  BinaryHeap<int> heap1,heap2;
  clock_t begin, end;
  switch (mode)
  {
  case 1://正序
      begin = clock();
      for (int i = 1; i <= num; ++i)
      {
          heap1.insert(i);
      }
      end = clock();
      cout << "一个一个正序插入所用时间：" << double(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
      break;
  case 2://倒序
      begin = clock();
      for (int i = num; i >= 1; --i)
      {
          heap1.insert(i);
      }
      end = clock();
      cout << "一个一个倒序插入所用时间：" << double(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
      break;
  case 3://正倒序交叉模拟随机
      begin = clock();
      for (int i = 1; i<num/2; ++i)
      {
          heap1.insert(i);
          heap1.insert(num - i);
      }
      end = clock();
      cout << "一个一个随机插入所用时间：" << double(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
      break;
  default:
      break;
  }


  return 0;
}

1.2 GetTickCount()函数（Windows API）

GetTickCount返回（retrieve）从操作系统启动所经过（elapsed）的毫秒数，它的返回值是DWORD。

#include <stdio.h>
#include <windows.h>
#include<iostream>
#pragma comment(lib, "winmm.lib") //告诉编译器要导入winmm库，有时候可删

int main()
{
  DWORD t1, t2;
  t1 = GetTickCount();
  for(int i=1;i<=10000;++i)
  {
      
  }//do something
  t2 = GetTickCount();
  //printf("Use Time:%f\n", (t2 - t1) * 1.0);
  cout<<"Use Time:"<<(double)(t2-t1)<<"ms"<<endl;
  return 0;
}

1.3 timeGetTime()函数（Windows API）

以毫秒计的系统时间，该时间为从系统开启算起所经过的时间。在使用timeGetTime之前应先包含头文件＃include <Mmsystem.h>或＃include <Windows.h>并在project->settings->link->Object/library modules中添加winmm.lib。也可以在文件头部添加 #pragma comment( lib,"winmm.lib" )。

备注：命令行：#pragma comment( lib,"xxx.lib" )时预编译处理指令，让vc将winmm.lib添加到工程中去进行编译。

//#include<stdio.h>
#include<windows.h>
#include<iostream>
#pragma comment( lib,"winmm.lib" )

int main()
{
  DWORD t1, t2;
  t1 = timeGetTime();
  foo();//do something
  t2 = timeGetTime();
  //printf("Use Time:%f\n", (t2 - t1)*1.0 / 1000);
  cout<<"Use Time:"<<(double)(t2-t1)<<"ms"<<endl;
  return 0;
}

该函数的时间精度是五毫秒或更大一些，这取决于机器的性能。可用timeBeginPeriod和timeEndPeriod函数提高timeGetTime函数的精度。如果使用了，连续调用timeGetTime函数，一系列返回值的差异由timeBeginPeriod和timeEndPeriod决定。也可以用timeGetTime实现延时功能Delay

void Delay(DWORD delayTime)
{
　　DWORD delayTimeBegin;
　　DWORD delayTimeEnd;
　　delayTimeBegin=timeGetTime();
　　do
　　{　　　　
　　	delayTimeEnd=timeGetTime();
　　}while((delayTimeEnd-delayTimeBegin)<delayTime)
}

1.4 timeval结构体（Linux）

timeval结构体

#include <sys/time.h> 
#include <iostream> 
#include <time.h> 
double get_wall_time() 
{ 
struct timeval time ; 
if (gettimeofday(&time,NULL)){ 
  return 0; 
} 
return (double)time.tv_sec + (double)time.tv_usec * .000001; 
} 

int main() 
{ 
unsigned int t = 0; 
double start_time = get_wall_time() 
while(t++<10e+6); 
double end_time = get_wall_time() 
std::cout<<"循环耗时为:"<<end_time-start_time<<"ms"; 
return 0; 
}

2.微秒级精度

QueryPerformanceCounter()函数和QueryPerformanceFrequency()函数（Windows API）

QueryPerformanceFrequency()函数返回高精确度性能计数器的值,它可以以微妙为单位计时，但是QueryPerformanceCounter()确切的精确计时的最小单位是与系统有关的,所以,必须要查询系统以得到QueryPerformanceCounter()返回的嘀哒声的频率。QueryPerformanceFrequency()提供了这个频率值,返回每秒嘀哒声的个数。

//#include<stdio.h>
#include<iostream>
#include<windows.h>
#pragma comment( lib,"winmm.lib" )

int main()
{
  LARGE_INTEGER t1, t2, tc;
  QueryPerformanceFrequency(&tc);
  QueryPerformanceCounter(&t1);
  foo();//do something
  QueryPerformanceCounter(&t2);
  //printf("Use Time:%f\n", (t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart);
  cout << "Use Time:" << (double)((t2.QuadPart - t1.QuadPart) * 1000000.0 / tc.QuadPart) << "μs" << endl;
  return 0;
}

封装好的易于调用的代码：

//MyTimer.h// 
#ifndef __MyTimer_H__  
#define __MyTimer_H__  
#include <windows.h>  

class MyTimer 
{ 
private: 
int _freq; 
LARGE_INTEGER _begin; 
LARGE_INTEGER _end; 

public: 
long costTime;      // 花费的时间(精确到微秒)  

public: 
MyTimer() 
{ 
  LARGE_INTEGER tmp; 
  QueryPerformanceFrequency(&tmp);//QueryPerformanceFrequency()作用：返回硬件支持的高精度计数器的频率。  

  _freq = tmp.QuadPart; 
  costTime = 0; 
} 

void Start()      // 开始计时  
{ 
  QueryPerformanceCounter(&_begin);//获得初始值  
} 

void End()        // 结束计时  
{ 
  QueryPerformanceCounter(&_end);//获得终止值  
  costTime = (long)((_end.QuadPart - _begin.QuadPart) * 1000000 / _freq); 
} 

void Reset()      // 计时清0  
{ 
  costTime = 0; 
} 
}; 
#endif  

//main.cpp 
#include "MyTimer.h" 
#include <iostream> 


int main() 
{ 
MyTimer timer; 
unsigned int t = 0;  
timer.Start(); 
while (t++ < 10e+5); 
timer.End();  
std::cout << "耗时为：" << timer.costTime << "us"; 
return 0 ; 
}

3.纳秒级精度

要先获取CPU频率。

在Intel Pentium以上级别的CPU中，有一个称为“时间戳（Time Stamp）”的部件，它以64位无符号整型数的格式，记录了自CPU上电以来所经过的时钟周期数。由于目前的CPU主频都非常高，因此这个部件可以达到纳秒级的计时精度。这个精确性是上述几种方法所无法比拟的.在Pentium以上的CPU中，提供了一条机器指令RDTSC（Read Time Stamp Counter）来读取这个时间戳的数字，并将其保存在EDX:EAX寄存器对中。由于EDX:EAX寄存器对恰好是Win32平台下C++语言保存函数返回值的寄存器，所以我们可以把这条指令看成是一个普通的函数调用，因为RDTSC不被C++的内嵌汇编器直接支持，所以我们要用_emit伪指令直接嵌入该指令的机器码形式0X0F、0X31。

inline unsigned __int64 GetCycleCount()
{
  __asm
  {
      _emit 0x0F;
      _emit 0x31;
  }
}

void test()
{
  unsigned long t1,t2;
  t1 = (unsigned long)GetCycleCount();
  foo();//dosomething
  t2 = (unsigned long)GetCycleCount();
  printf("Use Time:%f\n",(t2 - t1)*1.0/FREQUENCY);   //FREQUENCY指CPU的频率
}

下面为获取CPU精度的代码

#include<Windows.h>
LONGLONG GetFrequency(DWORD sleepTime) //获取CPU主频

{

  DWORD low1 = 0, high1 = 0, low2 = 0, high2 = 0;

  LARGE_INTEGER fq, st, ed;

  /*在定时前应该先调用QueryPerformanceFrequency()函数获得机器内部计时器的时钟频率。接着在

需要严格计时的事件发生前和发生之后分别调用QueryPerformanceCounter()，利用两次获得的技术

之差和时钟的频率，就可以计算出时间经历的精确时间。*/

  ::QueryPerformanceFrequency(&fq); //精确计时（返回硬件支持的高精度计数器的频率）

  ::QueryPerformanceCounter(&st); //获得起始时间

  __asm { //获得当前CPU的时间数

rdtsc

mov low1, eax

mov high1, edx

  }

  ::Sleep(sleepTime); //将线程挂起片刻

  ::QueryPerformanceCounter(&ed); //获得结束时间

  __asm {
rdtsc //读取CPU的时间戳计数器

mov low2, eax

mov high2, edx

  }

  //将CPU得时间周期数转化成64位整数

  LONGLONG begin = (LONGLONG)high1 << 32 | low1;

  LONGLONG end = (LONGLONG)high2 << 32 | low2;

  //将两次获得的CPU时间周期数除以间隔时间，即得到CPU的频率

  //由于windows的Sleep函数有大约15毫秒的误差，故以windows的精确计时为准

  return (end - begin) * fq.QuadPart / (ed.QuadPart - st.QuadPart);
}

4.利用chrono的各精度集成版（本质微秒）

4.1 chrono库介绍

函数原型：

template <class Clock, class Duration = typename Clock::duration>
class time_point;

std::chrono::time_point 表示一个具体时间

第一个模板参数Clock用来指定所要使用的时钟,在标准库中有三种时钟，分别为：

system_clock：当前系统范围(即对各进程都一致)的一个实时的日历时钟(wallclock)
steady_clock：当前系统实现的一个维定时钟，该时钟的每个时间嘀嗒单位是均匀的(即长度相等)。
high_resolution_clock：当前系统实现的一个高分辨率时钟。

第二个模板函数参数用来表示时间的计量单位(特化的std::chrono::duration<> )

时间点都有一个时间戳，即时间原点。chrono库中采用的是Unix的时间戳1970年1月1日 00:00。所以time_point也就是距离时间戳(epoch)的时间长度（duration）。

4.2 代码示例

#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

class TimerClock
{
public:
TimerClock()
{
update();
}

~TimerClock()
{
}

void update()
{
_start = high_resolution_clock::now();
}
//获取秒
double getTimerSecond()
{
return getTimerMicroSec() * 0.000001;
}
//获取毫秒
double getTimerMilliSec()
{
return getTimerMicroSec()*0.001;
}
//获取微妙
long long getTimerMicroSec()
{
//当前时钟减去开始时钟的count
return duration_cast<microseconds>(high_resolution_clock::now() - _start).count();
}
private:
time_point<high_resolution_clock>_start;
};

//测试的主函数
int main()
{
TimerClock TC;
int sum = 0;
TC.update();
for (int i = 0; i > 100000; i++)
{
sum++;
}
cout << "cost time:" << TC.getTimerMilliSec() <<"ms"<< endl;
cout << "cost time:" << TC.getTimerMicroSec() << "us" << endl;

return 0;
}

5.秒级精度

单纯以备不时之需，没人用吧。

time() 函数

在头文件time.h中，time()获取当前的系统时间，只能精确到秒，返回的结果是一个time_t类型，其使用方法如下：

#include <time.h>   
#include <stdio.h>   

int main()
{  
   time_t first, second;  
   first=time(NULL);  
   delay(2000);  
   second=time(NULL);  
   printf("The difference is: %f seconds",difftime(second,first));  //调用difftime求出时间差
   return 0;   
}

关于C++算法计时器的实现示例的文章就介绍至此，更多相关C++算法计时器内容请搜索编程宝库以前的文章，希望以后支持编程宝库！

下一节：C语言深入探究直接插入排序与希尔排序使用案例讲解

C语言编程技术

一.直接插入排序1.1直接插入排序引入排序是我们生活中经常会面对的问题，以打扑克牌为例，你摸的手牌肯定是杂乱的，你一定会将小牌移动到大牌的左面，大牌移动到小牌的右面，这样顺序就算 ...

C语言深入探究冒泡排序与堆排序使用案例讲解

C语言深入探究直接插入排序与希尔排序使用案例讲解

编程宝库 - 技术改变世界

C++算法计时器的实现示例

1.毫秒级精度

1.1 CLOCKS_PER_SEC

1.2 GetTickCount()函数 （Windows API）

1.3 timeGetTime()函数（Windows API）

1.4 timeval结构体（Linux）

2.微秒级精度

QueryPerformanceCounter()函数和QueryPerformanceFrequency()函数（Windows API）

3.纳秒级精度

4.利用chrono的各精度集成版（本质微秒）

4.1 chrono库介绍

4.2 代码示例

5.秒级精度

time() 函数

下一节：C语言深入探究直接插入排序与希尔排序使用案例讲解

C语言编程技术

1.2 GetTickCount()函数（Windows API）