【编程珠玑】第九章 代码调优

一，概述

1）代码调优的目的是什么？

减少CPU运行时间；减少分页或增加高速缓存命中率；减少程序所需空间

2）代码调优为什么不能“滥用”？

1>效率的角色：不成熟的优化是大量编程灾害的根源，可能危及程序正确性、功能及可维护性。

2>度量工具：利用性能检测工具，找到“热点”代码，即程序关键区域，然后优化。

3>设计层面：效率问题可以从多个方面进行解决（算法和数据结构、数据结构重组、硬件升级），只有没有更好的解决方案才进行代码优化。

4>双刃剑：有些优化在特定程序中可以提速，但在另外程序中有可能急剧减速。

3）急救方案集锦

1>整数取模(取模运算时间大于加减法执行时间)

k=k%n;

可以替换为

if(k>=n) k=k-n;

2>函数、宏、和内联代码

内联函数和宏具体参见博客http://blog.csdn.net/tianshuai11/article/details/7569659

3>顺序搜索

采用“哨兵” 让循环体不用 每次都判断边界。从而增加了运行速度

将循环展开，替换自增。

a[100]=50;
	
	for(i=0; ; ++i)
	{
		if(a[i] == t)
			break;
	}
  
  	if(i == 100)
  		printf("false\n");
	else
		printf("true\n");

替换为

	a[100]=50;
	for(i=0; ; i+=4)
	{
		if(a[i] == t)
		{
			break;
		}		
		if(a[i+1] == t)
		{
			i+=1;
			break;
		}	
		if(a[i+2] == t)
		{
			i+=2;
			break;
		}	
		if(a[i+3] == t)
		{
			i+=3;
			break;
		}	
		if(a[i+4] == t)
		{
			i+=4;
			break;
		}	
	}
  	if(i == 100)
  		printf("false\n");
	else
		printf("true\n");

4>计算球面距离

4）大手术---二分搜索

#include "stdio.h"
#include<windows.h> 
int main()
{
	int i;
	int t=500;//要查找的数 
	
	int a[1000]; //初始化数组 
	for(i=0;i<1000;++i)
		a[i]=i;
	
	
	a[1000]=50;//哨兵 
	i=512;
	int l=-1;
	if(a[511]<t)
		l=1000 -512;
	while(i!=1)
	{
		i=i/2;
		if(a[l+i] < t)
			l = l+i;
		
	}
  
    int p=l+1;
  	if(p> 1000 || a[p] != t)
  	{
	  	p=-1;
	  	printf("false\n");
    }	
	else
	{
		printf("位置为：%d\n",p);
		printf("true\n");
	}	
 	
} 

二，习题

3）while 语句的开销 大于 if语句

4）宏 不适合用于递归函数中

5）不排序 进行二分查找，如果找到则肯定存在。找不到也不一定 不存在。

6） isdigit(char c) {if(c>='0' && c<='9'}

例子

#include <stdio.h>
#include <ctype.h>
#define in_area(x, a, b) ((x)>=(a) && (x)<=(b))
#define isxdigit(x) (isdigit(x) || in_area(x, 'a', 'f') || in_area(x, 'A', 'F') )

void print( int boolean )
{
    printf( "%s\n", boolean ? "true" : "false" );
}

int main(int argc, char *argv[])
{
    // for testing .... 
    print(isxdigit('0'));
    print(isxdigit('9'));
    print(isxdigit('5'));
    print(isxdigit('A'));
    print(isxdigit('F'));
    print(isxdigit('a'));
    print(isxdigit('f'));
    print(isxdigit('z'));
    print(isxdigit('M'));
    print(isxdigit('L'));
    return 0;
}

7）给定一个非常长的字节序列（假设有十亿或万亿），如何高效的统计1的个数

题意：快速计算整数的二进制表示法中1的个数

分析：转换为二进制然后一个一个求，是不现实的做法。蛮干不是我们想要的结果。

方法一：（算法的时间复杂度就是1的个数）

//& 按位与  只要两个相同位同时为 1 则该位为 1  
//7&5   0111 & 0101 = 0101 (5)
int OneCount(unsigned int x)
{
  int count;
  for(count=0; x>0; count++)
    x&=x-1;//把最后面的1变0
  return count;
}

方法二：

const int idx[256]={0,1,1,……,8}//0~255中含1的个数
int OneCount(unsigned int x)
{
  int count=0;
  for(; x>0; x>>=8)
     count+=idx[x&255];
  return count;
}

8）在程序中如何使用哨兵找出数组中的最大元素

#include "stdio.h"
int main()
{
	int i;
	int max;
	int a[100];
	for(i=0;i<100;++i)
		a[i]=i;
	
	i=0;
	while(i<100)
	{
		max=a[i];
		a[100]=max;
		++i;
		while(a[i]<max)//直到找到比刚才的大的元素 
			i++;
	}
	
	printf("%d\n",max);
	return 0;
}