【编程珠玑】鸟瞰 --- 编程珠玑 （2012.8.7）

序：刘翔今天再一次倒在起跑线上，我作为翔子的Fans，盯着屏幕看刘翔起跑，当他第一个栏摔倒时，我的心碎了，情绪异常低落，久久难以平复。然后给老爸发短信抱怨：刘翔退赛了，为什么又是因伤退赛？我难受。老爸轻描淡写：没办法，这就是竞技体育，有起有落才是人生。

希望刘翔身体无大碍，早日康复。翔子：咱是纯爷们，这届不行，咱再来一届。

*****************************************************************************************************************

第一章：开篇

磁盘文件排序问题：

1MB内存，磁盘中有一千万个整数（每个数都小于1千万）。如何排序输出？

解答：1）位图法：每一位代表一个数，则1千万/(1024*1024*8) 约为1.25MB内存空间。所以如果内存可以容易扩展时候，考虑采用这种方法。（1MB总共有838，8608个比特位）

2）时间换空间：两次遍历或者除去第一位为0或1的整数。

解释：考虑到没有以数字0或1开头的电话号码，可以省略对这些数的操作。

两次遍历：对 1 ---4999 999之间的数排序，需要存储空间为：5000 000/8 =625 000 字节（8为一个字节中的位数）

对 5000 000 -10000 000 之间的数排序。

如果需要采用k趟算法，方法类似。

位图表示，采用整形数。总体相当于一个二维数组，每一个整形代表32位，即代表一行。总共有32列。

列可以通过i >> shift 取得，这个其实就是把i除以32，也就是2^5。目的是找出i应该数组中的哪个行位置；

行是一个32位的Bit，需要将对应的位置0或1，需要将对应的位置0或1，需要i<<(i&mask):保留数值i的低五位，这五位则标示在某个元素中处于哪个位置。i & mask首先算出应该向左移动的位数，然后把1向左移动这么多位，剩下的就是和数组中的那个元素或者与运算，或者或运算了。

a[i/32] |= (1<<(i%32)); 说明0-31都存放在第一个数组中。

clr是将对应的位清零，test是判断对应的位置的数是否在集合中存在的。a[i/32] &= ~(1<<(i%32));

判断是否存在

return a[i/32] &(1<<(i%32));

快速搜索要用到索引

顺序搜索解决冲突的“开放定址法”

存放的数，位数较多时候，采用最后几位或者某几位作为 Hash表的索引，然后其内存放以该几位数为结尾的剩余位数。

查找时候，先通过Hash快速找到索引，然后再顺序搜索索引内的数。

第二章 二分查找

1.给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。

在内存足够的情况下，可以用位图来解决这个问题，位图中标记为0对应的数就是所要找的。

当内存不足时，此时采用分治的思想：

按最高位（也可按低位）的值对所有整数分类，高位为0的一组，记为A，高位为1的一组，记为B，分别统计A，B组元素的个数。此时若len（A）<2^31，则A组中必有漏掉的数（此时缺失的数高位一定为0）；同理可判断B中是否有遗漏。选择一个有遗漏的分组，再对它的次高位进行分类，

一直递归下去直到对最低位也进行了分类。此时缺失的数每一位的值均可以确定，找出了这个数。

2.将一个n元一维向量旋转i个位置。

书中给出了两个算法：

（1）杂技法。该方法很巧妙，但不太容易理解，不知道算法的作者是怎么想出来的。

（2）分块求逆。这个算法很好用，通过分别求逆后再求逆来得到最终的结果。

比如要将n元向量旋转i位，过程为：

reverse（0，i-1）

reverse（i，n-1）

reverse（0，n-1）

我的思路：可以用空间换时间的思想来解决。比如要旋转的n元向量为abcdefgh，要将它旋转3位：defghabc我们可以开辟一块新空间来再存储一份n元向量，将它们拼接，为abcdefghabcdefgh，则所要求的旋转结果为这个字符串的子串，取s[3:len(n)+3)即为所求

3.给定一个英文字典，找出变位词的集合。

解决思路就是对每一个单词进行标记，使得互为变位词的单词有相同的标记，而不是变位词的单词有不同的标记。

这里列出几种可用的标记方法：

（1）对每个单词进行字典序排序，则互为变位词的单词有着相同的排序（若单词量大，对每个单词排序比较耗时）

（2）将26个英文字母分别对应一个素数，则一个单词的标记为组成它的每个字母的素数乘积。这样保证了变位词的标记时一样的，而非变位词有不同的标记。但当一个单词长度比较长时，计算一个乘积结果，数据量也比较大。

（3）统计一个单词中各字母出现的次数，并以此作为标记索引。如mississippi对应i4m1p2s4，可以将1省略，为i4mp2s4.

习题：

1.没有时间进行预处理，则直接按该单词的标识值去查字典，标识相同的单词输出

如有时间和空间进行预处理，可以先对整个字典进行标识计算，将计算值作为索引hash到不同的数组中，并将标识相同的单词（变位词）链在同一个链表中。

查找时按给定的单词去查索引表（第一个节点即为链表表头节点），然后一次取出变位词输出。

7，一种处理数据的方法：先对数据进行添加标识处理，然后根据标识处理数据。

对磁带上顺序存储的数据添加行号和列号，然后先根据列号排序，然后再根据行号排序则得到矩阵的转换。

第三章 数据决定程序结构

强调数据结构的重要性，数据的表示形式是程序设计的根本。主要是寻找通用公式，用合理的数据结构表示并求解。

第四章 编写正确的程序

主要提醒我们：要对程序可能发生的事情，做好准备。如果不能考虑周到，要再继续编程之前，做好断言Assert()；方便调试代码。

求两个数平均值，int mid = min+(max-min)/2; //防止溢出

第五章 编程小事

使用断言函数：#include <assert.h>

在程序中 assert(你要断言判断的部分); //如果该断言部分为false 则程序报错提示

第六章 程序性能分析

如果要提高软件的性能，需要从下面几个方面入手：

1、算法与数据结构

2、算法调优

3、数据结构重组

4、与系统无关的代码的调优（float取代double）。

5、与系统相关的调优，把经常使用的函数进行加速，比如关键代码使用汇编代替高级语言

6、硬件上使用浮点加速器。

第七章 粗略估算

测试时间时候，要关闭自动优化功能，否则，优化会删除计时循环，使运行时间始终为0。

1）72法则：单位时间增长率 * 时间 =72 则该时间完成初始值翻番

题目：假设最初投资金额为100元，复息年利率9%，实现资金翻番需要多久？

利用“72法则”，将72除以9（增长率），得8，即需约8年时间，投资金额滚存至200元（翻番），而准确需时为8.0432年。

题目：盘子中的菌每小时增长3%，那么其数量多久会翻番？

24小时（3 * 24 =72）

2）pi(π)秒就是一个纳世纪 10E-7 年；

3）little定律：系统中物体的平均数量等于物体离开系统的平均数率和每个物体在系统中停留的平均时间的乘积。

性能分析法则：总开销等于每个单元的开销乘以单元的个数。

例子：如果一个群体的平均寿命为75岁，则这个群体的死亡率为多少？

1/75 =1.3%

二，习题

4）时间变慢，所有都变慢为原来1/10，那么你估计一下打出自己的名字需要多久？

时钟如果变慢，则打出名字的时间不会变。

6）1998年世界人口为59亿，年增长率为1.33%。如果这样下去，到2050年会有多少人口？

利用72法则，72/1.33 = 54 接近52年。所以人口将翻番（计划生育则会控制增长）

第八章 算法设计技术

优化算法的策略

1）保存已经计算的状态，避免重复计算。

2）将信息预处理到数据结构中。例如算法二

3）分治算法，采取更高级的算法

4）扫描算法，巧妙

5）下界：证明某个匹配的下界，确定最优算法

第九章 代码调优

调优方案：

1> 整数取模替换为减法

2> 内联函数和宏替换经常使用的代码，递归函数不要使用宏

3> 顺序搜索采用哨兵，循环展开

第十章 节省空间

1）节省空间带来的副作用（好处）程序变小使得加载更快，更容易读入告诉缓存，需要操作的数据更少从而减少操作时间。

2）节省空间的方法

数学函数式替代要存储的数据。简单例子为：a[i]=i 。如果你要读取数组第i个元素只需要通过函数f(i) = i得到元素值，而不需要将所有数据存储在数组中。

改变数据结构。如果一个数字范围为0-200，则完全没有必要采用32位的int型存储，只需要采用8位的无符号char型存储即可。

链表替代稀疏二维数组。虽然指针也需要空间存储，如果二维数组存储很少的数据，则可以考虑权衡一下是否要用链表代替稀疏二维数组。（数组表示列，链表表示行的方式。而不是单链表）

3）减少程序所需数据的存储空间的技术

1> 不存储结果，用到时计算判断。

2> 稀疏数据结构。使用指针共享大型对象，消除存储同一对象的众多副本的开销

3> 数据压缩。用8位的char替代 32位的int 。利用函数将两个十进制数，放到一个字节里。加密：c= 10 * a + b; 解密：a= c / 10 ; b= c % 10;

注意 / 和 %运算符开销较大，即运行时占用内存较多。如果采用这种方法，相当于用较小的内存来换取存储字节的磁盘存储空间。

4> 分配策略。动态分配替代静态分配。即只有在需要的时候才分配空间。

5> 垃圾回收。

第十一章 排序

库函数使用：

一、对int类型数组排序

 int num[100];
         int cmp ( const void *a , const void *b )
        {
             return *(int *)a - *(int *)b;
        }
         qsort(num,100,sizeof(num[0]),cmp);

二、对char类型数组排序（同int类型）

char word[100];
int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}
qsort(word,100,sizeof(word[0]),cmp);

三、对double类型数组排序（特别要注意）

double in[100];
int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}
qsort(in,100,sizeof(in[0]),cmp)；

四、对结构体一级排序

struct In
{
   double data;
   int other;
}s[100]
//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，参考上面的例子写
int cmp( const void *a ,const void *b)
{
   return (*(In *)a).data > (*(In *)b).data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp);

五、对结构体二级排序

struct In
{
   int x;
   int y;
}s[100];
//按照x从小到大排序，当x相等时按照y从大到小排序
int cmp( const void *a , const void *b )
{
   struct In *c = (In *)a;
   struct In *d = (In *)b;
   if(c->x != d->x)
        return c->x - d->x;
   else
       return d->y - c->y;
}
qsort(s,100,sizeof(s[0]),cmp);

六、对字符串进行排序

struct In
{
   int data;
   char str[100];
}s[100];
//按照结构体中字符串str的字典顺序排序
int cmp ( const void *a , const void *b )
{
    return strcmp( (*(In *)a)->str , (*(In *)b)->str );
}
qsort(s,100,sizeof(s[0]),cmp);

七、计算几何中求凸包的cmp

int cmp(const void *a,const void *b) //重点cmp函数，把除了1点外的所有点，旋转角度排序
{
   struct point *c=(point *)a;
   struct point *d=(point *)b;
   if( calc(*c,*d,p[1]) < 0) return 1;
   else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y)) //如果在一条直线上，则把远的放在前面
        return 1;
   else return -1;
}

PS:

其中的qsort函数包含在<stdlib.h>的头文件里，strcmp包含在<string.h>的头文件里

STL sort()

vector < int > vect;

//...

sort(vect.begin(), vect.end());

//此时相当于调用

sort(vect.begin(), vect.end(), less<int>() );

上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数，以下是仿函数列表:

名称	功能描述
equal_to	相等
not_equal_to	不相等
less	小于
greater	大于
less_equal	小于等于
greater_equal	大于等于

需要注意的是，这些函数不是都能适用于你的sort算法，如何选择，决定于你的应用。另外，不能直接写入仿函数的名字，而是要写其重载的()函数：

less<int>()

greater<int>()

排序库函数总结：

如果你以前有用过C语言中的qsort, 想知道qsort和他们的比较，那我告诉你，qsort和sort是一样的，因为他们采用的都是快速排序。从效率上看，以下几种sort算法的是一个排序，效率由高到低（耗时由小变大）：

partion

stable_partition //以某元素为轴，将整个集合分成两部分

nth_element //找到第n个数

partial_sort //选取top n

sort

stable_sort

若需对vector, string, deque, 或 array容器进行全排序，你可选择sort或stable_sort；

若只需对vector, string, deque, 或 array容器中取得top n的元素，部分排序partial_sort是首选.

若对于vector, string, deque, 或array容器，你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序，nth_element是最理想的；

若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开，你最好使用partition或stable_partition；

若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果，你必须间接使用。正如上面介绍的有几种方式可以选择。

1）插入排序： for(int i=1;i<5;i++)

for(int j=i;j>0&&a[j-1]>a[j];j--) //小的换到前面，否则结束循环 swap(a[j-1],a[j]);

改进一：多次循环调用，用内联函数替换函数调用

改进二：减少移动次数，循环开始前 t=a[i] ; 循环中一步一步后移 ; 最后a[j]=t;

2）快速排序：

qsort1:O(nlog(n)时间和O(logn)的栈空间

改进一：双向移动，改进最坏情况（所有元素相等）

改进二：随机选轴

改进三：先按小组排序，组内无序，组间递增。然后整个插入排序。

第十二章 取样问题

问题描述：如何生成0~n-1内的m个随机整数（不重复）

需求：按序输出，并且保证每个子集被选中的可能性相等。

//这里没有保证按顺序输出

for(i=0;i<n;++i)

If(rand()%(n-i) < m) //这里n-i保证了选取每个数概率相同

{

print I; --m;

}

//采用模板容器 Set 保证按序输出插入操作在O(logm)时间内完成，而遍历集合需要O(m)时间。所以完整程序需要O(mlogm)时间

set<int> s;

while(s.size() < m)

s.insert(rand()%n);

如果要选取的数个数 m 非常接近最大值n 。则可以采取剔除 n-m 个数的方法选取。

方法二：打乱前m个数，然后排序前m个数输出

核心代码：

for(int i=0;i<m;++i)

{

swap(a[i],a[rand()%(n-i)]);

}

问题1）一般随机选择m个整数，给出一个算法在最坏情况下

十三章 搜索

主要通过使用数组、链表、STL模板容器、位向量、二叉树、箱等数据结构来处理“生成a-b之间的随机数”的问题。

如果经常插入节点，而每次都要申请内存。

改进：freenode =new node[maxelements];

用的时候，node p =freenode++; //保证freenode 总是指向当前可用空间

第十四章 堆（排序，优先级队列）

1）初始建立堆（向下调整堆）

给一个数组，将数组看做完全二叉树。

从最后一个非叶结点（length/2，下标从1开始），直到第一个结点a[1]，向上调整建立堆。

2）排序和堆调整（向下调整堆）

将第一个值a[1] 跟最后一个值交换，然后对 a[1] 调整堆（此时数组长度调整为length-1）

3）插入（向上调整堆）

将元素插入到数组最后，采用向上调整堆的策略。

二，1）向上调整堆（采用哨兵）

void insert(T t) //向上调整堆
{
      int i, p;
      x[++n] = t; //插入的元素放到最后
     x[0]=t;
    for (i = n; x[p=i/2] > x[i]; i = p)
         swap(x[p], x[i]);
}

第十五章 字符串

字符串个数统计 map容器、散列表

字符串排序 set容器

字符串相同子串 后缀数组

如何将单词按频率递减顺序输出，并输出M个最常见单词（频率最高的M个单词）

map容器存放每个单词，然后根据元素个数域查找频率最高的M个单词