《实用算法》_计算程序运行时间

对算法进行改进以求获得最佳的性能通常有两种策略：优化现有的算法，或者开发新的算法。

优化算法的标准技术：

1、使I/O减到最少，减少函数调用的次数，限制计算密集型操作（浮点数运算和除法运算）；

2、确定执行得最频繁的算法元素，比如冒泡排序的比较和交换；

3、检查可能由于疏忽导致而导致特别缓慢的的实现。这往往与查找最坏情况相似。

I/O通常是发生在毫秒(ms)级的时间范围内，而CPU的活动一般发生在亚微秒级的范围内。因此对于算法而言，任何I/O的代价都非常高昂。

如果不能消除I/O本身，那么可以使用缓冲区来减小它的影响。

下面的一个算法，就是用来测试从输入文件流infile向输出文件流outfile传输时，多少大小的缓冲区buf最合适(既可以速度达到最快，也不浪费存储空间)

 

/*--- BUFSIZE.C -------------------------- Listing 1-1 --------
 * Purpose:  Demonstrate use of setvbuf
 * Usage:    bufsize infile outfile [insize [outsize]]
 * Method:   Copies infile to outfile one character at a time,
 *           reporting elapsed time. Infile is set to use a
 *           buffer of insize bytes, while outfile uses an
 *           outsize bytes buffer. Default size is 512 bytes.
 * >> Should be changed per text for UNIX systems <<
 *-----------------------------------------------------------*/

//#include <bios.h>   /* for timer function */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <windows.h>


#undef CopyFile//取消以前定义的CopyFile（下面有重写的CopyFile()）
#pragma comment(lib, "kernel32.lib")//yyw

#define DEF_BUF 512//定义默认的缓冲区大小为512字节

long GetCPUTime() //获取当前时间，精度100微秒
{
	static LARGE_INTEGER li = {0};//LARGE_INTEGER是一个联合体结构
												/*
												typedef   union   _LARGE_INTEGER   {    
														struct   { 
																DWORD   LowPart;    
																LONG     HighPart;    
														}; 
														LONGLONG   QuadPart; 
											}   LARGE_INTEGER; 
												*/                                              
	                                             
	LARGE_INTEGER linow = {0};
	if (li.QuadPart == 0)
		QueryPerformanceFrequency(&li);//获取机器内部计时器的时钟频率，即每秒CPU多少次Performance Tick

	QueryPerformanceCounter(&linow);//这个函数返回高精确度性能计数器的值
	                                                       //（这个值，肯定不会是时间，应该会是系统当前计数器所显示的一个“次数”，
	                                                       //这个次数相对于下一次Counter，就可以计算出两次的时间间隔，是这样的吗？）
	return linow.QuadPart * 10000 / li.QuadPart;//得出系统当前时间，并放大10000倍，精度是100微秒
}


//根据当前的编译器环境来采用不同的库函数获取系统时钟的时间
//如果编译器是TURBO C那么就把获取系统时钟的宏get_clock_ticks(x)定义为x=biostime(0,0L)
//如果不是就定义为x=GetCPUTime()
#ifdef __TURBOC__               /* Borland   */
#define get_clock_ticks(x) x=biostime(0,0L)
#else                           /* Microsoft and Watcom */
#define get_clock_ticks(x) \
	x = GetCPUTime()//yyw
//        _bios_timeofday(_TIME_GETCLOCK, &x)//yyw
#endif


long CopyFile ( char *infilename, char *outfilename,
            size_t insize, size_t outsize )//size_t 是一个与机器相关的unsigned类型，其大小足以保证存储内存中对象的大小。
{
    int  c;
    long starttime, donetime;
    FILE *infile, *outfile;

    /* open input file and setup its buffer */
    if (( infile = fopen ( infilename, "rb" )) == NULL)//打开文件，用infile指向输入文件流
    {
          printf ( "Can't open %s\n", infilename );
          exit ( 1 );
    }

    if ( setvbuf ( infile, NULL, _IOFBF, insize ))//setvbuf的功能就是把缓冲区与流相关。这里的缓冲区和流分别是NULL和infile
		                                                           //第2参数为NULL，是未指定缓冲区的意思？
																   //这个函数应该在打开流后，在对流做任何输入输出前，立即调用
    {
         printf ( "Couldn't set infile buffer to %u bytes.\n",
                   insize );
         exit ( 1 );
    }


    /* open output file and setup its buffer */

    if (( outfile = fopen ( outfilename, "wb" )) == NULL )//打开文件，用outfile指向输出文件流
    {
          printf ( "Can't open %s\n", outfilename );
          exit ( 1 );
    }

    if ( setvbuf ( outfile, NULL, _IOFBF, outsize ))
    {
         printf ( "Couldn't set outfile buffer to %u bytes.\n",
                   outsize );
        exit ( 1 );
    }

    /* do it */
	//开始测试
	//把输入文件转入输出文件，计算所话费的时间
	//完成后关闭输入输出文件流，返回所话费时间
    get_clock_ticks ( starttime );    /* get timer value */
    while (( c = fgetc ( infile )) != EOF )
        fputc ( c, outfile );
    get_clock_ticks ( donetime );
    fclose ( infile );
    fclose ( outfile );

    return ( donetime - starttime );
}


int main ( int argc, char *argv[] )
{
    size_t insize, outsize;
    int    i;
    long   total, average, lo, hi, elapsed;

    insize = outsize = DEF_BUF;

    if ( argc < 3 || argc > 5 )
    {
        fprintf ( stderr,
         "Usage: BUFSIZE infile outfile [insize [outsize]]\n" );
        return ( EXIT_FAILURE );
    }

    /* get buffer sizes */
    if ( argc > 3 )
         insize = (unsigned) atoi ( argv[3] );

    if ( argc > 4 )
         outsize = (unsigned) atoi ( argv[4] );

    /* now, copy the file five times */
    total = hi = 0;
    lo = LONG_MAX;
    for ( i = 1; ; i++ )
    {
        elapsed = CopyFile ( argv[1], argv[2], insize, outsize );//执行拷贝文件的操作，用elapsed存放所耗费时间
        if ( elapsed > hi )
            hi = elapsed;
        if ( elapsed < lo )
            lo = elapsed;
        total += elapsed;
		
		//累计每次所耗时间，得出总的时间
		//一旦总时间超过500ms，或者执行次数达到5次，就停止拷贝
        if ( total > 500 ||   /* Change this value depending   */
                              /*   on how long you can wait    */
                 i > 4 )      /* Do 4 passes, if time limit OK */
            break;
    }

    average = total / i;//计算平均每次拷贝的时间

    printf ( "Average of %4ld ticks (%4ld - %4ld). "
             "Insize = %5u. Outsize = %5u.\n",
             average, lo, hi, insize, outsize );

    return ( EXIT_SUCCESS );
}

 

 

该算法的思路：设置inbuf、outbuf，从infile读取存入outfile5次，记录最长时间、最短时间、平均时间。改变inbuf、outbuf，以试探得出一个比较合适的缓存buf大小。

涉及的一些类型或函数：

LARGE_INTEGER

LARGE_INTEGER是union；用于表示一64位有符号整数值.其他定义如下：    
   
typedef   union   _LARGE_INTEGER   {    
          struct   { 
                  DWORD   LowPart;    
                  LONG     HighPart;    
          }; 
          LONGLONG   QuadPart; 
}   LARGE_INTEGER; 
   
如果你有编译器直接支持64位整数可以直接使用QuadPart（64位）,否则分别对LowPart(32位)和HighPart（32位）存取,HighPart的最高位为符号位。 

QueryPerformanceFrequency()

 

QueryPerformanceFrequency() - 基本介绍
类型：Win32API

原型：BOOL QueryPerformanceFrequency(LARGE_INTEGER *lpFrequency);

作用：返回硬件支持的高精度计数器的频率。QueryPerformanceFrequency()提供了这个频率值,返回每秒嘀哒声的个数.

返回值：非零，硬件支持高精度计数器；零，硬件不支持，读取失败。

QueryPerformanceCounter()

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

在支持64位的编译器上，QueryPerformanceFrequency() 和QueryPerformanceCounter()的返回值都存放在QuadPart上。

 

 

参考链接1

参考链接2

fopen()

函数原型：FILE * fopen(const char * path,const char * mode);

函数功能：打开一个文件

返回值：文件顺利打开后，指向该流的文件指针就会被返回。如果文件打开失败则返回NULL，并把错误代码存在errno 中。

　　一般而言，打开文件后会作一些文件读取或写入的动作，若打开文件失败，接下来的读写动作也无法顺利进行，所以一般在fopen()后作错误判断及处理。例如：

 

    if (( infile = fopen ( infilename, "rb" )) == NULL)//打开文件，用infile指向输入文件流
    {
          printf ( "Can't open %s\n", infilename );
          exit ( 1 );
    }

 

setvbuf()

功能：把缓冲区与流相关

原型： int setvbuf(FILE *stream, char *buf, int type, unsigned size);

参数：stream ：指向流的指针 ；　　buf ： 期望缓冲区的地址；　　type ： 期望缓冲区的类型：　　_IOFBF(满缓冲）：当缓冲区为空时，从流读入数据。或者当缓冲区满时，向流写入数 据。　　_IOLBF(行缓冲）：每次从流中读入一行数据或向流中写入一行数据。　　_IONBF(无缓冲）：直接从流中读入数据或直接向流中写入数据，而没有缓冲区。　　size ： 缓冲区内字节的数量。

这个函数应该在打开流后,在任何对该流做输入输出前,立即调用.

fgetc()

功能：从流中读取字符

格式：int fgetc(FILE *stream);　　

意为从文件指针stream指向的文件中读取一个字符。这个函数的返回值，是返回读取的一个字节。如果       读到文件末尾或者读取出错时返回EOF。

fputc()，与fgetc()相对应

例如：

 

 while (( c = fgetc ( infile )) != EOF )
        fputc ( c, outfile );

  

 

算法实际运行截图：

case1：

 

case2：

 

case3：

case4(正常测试)：

case5：