把《编程珠玑》读薄
具体化你的解决的问题
给定一个包含32位整数的顺序文件，它至多只能包含40亿个这样的整数， 并且整数的次序是随机的。请查找一个此文件中不存在的32位整数。 在有足够主存的情况下，你会如何解决这个问题？ 如果你可以使用若干外部临时文件，但可用主存却只有上百字节， 你会如何解决这个问题？
http://www.hawstein.com/posts/12.3.html
具体化你的解决的问题
如果主存容量不是严苛地限制在1MB，比如说可以是1MB多，或是1~2MB之间， 那么我们就可以一次性将所有数据都加载到主存中，用Bitmap来做。 10,000,000个数就需要10,000,000位，也就是10,000,000b = 1.25MB。
如果主存容量严苛地限制在1MB，而使用Bitmap需要1.25MB， 因此无法一次载入完成排序。那么，我们可以将该文件分割成两个文件， 再分别用Bitmap处理。分割策略可以简单地把前一半的数据放到一个文件， 后一半的数据放到另一个文件，分别排序后再做归并。 也可以把文件中小于某个数(比如5,000,000)的整数放到一个文件，叫less.txt， 把其余的整数放到另一个文件，叫greater.txt。分别排序后， 把greater.txt的排序结果追加到less.txt的排序结果即可。
啊哈！算法给定一个包含32位整数的顺序文件，它至多只能包含40亿个这样的整数， 并且整数的次序是随机的。请查找一个此文件中不存在的32位整数。 在有足够主存的情况下，你会如何解决这个问题？ 如果你可以使用若干外部临时文件，但可用主存却只有上百字节， 你会如何解决这个问题？
http://www.hawstein.com/posts/12.3.html
Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory.
FOLLOW UP
What if you have only 10 MB of memory?
Heap
后缀数组
我们对数组pc进行排序，将所有后缀按字典序排序
许智磊，《后缀数组》
罗穗骞，《后缀数组——处理字符串的有力工具》
Please read full article from 把《编程珠玑》读薄
我们先来做个算术题，40亿个整数大概有多大？
40 * 10^8 * 4B = 16GB (大约值，因为不是按照2的幂来做单位换算)
这个明显无法一次性装入内存中。但是，如果我们用计算机中的一位来表示某个数出现与否， 就可以减少内存使用量。比如在一块连续的内存区域，15出现，则将第15位置1。 这个就是Bit Map算法
如果用Bit Map算法，一个整数用一位表示出现与否，需要的内存大小是：
40 * 10^8 b = 5 * 10^8 B = 0.5GB
而我们有1GB的内存，因此该算法可行。由于Bit Map只能处理非负数， (没有说在第-1位上置1的)，因此对于有符号整数，可以将所有的数加上0x7FFFFFFF， 将数据移动到正半轴，找到一个满足条件的数再减去0x7FFFFFFF即可。 因此本文只考虑无符号整数，对于有负数的情况，按照上面的方法处理即可。
int int_len = sizeof(int) * 8;
int bit_len = 0xFFFFFFFF / int_len;
int* bit = new int[bit_len];
int v;
while(scanf("%d", &v) != EOF){
bit[v/int_len] |= 1<<(v%int_len);
}
bool found = false;
for(int i=0; i<bit_len; ++i){
for(int j=0; j<int_len; ++j){
if((bit[i] & (1<<j)) == 0){
cout<<i*int_len + j<<endl;
found = true;
break;
}
}
if(found) break;
}What if you have only 10 MB of memory?
第二问，如果我们只有10MB的内存，明显使用Bit Map也无济于事了。 内存这么小，注定只能分块处理。我们可以将这么多的数据分成许多块， 比如每一个块的大小是1000，那么第一块保存的就是0到999的数，第2块保存的就是1000 到1999的数……实际上我们并不保存这些数，而是给每一个块设置一个计数器。 这样每读入一个数，我们就在它所在的块对应的计数器加1。处理结束之后， 我们找到一个块，它的计数器值小于块大小(1000)， 说明了这一段里面一定有数字是文件中所不包含的。然后我们单独处理这个块即可。
接下来我们就可以用Bit Map算法了。我们再遍历一遍数据， 把落在这个块的数对应的位置1(我们要先把这个数归约到0到blocksize之间)。 最后我们找到这个块中第一个为0的位，其对应的数就是一个没有出现在该文件中的数。
int int_len = sizeof(int) * 8;
int totalnum = 20000;
int blocksize = 2000;
int blocknum = totalnum / blocksize;
int* block = new int[blocknum];
int* bit = new int[blocksize/int_len+1];
int v;
while(scanf("%d", &v) != EOF){
++block[v/blocksize];
}
fclose(stdin);
int start;
for(int i=0; i<blocknum; ++i){
if(block[i] < blocksize){
start = i * blocksize;
break;
}
}
freopen("12.3.in", "r", stdin);
while(scanf("%d", &v) != EOF){
if(v>=start && v<start+blocksize){
v -= start; // make v in [0, blocksize)
bit[v/int_len] |= 1<<(v%int_len);
}
}
bool found = false;
for(int i=0; i<blocksize/int_len+1; ++i){
for(int j=0; j<int_len; ++j){
if((bit[i] & (1<<j)) == 0){
cout<<i*int_len+j+start<<endl;
found = true;
break;
}
}
if(found) break;
}
- 请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8,i=3， 那么向量abcdefgh旋转之后得到向量defghabc。
这个问题很常见了，做3次翻转即可，无需额外空间：
reverse(0, i-1); // cbadefgh
reverse(i, n-1); // cbahgfed
reverse(0, n-1); // defghabc
- 给定一本英语单词词典，请找出所有的变位词集。例如，因为“pots”， “stop”，“tops”相互之间都是由另一个词的各个字母改变序列而构成的， 因此这些词相互之间就是变位词。
数据决定程序结构恰当的数据视图实际上决定了程序的结构。 我们常常可以通过重新组织内部数据来使程序变得小而美。
发明家悖论：更一般性的问题也许更容易解决。
程序员在节省空间方面无计可施时，将自己从代码中解脱出来， 退回起点并集中心力研究数据，常常能有奇效。数据的表示形式是程序设计的根本。
下面是退回起点进行思考时的几条原则：
- 使用数组重新编写重复代码。冗长的相似代码常常可以使用最简单的数据结构—— 数组来更好地表述。
- 封装复杂结构。当需要非常复杂的数据结构时，使用抽象术语进行定义， 并将操作表示为类。
- 尽可能使用高级工具。
- 从数据得出程序的结构。在动手编写代码之前，优秀的程序员会彻底理解输入， 输出和中间数据结构，并围绕这些结构创建程序。
提到的书籍：Polya的《How to Solve it》，中文书《怎样解题》； Kernighan和Plauger的《Elements of Programming Style》；Fred Brooks的《人月神话》 Steve McConnell的《代码大全》；《Rapid Development》； 《Software Project Survival Guide》
编写正确的程序
本章以二分搜索为例子，讲述了如何对程序进行验证及正确性分析。
深入阅读：David Gries的《Science of Programming》 是程序验证领域里极佳的一本入门书籍。
编程中的次要问题
到目前为止，你已经做了一切该做的事：通过深入挖掘定义了正确的问题， 通过仔细选择算法和数据结构平衡了真正的需求，通过程序验证技术写出了优雅的代码， 并且对其正确性相当有把握。万事俱备，只欠编程。
使用断言assert
自动化测试程序
进阶阅读：《Practice of Programming》第5章(调试)，第6章(测试) 《Code Complete》第25章(单元测试)，第26章(调试)
程序性能分析
一个程序可以从多方面进行性能提升，而其中算法和数据结构的选择又显得尤为重要。
粗略估算
文中先抛出一个问题：密西西比河一天流出多少水？如果让你来回答， 你会怎么答，注意不能去Google哦。
作者是这么回答这个问题：假设河的出口大约有1英里宽和20英尺深(1/250英里)， 而河水的流速是每小时5英里，也就是每天120英里。则可以计算出一天的流量：
1英里 * 1/250英里 * 120英里/天 约等于 1/2 英里^3/天
两个答案比一个答案好。即鼓励你从多个角度去对一个问题进行估算， 如果从不同角度得到的答案差别都不大，说明这个估算值是比较靠谱的。
节省空间
不存储，重新计算。
稀疏数据结构。下面着重讲一下这点。
数据压缩。可以通过压缩的方式对对象进行编码，以减少存储空间。
分配策略。只有在需要的时候才进行分配。
垃圾回收。对废弃的存储空间进行回收再利用。
排序
// 版本1
void InsertSort(int a[], int n) {
for(int i=1; i<n; ++i)
for(int j=i; j>0 && a[j-1]>a[j]; --j)
swap(a[j-1], a[j]);
}
// 版本2
void InsertSort1(int a[], int n) {
for(int i=1; i<n; ++i) {
int t = a[i];
int j = i;
for(; j>0 && a[j-1]>t; --j)
a[j] = a[j-1];
a[j] = t;
}
}
实现1：单向移动版本
这个版本的关键是设置一快一慢两个指针，慢指针左侧都是小于等于pivot(包含慢指针所在位置)， 慢指针到快指针之间的值是大于pivot，快指针右侧的值是还未比较过的。示意图如下：
小于等于pivot ｜ 大于pivot ｜ ？
slow fast
快指针一次一步向前走，遇到大于pivot什么也不做继续向前走。遇到小于等于pivot的元素， 则慢指针slow向前走一步，然后交换快慢指针指向的元素。一次划分结束后， 再递归对左右两侧的元素进行快排。代码如下：
// 数组快排
void QSort(int a[], int head, int end) {
if(a==NULL || head==end) return;
int slow = head, fast = head + 1;
int pivot = a[head];
while(fast != end) {
if(a[fast] <= pivot)
swap(a[++slow], a[fast]);
++fast;
}
swap(a[head], a[slow]);
QSort(a, head, slow);
QSort(a, slow+1, end);
}
排序数组a只需要调用QSort(a, 0, n)即可。该思路同样可以很容易地在链表上实现：
// 单链表快排
void qsort(Node *head, Node *end){
if(head==NULL || head==end) return;
Node *slow = head, *fast = head->next;
int pivot = head->data;
while(fast != end){
if(fast->data <= pivot){
slow = slow->next;
swap(slow->data, fast->data);
}
fast = fast->next;
}
swap(head->data, slow->data);
qsort(head, slow);
qsort(slow->next, end);
}
排序头指针为head的单链表只需调用qsort(head, NULL)即可。
实现2：双向移动版本
版本1能能够快速完成对随机整数数组的排序，但如果数组有序， 或是数组中元素相同，快排的时间复杂度会退化成O(n2 )，性能变得非常差。
一种缓解方案是使用双向移动版本的快排，它每次划分也是使用两个指针， 不过一个是从左向右移动，一个是从右向左移动，示意图如下：
小于等于pivot ｜ ？ ｜ 大于pivot
i j
指针j不断向左移动，直到遇到小于等于pivot，就交换指针i和j所指元素 (指针i一开始指向pivot)；指针i不断向右移动，直到遇到大于pivot的， 就交换指针i和j所指元素。pivot在这个过程中，不断地换来换去， 最终会停在分界线上，分界线左边都是小于等于它的元素，右边都是大于它的元素。 这样就避免了最后还要交换一次pivot的操作，代码也变得美观许多。
int partition(int a[], int low, int high){
int pivot = a[low], i=low, j=high;
while(i < j){
while(i<j && a[j]>pivot) --j;
if(i < j) swap(a[i], a[j]);
while(i<j && a[i]<=pivot) ++i;
if(i < j) swap(a[i], a[j]);
}
return i;
}
void quicksort(int a[], int first, int last){
if(first<last){
int k = partition(a, first, last);
quicksort(a, first, k-1);
quicksort(a, k+1, last);
}
}
当然，如果对于partition函数，你如果觉得大循环内的两个swap还是做了些无用功的话， 也可以把pivot的赋值放到最后一步，而不是在这个过程中swap来swap去的。代码如下：
int partition(int a[], int low, int high){
int pivot = a[low], i=low, j=high;
while(i<j){
while(i<j && a[j]>pivot) --j;
if(i<j) a[i++] = a[j];
while(i<j && a[i]<=pivot) ++i;
if(i<j) a[j--] = a[i];
}
a[i] = pivot;
return i;
}
如果数组基本有序，那随机选择pivot(而不像上面那样选择第一个做为pivot) 会得到更好的性能。在partition函数里，我们只需要在数组中随机选一个元素， 然后将它和数组中第一个元素交换，后面的划分代码无需改变， 就可以达到随机选择pivot的效果。
进一步优化
对于小数组，用插入排序之类的简单方法来排序反而会更快，因此在快排中， 当数组长度小于某个值时，我们就什么也不做。对应到代码中， 就是修改quicksort中的if条件：
if(first < last) 改为 if(last-first > cutoff)
其中cutoff是一个小整数。程序结束时，数组并不是有序的， 而是被组合成一块一块随机排列的值，并且满足这样的条件： 某一块中的元素小于它右边任何块中的元素。我们必须通过另一种排序算法对块内进行排序。 由于数组是几乎有序的，因此插入排序比较适用。
这种方法结合了快排和插入排序，让它们去做各自擅长的事情，往往比单纯用快排要快。
取样问题
问题：对于整数m和n，其中m<n，输出0~n-1范围内m个随机整数的
有序列表， 不允许重复。
比如m=3, n=5，那么一种可能输出是0，2，3(要求有序)。实现1来自Knuth的TAOCP， 时间复杂度O(n)：
void GenKnuth(int m, int n) {
for(int i=0; i<n; ++i) {
if((bigrand()%(n-i)) < m) {
cout<<i<<endl;
--m;
}
}
}
其中，bigrand()的作用是返回一个很大的随机整数。
实现2：在一个初始为空的集合里面插入随机整数，直到个数足够。代码如下：
void GenSets(int m, int n) {
set<int> s;
while(s.size() < m)
s.insert(bigrand() % n);
set<int>::iterator i;
for(i=s.begin(); i!=s.end(); ++i)
cout<<*i<<endl;
}
实现3：把包含整数0～n-1的数组顺序打乱，然后把前m个元素排序输出。 该方法的性能通常不如Knuth的算法。代码如下：
void GenShuf(int m, int n) {
int x[n];
for(int i=0; i<n; ++i)
x[i] = i;
for(int i=0; i<m; ++i) {
int j = randint(i, n-1);
swap(x[i], x[j]);
}
sort(x, x+m);
for(int i=0; i<m; ++i)
cout<<x[i]<<endl;
}Heap
// 把第i个元素向上移动
void ShiftUp(int a[], int i) {
while(i>1 && a[i]>a[i/2]) {
swap(a[i], a[i/2]);
i >>= 1;
}
}
// 把第i个元素向下移动
void ShiftDown(int a[], int n, int i) {
while((i=2*i) <= n) {
if(i+1<=n && a[i+1]>a[i]) ++i;
if(a[i] > a[i/2]) swap(a[i], a[i/2]);
else break;
}
}
// 把数组a变成具备最大堆性质的数组
void MakeHeap(int a[], int n) {
for(int i=n/2; i>0; --i)
ShiftDown(a, n, i);
}
// 向堆中插入元素x
void Insert(int a[], int &n, int x) {
a[++n] = x;
ShiftUp(a, n);
}
// 删除堆中第i个元素
void Del(int a[], int &n, int i) {
a[i] = a[n--];
if(i>1 && a[i]>a[i/2]) ShiftUp(a, i);
else ShiftDown(a, n, i);
}
// 堆排序，时间复杂度O(nlogn)
void HeapSort(int a[], int n) {
MakeHeap(a, n);
for(int i=n; i>1; --i) {
swap(a[i], a[1]);
ShiftDown(a, i-1, 1);
}
}后缀数组
我们对数组pc进行排序，将所有后缀按字典序排序
我们再输出pc[i]，会得到排序后的结果：
awstein
ein
hawstein
in
n
stein
tein
wstein
我们把数组pc称为“后缀数组”。这里需要注意，数组pc 中存储的是指向每个后缀首字符的地址。我们也可以存储每个后缀首字符在原数组中的下标， 效果是一样的。
本章中用后缀数组解决了一个小问题：可重叠最长重复子串。比如对于字符串"banana"， 其后缀数组为：
a
ana
anana
banana
na
nana
扫描一次数组，比较相邻子串，找到相邻子串的最长公共前缀即可。本例为"ana"， 其中一个a是重叠的。
后缀数组是处理字符串的有力工具，常见的两种实现方法是：倍增算法和DC3算法。 推荐阅读以下材料来学习后缀数组：
许智磊，《后缀数组》
罗穗骞，《后缀数组——处理字符串的有力工具》
Please read full article from 把《编程珠玑》读薄
