《实用算法》_计算程序运行时间
对算法进行改进以求获得最佳的性能通常有两种策略:优化现有的算法,或者开发新的算法。
优化算法的标准技术:
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上。
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: