编程珠玑算是比较有年头的一套程序员进阶的书籍，这里是我的读书笔记。
开篇
一开头就拿出了这么一个例子，给10000000个7位整数排序（无重复的整数），但是你可能只有1MB的主存，怎么办又快又好呢？通常的想法是归并，多几次就可以了。但是其实还有更好的方法，就是利用位图的位向量。例如如果集合是{1，2，3，5，8，13}，那么可以存储在下面这个字符串中：
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0
集合中代表数字的各个位设置为1，而其他的位全部都设置为0。这时候如果要个这10000000个整数排序，就可以分成这三步：1）初始化一个大数组。2）遍历一遍这10000000个数，出现过的就在数组中标注为1。3）最后再遍历一遍这个数组，把出现1的对应位置的数字输出一遍即可。
瞬间什么排序都不用了，而且只需要两次遍历，豁然开朗，柳暗花明之感。从这个例子可以总结出一些值得以后借鉴的经验：
正确的问题。明确了问题，就更能找到最佳的解答。
位图数据结构。该数据结构描述了一个有限定义域内的稠密集合，其中的每一个元素最多出现一次并且没有任何其他数据与该元素相关联。即使这些条件没有完全满足(例如，存在重复元素或额外的数据)，也可以用有限定义域内的键作为一个表项更复杂的表格的索引。
多趟算法。多趟读入其输入数据，每次完成一步。
时间-空间折中与双赢。只有在原始的设计远非最佳方案时，才有可能时空双赢。
简单的设计。设计者确定其设计已经达到了完美的标准不是不能再增加任何东西，而是不能再减少任何东西。
1.如果不缺内存，如何使用一个具有库的语言来实现一种排序算法以表示和排序集合？
python 的 list 的 sort 方法就挺好，简单粗暴
list = [1,2,3,4,5]
list.sort()
2.如何使用位逻辑运算(与，或，移位)来实现位向量？
位向量的实现就是用比特位0,1来表示一些特定信息，通常是用数组，每个int中包含32个bits，当我们定位某个位置时，先确定索引是在哪个int中，然后再确定int中的那个位对应索引。
c++中有现成的 bitset，原理应该差不多
3.实现位图排序并度量运行时间
位图的实现我用了三种，一个是c语言的（简称cvec），一个是c++的（简称cppvec），还有时c++现成的bitset（简称bitset）。系统排序用的是sort命令，加上-n选项。排序用了c的qsort，c++的sort和c++的set。
cvec 1.737 1.001
cppvec 1.769 1.033
bitset 2.644 1.908
系统sort命令 5.290 4.554
qsort 2.081 1.345
sort 2.802 2.066
set 5.921 5.185
输入输出的时间是0.736s。左右分别为带输入输出和不带的。
可以看出两种语言位图的实现都是效率最高的，c++中的bitset，set，sort虽然效率上差了点，但是实现上非常方便，而且能保证一定的正确性。系统的排序实在方便，一句命令就可以搞定(sort -n < in -o out).
4.如何生成小于 n 且没有重复的 k 个整数？
如果要想生成这样一个数组，可以直接从头到尾循环，每个数随机位置交换值就可以。
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 10000000;
const int K = 10000000;
int randint( int l, int r ){
return rand() % ( r-l ) + l;
}
int a[ N ];
int main(void){
for( int i = 0; i < N; i++ )
a[i] = i;
for( int i = 0; i < K; i++ ){
swap( a[i], a[ randint(i,N) ] );
printf("%d\n",a[i]);
}
return 0;
}
5.如果存储[0,10000000]大概需要1.25MB，但内存限定为1MB，要如何处理呢？
可以将输入文件分成两分，第一份保存[0,5000000)的数，第二个文件保存[5000000,10000000)的数字，然后分别进行排序，所用内存就可以降到1MB以内。如果我们把文件分成k份（每份都存一定区间的数），那么就可以在n的时间，n/k的空间内完成排序。
6.如果每个整数不只是出现一次而是最多可能出现十次，那么要如何修改算法呢？
每个整数最多出现10次，那么保存每个数字信息的空间不再是1bit了，可以用4bits来保存，可以类比第五题，可以分成4份，在n/4的空间内完成。同样，当保存数字信息的量变化时，分成更多份，就可以在更小的空间内完成。
7.程序还需要进行哪些错误检测，如何处理？
数出现超过一次。当第二次更新的时候，相应位已经是1了，这个时候提示错误。
当输入小于0或者大于等于n。当输入数字时候对其进行范围判断，忽略或者提示错误。
不是数值。忽略，给出提示
8.之前的电话数据区号都是800，现在免费电话的区号还包括877和888并且可能还会增多，那么如何排序呢？如何将免费电话存储在一个集合中，要求可以实现非常快速的查找来判定是否已经存在？
一个想法是把区号作为前缀加入到每个号码后面，然后利用bitmap进行存储，又或者维护另一个区号的映射表，这样可以减少编码的长度。检索的时候就看对应值是不是为1就行。
!!9.使用更多的空间来换取更少的运行时间存在一个问题：初始化空间本身需要消耗大量的时间。如果数据很稀疏，那么要如何存储？
初始化空间需要大量时间，不过我们的应用只需要其中一点点空间，比如1000000的位图，我们只用到其中的10位，怎样节省时间？题目中提示，可以用额外的正比于向量大小的空间。
解决方法使用了两个额外的向量，from和to，变量top。如果对i位置进行初始化，进行以下步骤：
from[i] = top;
to[top] = i;
data[i] = 0;
top++;
from[i]=top的目的是将i在to中的索引放入to中，to[top]=i的意思是，这个top位置对应的是i，这时data就可以做相应的操作，然后top右移。
判断一个位置是否初始化过的条件是from[i] < top && to[from[i]] == i,from[i]<top的意思是from[i]对应的to中的位置已经被处理过了，但是from[i]可能是随机值，也只能会小于top，那么这时就需要第二个条件了，to[from[i]] == i的意思是，to[from[i]] 所指向的位置就是i，这种双向的指向性的内容确保了能确定i位置是否被初始化过。
10.如何组织电话号码以允许高效的插入和检索操作？
类似于取快递，根据电话号码的最后一位或者最后两位进行分类，类似于哈希的思想，用顺序遍历来处理碰撞。不能用开头的原因是很多电话号码的前面都是一样的，比如手机号码都是以1开头的。而且最后一位的分布比较随机、均匀。
11.汽车每天运送图纸需要一个小时，有什么办法可以减少时间或者费用？
飞鸽传书，答案也是醉
12.外太空写字的笔
铅笔
深入阅读
Michael Jackson \
程序员的主要问题与其说是技术问题，还不如说是心理问题。很多时候没有办法解决问题是因为想要解决错误的问题。问题的最终解决，是通过打破概念壁垒，进而去解决一个较简单的问题而实现的。
James L. Adams
啊哈！算法
看起来很困难的问题解决起来可能很简单，并且还很可能出人意料之外。只有经过广泛的研究之后才能对算法具备那种出神入化的理解力。任何愿意在编码前、编码期间以及编码后任职思考的程序员都可具备这种能力。
算法与其他哪些深奥的思想一样重要，但在更一般的编程层面上具有更重要的影响
三个问题
- 给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数。在具有足够内存的情况下，如何解决？如果有几个外部的临时文件可用，但是只有几百字节的内存，又该如何解决？
- 将一个 n 元一维向量向左旋转 i 个位置。简单的代码使用一个 n 元的中间向量在 n 步内完成工作。你能否仅适用数十个额外字节的存储空间，在正比于 n 的时间内完成向量的旋转？
- 给定一个英语词典，找出其中的所有变位词集合，例如
pots,stop,tops互为变位词。
问题 1
采用已知包含至少一个缺失元素的一系列整数作为范围，并使用包含所有这些整数在内的文件表示这个范围，通过统计中间点之上和之下的元素来探测范围：或者上面或者下面的范围具有至多全部范围的一半元素。由于整个范围中有一个缺失元素，因此我们所需的那一半范围中必然也包含缺失的元素
问题是这样的，给定一个包含32位整数的顺序文件，它至多只能包含40亿个这样的整数，并且整数的次序是随机的。请查找一个此文件中不存在的32位整数。
这个时候二分查找法就非常有用，首先遍历一遍这40亿个数字，并分为两组，一组是左边第一位为1的，一组是左边第一位为0的，正常来说，上下应该各占据一半，但因为总范围内有遗漏元素（假设只有一个），那么比较小的那一组必包含此遗漏元素。继续在比较小的那一组使用1与0的分组，很快就可以找到这个遗漏的整数。
问题 2
简单的方法就不说了，另一个想法是给出了旋转的位数其实每个字母的最终位置是确定的，只需要一个临时变量，把对应的放过去即可。但是这种方法比较容易出错，不容易维护。
另一个方法是把问题看做数组 ab 转换成 ba。
ab - a’b - a’b’ - (a’b’)’ - ba
假设原来是 abcdefgh，向左旋转 3 位
reverse(0, i-1) // cbadefgh
reverse(i, n-1) // cbahgfed
reverse(0, n-1) // defghabc
这种方法高效且简短
问题 3
直接处理的话，问题非常复杂，需要大量的计算。因为我们只是需要找到同位词，那其实只要把拥有同样字母的单词贴上同样的标志即可。比如说，把每个单词里的字母按照字典序排序，而在具体的标志过程其实也有一些技巧，比如说good可以简化为go2d，这种标识法在长单词多重复时可以减少编码的长度。
具体的映射方式很多，这里不一一赘述
1.考虑查找给定输入单词的所有变位词的问题。仅给定单词和字典的情况下，如何解决该问题？如果有一些时间和空间可以在响应任何查询之前预先处理字典，又会如何？
在给定单词和字典的情况下，遍历字典，计算每个的标签，然后与给定的单词的标签比较。可以预处理的话就好说了，将所有单词按照标签排序，然后可以用equal_range求出区间，O(logN)。
2.给定包含 4300000000 个 32 位整数的顺序文件，如何找出一个出现至少两次的整数？
可以类比如何找出没有出现的整数。4300000000 大于int的表示范围。可以先扫描一遍，把第一位为0的和第一位为1的放到两个不同的文件中，看哪个文件里面的数多，就开始处理这个文件，把第二位的0和1的数字放到两个文件中，看哪个的数字多，依此类推，最后肯定得到一个数，他出现了不止一次。
3.前面涉及了两个需要精确代码来实现的旋转算法，写出代码。在每个程序中，i 和 n 的最大公约数如何出现
gao函数是那个杂技算法，gaogao是块交换算法。经过简单的测试还没有发现什么问题。n和len的最大公约数就是置换的次数。
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int gcd( int a, int b ){
return b==0?a:gcd(b, a%b);
}
int gao( int *start, int *end, int n ){
int len = end - start;
int d = gcd( n, len );
for( int i = 0; i < d; i++ ){
int t = *(start+i);
int next = i;
while( (next+n)%len != i ){
*(start+next) = *(start+(next+n)%len);
next = (next+n)%len;
}
*(start+next) = t;
}
}
gaogao函数用到了一个辅助函数，rangeswap，就是将[start1,start1+n)和[start2,start2+n)的值进行交换。
void rangeswap( int *start1, int *start2, int n ){
for( int i = 0; i < n; i++ )
swap( *(start1+i), *(start2+i) );
}
void gaogao( int *start, int *end, int shift ){
int len = end - start;
shift = ( shift%len + shift )%len;
if( len <= 1 ) return;
if( shift <= len / 2 ){
rangeswap( start, end - shift, shift );
gaogao( start, end - shift, shift );
}
else{
rangeswap( start, start+shift, len - shift );
gaogao( end - shift, end, shift - len );
}
}
const int n = 1000000;
int main(void){
int a[n];
for( int i = 0; i < n; i++ )
a[i] = i;
gao( a, a+n, 6);
for( int i = 0; i < n; i++ )
cout << a[i] << ' ';
cout << endl;
return 0;
}
STL中还有一种更bt的实现方法，algorithm中有个rotate，他用及其简单的代码就实现了循环位移。代码如下：
template <class ForwardIterator>
void rotate ( ForwardIterator first, ForwardIterator middle, ForwardIterator last )
{
ForwardIterator next = middle;
while (first!=next)
{
swap (first++,next++);
if (next==last) next=middle;
else if (first == middle) middle=next;
}
}
除了Orz我已经无话可说了。。
4.比较三种不同的旋转算法
暂略
5.向量旋转函数将向量 ab 变为 ba，如何将 abc 变为 cba？
对每一块儿进行翻转，然后对整体进行翻转即可。
6.如何实现以一个名字的按键编码为参数，并返回所有可能的匹配名字的函数？
计算出所有人名的按键信息（标识），然后按照标识进行排序，查询的时候二分即可。答案中提示更多使用的是hash和数据库。
7.如何快速转置一个存储在磁带上的 4000x4000 的矩阵，从原来的50个小时缩减到半小时？
可能是因为磁带的读写问题所导致的，具体不清楚
8.给定一个 n 元实数集合、一个实数 t 和一个整数 k，如何快速确定是否存在一个 k 元子集，其元素之和不超过 t？
第一感觉想到的是排序，然后看前k个数的和是否不超过t，不超过的话肯定存在。更优的方法用O(N)的选择算法求出第k大的数，然后把数组扫描一遍，求出小于第k大数的数的和sum，加上第k大。这样看似没有什么错误，但是仔细想想，如果第k-1大，第k大，第k+1大的数一样，肿么办？easy~扫描的时候顺便统计小于第k大数的数的个数a，和第k大的数的个数b，嗯，然后如果a<k-1,就从b中取出m个，直到a+m == k-1。
9.顺序搜索和二分搜索代表了搜索时间和预处理时间之间的折中。处理一个 n 元表格时，需要执行多少次二分搜索才能弥补对表进行排序所消耗的预处理时间？
这个，具体让我来算一算
10.爱迪生的故事
用水来测体积
数据决定数据结构
合适的数据结构确实构造了程序。本章描述了各种不同的程序，通过重构它们的内部数据，使其变得更加简短（而且更好）。数据结构本该短小、干净、漂亮，而不是巨大、混乱、丑陋不堪的。
能用小程序实现，就不要编写大程序。
程序员在节省空间方面无计可施时，将自己从代码中解脱出来，退回起点并集中心力研究数据，常常能有奇效，(数据的)表示形式是程序设计的根本。
下面是退回起点进行思考时的几条原则：
- 使用数组重新编写重复代码。冗长的相似代码常常可以使用最简单的数据结构——数组来更好地表述。
- 封装复杂结构。当需要非常复杂的数据结构时，使用抽象术语进行定义，并将操作表示为类。
- 尽可能使用高级工具。超文本、名字-值对、电子表格、数据库、编程语言等都是特定问题领域中的强大的工具。
- 从数据得出程序的结构。彻底理解输入、输出和中间数据结构，并围绕这些结构创建程序。
1.税收分段计费
使用数组来简化循环。数组中每个点表明一个阶段，用level[i]表示阶段i的起始点，tax[i]表示阶段i的税率，用have [i]表示这个阶段已经有的税收，然后得到收入后二分到相应的阶段，计算税收。
2.k 阶常系数线性递归
真心没看懂题目，也是醉
3.编写一个“banner”函数，该函数的输入为大写字母，输出为一个字符数组，该数组以图形化的方式表示该字母
这个就是用数组画图呗，三维数组即可。
原来要求的就是对三维数组进行信息压缩，自定一种格式显示即可。
4.编写处理如下日期问题的函数：给定两个日期，计算两者之间的天数；给定一个日期，返回值为周几；给定月和年，使用字符数组生成该月的日历
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int month[13] = {
0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
// 1 2 3 4 5 6 7 8 9 10 11 12
};
class D{
public:
int year,mon,day;// 1900 <= year, 1 <= mon <= 12,
// 1 <= day <= 31
D(){}
D(int y, int m, int d):
year(y),mon(m),day(d){}
int yearday(void){//返回这一天是这一年的第几天
int sum = day;
for( int i = 1; i < mon; i++ )
sum += month[i];
if( isrun() && mon > 2 )
sum ++;
return sum;
}
bool isrun( void ){//是否是闰年
return (year%4==0&&year%100!=0)||(year%400==0);
}
};
int dist( D d1, D d2 ){//两个日期相差的天数
int sum = -(d1.yearday());
for( ; d1.year < d2.year ; d1.year++ )
sum += d1.isrun()?366:365;
return sum + d2.yearday();
}
int xingqiji( D d ){//某一天是星期几
D temp(1900,1,1);
return dist( temp, d )%7+1;
}
int print(int year, int mon ){//输出某月日历
D d(year, mon, 1 );
int week = xingqiji(d);
int sum = month[ mon ];
for( int i = 1; i < week; i++ )
cout << " ";
for( int i = 1; i <= sum; i++){
cout << i << " ";
if( week == 7 ){
week = 1;
cout << endl;
}
else week++;
}
cout << endl;
}
int main(void){
D a(2012,6,3);
cout << xingqiji(a) << endl;
print(1990,2);
return 0;
5.处理英语中的一小部分连字符问题。
从前到后进行比较，符合一个输出就行。
6.题目略
回答略
7.其实我没有看懂题目的意思
所以我也没办法回答
8.编写一个使用 5 个七段显示数字来显示十六位正整数的程序。输出为一个 5 字节的数组，当且仅当数字 j 中的第 i 段点亮时，字节 j 中的位 i 置 1。
转化为一道题目，是zoj1146
深入阅读
数据可以结构化程序，但是只有聪明的程序员才能结构化大型软件系统。
编写正确的程序
二分查找并不像想象中简单。
二分搜索的关键思想是如果 t 在 x[0…n-1] 中，那么它就一定存在于 x 的某个特定范围之内。这里使用 mustbe(range) 来表示。逻辑函数 mustbe(l, u) 是说：如果 t 在数组中，t 就一定在(闭区间)范围 x[l…u] 内。
最终的函数为
l = 0; u = n - 1
loop
{ mustbe(l, u) }
if l > u
p = -1; break;
m = (l + u) / 2
case
x[m] < t: l = m+1
x[m] == t: P = m; break
x[m] > t: u = m-1
1.如何证明二分搜索没有运行时错误(例如除数为0、数值溢出、变量值超出声明范围或者数组下标越界)？
为了保证范围不超过范围，我们需要在初始化的时候，让变量不超出范围。这样每次循环得到的新的范围是慢慢缩小的，不会越界。
!!2.把 t 在数组 x 中地一次出现的位置返回给 p(如果存在多个的话，原始的算法会任意返回其中的一个)。要求代码对数组元素进行对数次比较(在log~2 n 次比较内完成)
int bs( int *a, int l, int r, int v ){
while( l <= r ){
if( a[l] == v ) return l;
int mid = (l+r)/2;
if( a[mid] < v ) l = mid+1;
if( a[mid] == v )r = mid;
if( a[mid] > v ) r = mid-1;
}
return -1;
}
这个二分可以返回所需要查询的元素第一次出现的位置，如果不存在，则返回-1.在每个循环内，我们假定元素第一次出现的范围是闭区间[l，r]内，当循环体内语句执行完之后，我们得到了一个新的区间。新的区间的范围是一直在收敛的（不会存在r，l执行完循环之后大小没有变化。），所以程序可以终止，得到正确结果。
3.编写一个递归的二分搜索程序
int bss( int *a, int l, int r, int v ){
if( l > r ) return -1;
if( a[l] == v ) return l;
int mid = (l+r)/2;
if( a[mid] < v ) return bss( a, mid+1, r, v );
if( a[mid] == v )return bss( a, l, mid, v );
if( a[mid] > v ) return bss( a, l, mid-1, v );
}
递归每加深一层，[l,r]的范围就减小。本层的后置条件要和下一层的前置条件吻合。
4.验证运行时间是对数的
略
5.证明下面的程序在输入 x 为正整数时能够终止
while x != 1 do
if even(x)
x = x/2
else
x = 3 * x + 1
找一下规律
从 2 开始: 2 1 4 2 1 4….无法终止
从 3 开始: 3 10 5 16 8 4 2 1 4 2 1 4…无法终止
最终都会归于 214 循环
6.咖啡罐问题：给定一个装有一些黑豆子和一些白豆子的咖啡罐以及一大堆额外的黑豆子，重复下面过程直到罐中只剩一颗豆子为止——从罐中选取两个豆子，如果颜色相同，就都扔掉并放入一个额外的黑色豆子，如果颜色不同，将白色的留下，黑色的扔掉。证明该过程会停止，最后留在罐中的豆子颜色与最初白豆子和黑豆子的数量有何函数关系？
每次执行一次，罐子中的豆子数量就减去1,所以此过程可以终止。
化简到最后的阶段
1 白 1 黑 -> 白
2 白 -> 黑
2 黑 -> 白
可得出以下结论：
如果最后留下的是白色的，那么开始时候白色的个数为奇数，否则为偶数。
7.确定点与线段的位置关系
先是给一个线段的范围。然后选取中间的线，看点在他上面还是下面，然后可以缩小一半的查找范围。类似于二分查找
8.如何在不改变二次比较次数的前提下让代码运行得更快？
暂时没有想到什么
9.证明程序有效性的题目
两个n维的向量相加。初开始时：i=0表示前i个维度的都已经计算好了。在循环之中，计算一个维度，然后i加一，计算下一个维度，每个循环结束表明前i个维度已经计算完毕。i一直在增大，证明这个过程是可以终止的。当最后一个循环执行完毕的时候，i的值是n，表明前n个维度已经计算好了。所以其代码是正确的。
求x数组的最大值。初开始时候，max=x[0]表示最大值是第一个数，i=1表示前i个数的最大值已经求出。每次循环时候，如果有比max大的数，就替换，当循环结束时候，前i个数的最大值就知道了。当整个过程结束时，i==n，所以前n个数的最大值可以求出。
当循环找个一个t的时候，就停止循环，或者当i超出范围的时候停止。i在每一次循环的时候值都增加，所以这个算法是可以结束的。当超出范围的时候，返回-1，否则返回的就是第一次出现的位置，因为i的值是从小到大递增的。
每次递归，问题的规模都是缩小的，所以问题可以在有限步骤内结束。每次递归完成一次，就可以得到上次层想要的运算结果，接着向上传递。
编程小事
脚手架。最好的脚手架通常是最容易构建的脚手架。
编码。对于比较难写的函数，我发现最容易的方法是使用方便的高级伪代码来构建程序框架，然后将伪代码翻译成要实现的语言。
测试。在脚手架中对组件进行测试要比在大系统中更容易、更彻底。
调试。对隔离在其脚手架中的程序进行调试是很困难的，但是若将其嵌入真实运行环境中，调试工作会更困难。
计时。用以测试达到预期的性能
程序性能分析
可以通过以下几个不同层次的改进，来获得巨大的加速：
- 算法和数据结构。改进访问的效率，分治法
- 算法调优。配合数据结构进行优化
- 数据结构重组
- 代码调优。对于不需要特别高精度的计算，可以用精度较低的类型代替
- 硬件。升级性能我会乱说
原理
- 计算机系统中最廉价、最快速且可靠的元件是根本不存在的
- 如果仅需要较小的加速，就对效果最佳的层面做改进
- 如果需要较大的加速，就对多个层面做改进
粗略估算
基本技巧
- 两个答案比一个答案好。如果两种方法得到的估算结果比较接近，那么很可能答案是靠谱的。
- 快速检验。量纲检验
- 经验法则。比如说，假设以年利率 r% 投资一笔钱 y 年，如果 r x y = 72，那么你的投资差不多会翻倍。
计算的输入决定了其输出的质量。基于良好的数据，简单的计算也可以得到精确的计算结果。
Brooklyn Bridge的设计者John Reobling是一个很有趣的人，在1940年左右，有许多桥因为暴风雨断裂了，那时候因为科学的限制并没有办法具体算出气动上升现象究竟需要多少的承载力。但是John Roebling充分意识到他不知道某些东西，所以在他意识到气动上升现象时，知道自己不足以对其建模，于是将Brooklyn Bridge桥上的铁索强度设计成基于已知的静态和动态负载的常规计算所要求强度的六倍。
Roebling是一名优秀的工程师，他使用一个巨大的安全系数来补偿他对某些方面的无知，从而使得Brooklyn Bridge成为当时所建现在唯一没有垮掉的桥。所以在对软件系统进行性能计算时，最好按照2、4或6的系数降低性能，以补偿我们的无知。
Little 定律：队列中物体的平均数量为进入速率与平均停留时间的乘积。
下面举三个例子来说明利特尔法则：
有一个非常火爆的夜总会，你现在在排队，前面有20个人，你知道这个地方可以容纳60个人，平均来说每个人进去待3个小时，所以进入率就是每小时20个人，你大概就知道你大约需要等待1个小时。（同样可以推广到在游乐场等待游戏设施，不过最好别算，算了总是让人伤心）
假如我在地下室中存有150个酒瓶，我每年会喝掉25瓶并买回新的25瓶酒，那么每个容器我要保存多少年。应用利特尔法则，150除以25，得到每个容器保存六年。
假设平均思考时间为z的n个用户连接到了一个任意的系统中，其响应时间为r。每个用户都在思考和等待响应之间循环，所以总计作业数都是n。如果切断系统输出到用户之间的路径，你就能看到一个元系统，其平均负载为n，平均响应时间为z+r，吞吐量x=n/(r+z)
任何事都应尽量简单，但不宜过于简单。
1.贝尔实验室距离狂野的密西西比河大约有1000英里，而我们距离平时比较温和的帕塞伊克河只有几英里。在一个星期的倾盆大雨后，报纸说“帕塞伊克河的流速为200英里每小时，大约是平时的五倍”，你有何评论？
什么叫温和，我觉得可能是流速大约在跑步与汽车低速之间，假设是20英里每小时好了。一条河的流速的影响因素很多，比方说总流量，宽度，还有水量。经过综合考虑，我觉得报道上的流速太夸张了，200英里，吓死人。
常见流速其实是每小时2英里。也许200英里是一天的流速，是常见的一天40英里的五倍
2.在什么距离下骑自行车的送信人使用移动存储介质传递信息的速度高于高速数据线的传输速度？
假设这个移动存储介质的容量是无限的，要传递的信息的大小是 N mb，然后高速数据线的传输速率是 V mb/h，骑车的速度是 S km/h
可以转化为 N / V x S = 临界距离，具体找几个可能的数值代入进去算，考虑一些额外消耗即可。
3.手动录入文字来填满一张软盘需要多长时间？
考虑到软盘几近灭绝，我们就拿填满 1MB 为例子吧。
一个汉字占两个字节，我的打字速度大概是一分钟80个字，也就是一分钟可以填充160个字节，那么 1 MB = 1024 KB = 1024 x 1024 B
1024 x 1024 / 160 = 6553 min = 109 hour
4.假设整个世界变慢为原来的百万分之一。你的计算机执行一条指令需要多长时间？你的磁盘旋转一周需要多长时间？磁盘臂在磁盘上搜索需要多长时间？键入自己的名字又需要多长时间？
CPU的时钟频率为5MHz，即一个时钟周期为0.2μs，那么一条指令大约需要6-20个周期。现在的硬盘大约是7200转或者5400转，后面的类推即可
5.如何进一步检验 72 法则？
增长速率介于 5% 和 10% 之间，72法则估算的误差在1%以内。
6.联合国估算1998年的世界人口为59亿，年增长率为1.33%。如果按照这个速率，到2050年世界人口会是多少？
2050-1998=52； 52*1.33≈70
因此根据72法则，2050年人口约为59*2=118亿。
10.请估计一下你所在城市的死亡率，用每年的总人口百分比来度量
通过报纸上的死亡通告并估算本地人口来估算死亡率。或者是利用 Little 定律以及对平均寿命的估算。例如，如果平均寿命为70年，那么每年有1/70或1.4%的人口死亡
11.给出 Little 定律的概要证明
具体看官方解答吧
12.一些报纸称，25美分硬币的平均寿命是30年，该如何检验真伪呢？
抽样统计，平均数的两倍大约为寿命
算法设计技术
算法领悟可以使程序更加简单。复杂算法有时可以极大地提高性能。
问题的提出
一个具有n个浮点数字的数组x，目标是要找到之中连在一起的数组元素中找到最大和。例如如果输入的数组是以下这十个元素：
31 -41 59 26 -53 58 97 -93 -23 84
那么程序应该返回从59到97的综合，也就是187。第一个算法迭代了所有满足 0 ≤ i ≤ j ＜ n 的 i 和 j 整数对，分别计算总和，最终找到综合最大的组合。
最初的算法（算法1）
maxsofar = 0
for i = [0, n)
for j = [i, n)
sum = 0
for k = [i, j]
sum += x[k]
maxsofar = max(maxsofar, sum)
这段代码比较简短、直观并且易于理解，唯一遗憾的就是——慢。基本上来说可以判断这个算法的大O是n的三次方。
二次算法（算法2）
第一个二次算法注意到 x[i..j]中的总和与前面已计算的 x[i..j-1] 的总和密切相关，从而减少了计算量。
maxsofar = 0
for i = [0, n)
sum = 0
for j = [i, n)
sum += x[j]
maxsofar = max(maxsofar, sum)
外循环和内循环都要执行n次，所以大O是n的平方。但是如果这样我们依然觉得不够，因为检测所有值肯定需要花费二次方时间，如何可以避开这个问题？
分治算法（算法3）
分治法的思想是这样的：要解决规模为 n 的问题，可递归解决两个规模近似为 n/2 的子问题，然后将它们的答案进行合并以得到整个问题的答案。
具体到这个问题上，可以把整个数组分为两个大约相等的部分，就叫 a 和 b。然后递归找出 a 和 b 中元素和最大的子数组，称为 ma 与 mb。然后再找到 ma 与 mb 之间的最大子数组称为 mc。最后找到最大的一个即可。代码如下：
float maxsum3(l, u)
if (l > u) return 0
if (l == u ) return max(0, x[l])
m = (l + u) / 2
lmax = sum = 0
for (i = m; i >= l; i--)
sum += x[i]
lmax = max (lmax, sum)
rmax = sum = 0
for i = (m, u]
sum += x[i]
rmax = max (rmax, sum)
return max(lmax+rmax, maxsum(l, m), maxsum3(m+1, u))
代码非常微妙，也就意味着非常容易出错，但是复杂度是O(n log n)。
扫描算法（算法4）
从最左端（元素 x[0]）开始，一直扫描到最右端（元素 x[n-1]），记下所碰到过的最大总和子数组。最大值初始为0.假设我们已经解决了针对 x[0..i-1] 的问题，现在需要拓展到 x[i] 中。可以使用类似分治法中的道理，前 i 个元素中，最大总和子数组要么在 i-1 个元素中（存储在 maxsofar 中），要么截止到位置 i（存储在 maxendinghere中）。下面就是扫描算法：
maxsofar = 0
maxendinghere = 0
for i = [0, n)
maxendinghere = max(maxendinghere + x[i], 0)
maxsofar = max(maxsofar, maxendinghere)
这个算法代码更加简短，但是运行起来是最快的，运行时间是O(n)，已经是线性算法，不可能再快了。
原则
这个问题的原型其实是Grenander面对的模式匹配问题（在最大子数组问题中，给定 n x n 的实数数组，如何找出任意具有最大总和的举行子数组）。为了简便，所以化为一维，并且经过不同人的努力，得到了最后的扫描算法。总这里我们就可以看出来几个重要的算法设计技术。
- 保存状态，避免重新计算。算法2和4使用了简单的动态编程形式。
- 将信息预处理到数据结构中
- 分治算法
- 扫描算法
- 累积
- 下限
只有经过广泛地研究和实践，才能熟练地使用算法设计技术
代码调优
优秀的程序员会保持代码效率：效率在软件中只是众多问题中的一个，但有时也是极其重要的一个。代码优化确定现有程序中的开销昂贵的部分并提高其速度，虽然并不总是适当的方法，并且很少能吸引人，但是有时确实可以使程序的性能大不一样。
问题1：整数取模
原来的代码
k = (j + rotdist) % n;
但在C语言中取模(其实大部分语言都是)的开销很大，使用下面代码可以减少时间
k = j + rotdist;
if (k >= n)
k -= n;
如果程序的运行时间主要消耗在输入输出上，那么对程序中的计算进行加速是毫无意义的。
问题2：函数、宏和内联代码
因为现代编译器的优化，小心出现很难发现的错误
问题3：顺序搜索
原来的代码是这样的
int ssearch1(t)
for i = [0,n)
if x[i] == t
return i
return -1
可以使用 loop unrooling 技术减少分支判断提高速度
问题4：计算球面距离
这个问题就是地理或集合数据处理方面的典型应用场合。先输入一个由球面上5000个点组成的S集，每个点都由经度和纬度表示。然后读入20000个点组成的序列，每个点都由经度和纬度表示。对于该序列中的每个点，程序需要指出S集中哪个点最接近它，其中的距离是以球体中心到两个点的连线之间的角度来度量的。
如果想要利用别出心裁的算法（很可能需要好几百行代码），那么可能付出很大的代价。为什么不是用简单的数据结构？于是更换成三维坐标系而不是精度纬度。这样只需要几十行的代码优化，运行时间从几个小时降低为半分钟。
问题5：二分查找
代码优化在二分查找中通常不是必需的，因为二分查找算法的效率已经较高了。但是对于特定问题其实仍有优化的空间，比如如果一个序列中同一数字出现多次的情况，这里就不细说。
原则
有关代码优化最重要的原则就是尽量少用代码优化。总的来说可以概括为以下几点：
- 效率的角色。软件的许多其他属性和效率一样重要，甚至更重要。不成熟的优化是大量编程灾害的根源。
- 度量工具。当效率变得重要时，第一步就是对系统进行配置，找出花费时间的位置。对程序进行剖析将指出关键的区域；对于其他区域，“没有坏的话就不要修复它”。
- 设计层次。在优化代码以前，我们应该确保其他方法不会提供更加有效的解决方案。
- 双刃剑。有时候使用if语句替换%求余运算符可以得到两倍的加速，而有时候则没有什么差别。“咬人的人也应该提防被咬”。
节省空间
时常努力考虑压缩程序是很有利的。有时这种思考会带来新的启示，使程序变得更加简单。减少空间通常带来运行时间上合理的副作用：程序越小，加载的时候也越快，也越容易填充到高速缓存中；需要操作的数据越少，操作时所花的时间通常也就越少。
关键在于简单性
简单性可以产生功能性、健壮性以及速度和空间。简单性也可以减少代码的空间。
例如遇到稀疏数组，就有多种方法可以进行空间的压缩，一种就是把一个二维数组转化为一个一维数组+链表的组合。
数据空间技术
不存储，重新计算。如果我们在需要某一给定对象的任何时候，都对其进行重新计算而不保存，那么所需空间就可以急剧减少。
稀疏数据结构。使用指针来共享大型对象可以消除存储同一对象的众多副本所需的开销。
数据压缩
分配策略。动态分配
垃圾回收
排序
使用库排序函数并不总是有效的，有时使用起来会非常麻烦，这种时候，手动编写排序函数就成为了唯一的选择。
插入排序
伪代码
for i = [1,n)
for (j=i; j>0 && x[j-1] > x[j]; j--)
swap(j-1, j)
swap 函数调用会带来很大的额外开销，内联之后还可以进一步优化
for i = [1, n)
t = x[i]
for (j=i; j>0 && x[j-1] > t; j--)
x[j] = x[j-1]
x[j] = t
一种简单的快速排序
排序数组时，将数组分成两个小部分，然后对它们递归排序。
void qsort(l, u)
if l >= u then
/* at most one element, do nothing */
return
/* goal:partition array around a particular value,
which is eventually placed in its correct position p
*/
qsort(l, p-1)
qsort(p+1, u)
更详细一点的代码是 qsort1，可以通过调用 qsort1(0, n-1) 来排序数组 x[n]
void qsort2(l, u)
if (l >= u)
return
m = l
for i = [l+1, u]
/* invariant: x[l+1..m] < x[l] && x[m+1..i-1] >= x[l] */
if (x[i] < x[l])
swap(++m, i)
swap(l, m)
/* x[1..m-1] < x[m] <= x[m+1..u] */
qsort2(l, m-1)
qsort2(m+1, u)
当输入数组是不同元素的随机排列时，该快速排序平均需要 O(n log n) 的时间和 O(log n) 的栈空间。
更好的几种快速排序
考虑一种极端的情况：n 个相同元素组成的数组，对于这种输入，qsort1 的性能非常糟糕，总的性能为O(n^2)
使用双向划分可以避免这个问题，下标 i 和 j 初始化为待划分数组的两端。主循环内有两个内循环，第一个内循环将 i 向右移过小元素，遇到大元素时停止；第二个内循环将 j 向左移过大元素，遇到小元素时停止。然后主循环测试这两个下标是否交叉并交换它们的值。
遇到相同的元素时停止扫描，并交换 i 和 j 的值。虽然这样做使交换的次数增加了，但却将所有元素都相同的最坏情况变成了比较好的情况
void qsort3(l, u)
if l >= u
return
t = x[l]; i = 1; j = u+1
loop
do i++ while i <= u && x[i] < t
do j-- while x[j] > t
if i > j
break
swap(i, j)
swap(l, j)
qsort3(l, j-1)
qsort3(j+1, u)
我们的快盘程序花费了大量的时间来排序很小的子数组。如果用插入排序之类的简单方法来排序这些很小的数组，程序的速度会更快。
void qsort4(l, u)
if u-l < cutoff
return
swap(l, randint(l, u))
t = x[l]; i = 1; j = u+1
loop
do i++ while i <= u && x[i] < t
do j-- while x[j] > t
if i > j
break
temp = x[i]; x[i] = x[j]; x[j] = temp
swap(l, j)
qsort4(l, j-1)
qsort4(j+1, u)
qsort4(0, n-1)
isort3() // 再用插入排序
3.在特定的系统上如何求出最佳的 cutoff 值？
做测试，都跑一次，然后找到最佳性能的点
4.虽然快速排序平均只需要 O(log n) 的栈空间，但是在最坏情况下需要线性空间，请解释原因。修改程序，使得最坏情况下仅使用对数空间。
参考算法书
5.编写程序，在O(n)时间内从数组 x[0..n-1] 中找出第 k 个最小的元素。算法可以对 x 中的元素进行排序
这个参考July的博客
取样问题
编写程序从 0 到 n-1 中随机输出 m 个有序整数
void gensets(int m, int n){
set<int> S;
while(S.size() < m)
S.inseart(bigrand() % n);
set<int>iterator i;
for (i = S.begin(); i != S.end(); ++i)
cout << *i << "\n";
}
但是用 set 的话，时间开销比较大。
另一种方法是把包含 0 到 n-1 的数组顺序打乱，然后把前 m 个元素排序输出
for i = [0, n)
swap(i, randint(i, n-1))
其实只需要打乱前 m 个元素即可
void genshuf(int m, int n){
int i, j;
int *x = new int[n];
for (i = 0; i < n; i++)
x[i] = i;
for (i = 0; i < m; i++){
j = randint(i, n-1)
int t = x[i]; x[i] = x[j]; x[j] = t;
}
sort(x, x+m);
for (i = 0; i < m; i++)
cout << x[i] << "\n";
}
原理
正确理解所遇到的问题。与用户讨论问题产生的北京。问题的陈述通常就包含了与解决方案有关的想法。
提炼出抽象问题。简洁、明确的问题陈述不仅可以帮助我们解决当前遇到的问题，还有助于我们把解决方案应用到其他问题中。
考虑尽可能多的解法
实现一种解决方案
1.C库函数 rand() 通常返回约15个随机位。使用该函数实现函数 bigrand() 和 randint(l,u)，要求前者至少返回30个随机位，后者返回[l,u]范围内的一个随机整数
int bigrand(){
return RAND_MAX*rand() + rand();
}
int randint(int l, int u){
return l + bigrand() % (u-l+1);
}
8.如何从 0 到 n-1 中随机选择 m 个整数，使得最终的输出顺序是随机的？如果有序列表中允许有重复整数，如何生成该列表？如果既允许重复，又要求按随机顺序输出，情况又如何？
第一次生成整数时就输出
9.[R. W. Floyd] 当 m 接近于 n 时，基于集合的算法生成的很多随机数都要丢掉，因为它们之前已经存在于集合中了。能否给出一个算法，使得即使在最坏情况下也只使用 m 个随机数？
void genfloyd(int m, int n){
set<int> S;
set<int>::iterator i;
for (int j = n - m; j < n; j++){
int t = bigrand() % (j+1);
if (S.find(t) == S.end())
S.insert(t); // t is not in S
else
S.insert(j); // t is in S
}
for(i = S.begin(); i != S.end(); ++i)
cout << *i << "\n";
}
10.如何从 n 个对象(可以依次看到这 n 个对象，但事先不知道 n 的值)中随机选择一个？具体说来，如何在事先不知道文本文件行数的情况下读取该文件，从中随机选择并输出一行？
总选择第一行，然后以1/2的概率选择第2行，然后1/3几率选择第三行。在这一过程是，每一行选中的概率都是相等的
i = 0
while more input lines
with probability 1.0/++i
choice = this input line
print choise
搜索
空间的重要性。调优得很好的链表虽然完成的工作只有数组的一半，但却需要两倍于数组的时间。因为数组中每个元素所占的内存只有链表的一半，而且数组是顺序访问内存的。
代码调优方法。最显著的改进就是用只分配一个较大的内存块的方案来替换通用内存分配。这样就消除了很多开销较大的调用，而且也使空间的利用更加有效。对大多数结构来说，引入哨兵可以获得清晰、简单的代码，并缩短运行时间。
10.在完成类似于生成随机数的任务时，可以使用其他哪些数据结构来表示整数集合？
混合并匹配多种数据结构来表示随机集合
第 14 章：
解决两个重要问题：排序和优先级队列
字符串
散列。这一结构的平均速度很快，且易于实现
平衡树。这些结构在最坏情况下也有较好的性能
后缀数组
!!9.给定两个输入文本，找出它们的共有的最长字符串
把第一个字符串读入数组c，记录器结束的位置并在其最后填入空字符；然后读入第二个字符串并进行同样的处理。跟以前一样进行排序。扫描数组时，使用异或来确保恰有一个字符串是从过渡点前面开始的。
算法分类
排序
通用函数
- 插入排序。稳定排序算法
- 快速排序。递归
- 堆排序。非递归，仅适用固定大小额外空间
专用函数
- 基数排序。对字符串排序
- 位图排序。待排序整数通常在小范围内，无重复也没有多余数据
搜索
通用函数
- 顺序搜索
- 二分搜索
- 散列
- 二分搜索树
专用函数
- 关键字索引
其他集合算法
- 优先级队列
- 选择
字符串算法
- 变位词
- 最长重复子串
- 生成随机文本