编程珠玑(The Programming Pearls)

https://book.douban.com/subject/3227098/

程序员在对空间缺乏无能为力时，往往会脱离代码的纠缠，回过头去凝神考虑它的数据结构，这样会找到更好的方法，表示法是编程的精华。

将重复代码写到数组里。使用最简单的数据结构数组，来表示一段冗长的相似性的代码，往往能达到最佳效果。
封装复杂的结构。当你需要一个复杂的数据结构时，使用抽象的术语对它进行定义，并将那些操作表示成一个类。
尽可能的使用高级工具。超文本，名称值对，电子表格，数据库，语言，以及类似的工具在其专门的问题域内都属于功能强大的工具。
让数据去构造程序。使用适当的数据结构去代替复杂的代码，这样可以使数据起到构造某个程序的效果。

这些技术仅仅是编写正确程序的一小部分，保持代码的简单性通常是正确性的关键。另一方面，有些熟悉这些技术的程序员给我的感觉是：当他们构建一个程序时，难的部分通常先通过，而错误往往就在容易的部分。这在我自己的编程经历中太常见了。当他们碰到难的部分时，他们就会耐下心来，成功的运用那些功能强大的正规技术；而在那些容易的部分，他们往往会回归到古老的编程方式中，因而得到的结果也是老的。以前我还没有碰到过这种现象，自己碰到过之后才相信这种现象。这种难堪的现象也是对经常使用这些正规技术的一个良好驱动。

“程序员在测试时使用断言，而在生产期间将它们关闭，这就像水手在岸上训练时穿上救生衣，在海里面时却将其脱下。” —— Tony Hoare. 我觉得这也是对对待错误处理应该是fail fast的一种支持。

多体仿真程序的优化（算法和数据结构优化才是根本）

设计层次	加速系数	修改
算法和数据结构	12	二叉树，O(n^2)->O(nlgn)
算法优化	2	使用更大的时间步长
数据结构重组	2	产生适合书算法的蔟
系统独立性代码优化	2	double->float
系统依赖性代码优化	2.5	汇编代码编写关键函数
硬件	2	浮点加速器

两个线性搜索程序的性能对比

int search1(int* x, int n, int t) {
    for (int i = 0; i < n; i++) {
        if (x[i] == t) {
            return i;
        }
    }
    return -1;
}

// 相比search1而言，增加sentinel. 因为我们确定最终肯定会匹配上
// 所以每次循环期间都可以少一次比较
int search2(int* x, int n, int t) {
    int tmp = x[n];
    x[n] = t;
    int i = 0;
    for (i = 0;; i++) {
        if (x[i] == t) {
            break;
        }
    }
    x[n] = tmp;
    if (i == n) {
        return -1;
    }
    return i;
}

// 和search2相比就是把循环展开，但是从指令数量上看并没有减少

int search3(int* x, int n, int t) {
    int tmp = x[n];
    x[n] = t;
    int i = 0;
    for (i = 0;; i += 8) {
        if (x[i] == t) { break; }
        if (x[i + 1] == t) { i += 1; break; }
        if (x[i + 2] == t) { i += 2; break; }
        if (x[i + 3] == t) { i += 3; break; }
        if (x[i + 4] == t) { i += 4; break; }
        if (x[i + 5] == t) { i += 5; break; }
        if (x[i + 6] == t) { i += 6; break; }
        if (x[i + 7] == t) { i += 7; break; }
    }
    x[n] = tmp;
    if (i == n) {
        return -1;
    }
    return i;
}

这里不好解释为什么循环展开要效率更高。可能是因为CPU可以进行推测执行来提高并行度或者是数据依赖被解开了（数组里面8个内容是可以并行访问的）。这种展开没有减少指令数，分支对比数，对分支预测似乎也没有改善。要是想继续什么了解指令优化，还是需要有相应的CPU工具，而不能只是胡乱猜测。

我在这里对比了这几种算法所占用的时间，我这里设计的case是需要查找的元素在数组的最末位。我觉得对比运行时间很有意思。我在代码里面实现了这么几个算法：

search1: 最简单的循环
search1-1: 在search1基础上循环展开
search2: 设置哨兵
search2-2: 在search2基础上按照步长8展开
search2-3: 在search2基础上按照步长16展开

然后分别使用-O0和-O2进行编译观察效果

先看-O0的效果，展开效果还是非常明显的，甚至比设置哨兵还要好。

➜  misc git:(master) ✗ g++ opt_linear_search.cc -O0 --std=c++0x
➜  misc git:(master) ✗ ./a.out
[  search1]Wall clock time passed: 211.902 ms
[ search11]Wall clock time passed: 96.595 ms
[  search2]Wall clock time passed: 169.321 ms
[ search21]Wall clock time passed: 72.6089 ms
[ search22]Wall clock time passed: 67.6039 ms

然后看-O2的效果. 展开效果似乎就没有那么明显了，甚至还有副作用。相比展开步长8和16的情况，发现步长并不是越长越好。

➜  misc git:(master) ✗ ./a.out
[  search1]Wall clock time passed: 34.7623 ms
[ search11]Wall clock time passed: 35.4613 ms
[  search2]Wall clock time passed: 43.5169 ms
[ search21]Wall clock time passed: 20.3011 ms
[ search22]Wall clock time passed: 24.6879 ms

现代处理器和编译器已经让这些古老的奇技淫巧变成了废物。规规整整地写代码通常可以获得比较好的性能，各种小技巧必须经过实测否则很难说明是否真的有效果。如果作为智力上的一种挑战那就是另外一回事情了。

书里面第9章代码优化里面给了一个二分搜索循环展开的例子，非常具有启发性。这个循环展开并不是基于[first, last]这种范围上，而是基于[first, first + size -1] 上不断地调整first和size展开的。假设我们搜索数组的范围大小是1000，那么我们可以先假设 size = 512 = 2^9. 代码如下，然后我们可以针对while最展开了。

int bin_search(int* x, int t) {
    int size = 512;
    int l = -1;
    if(x[511] < t) {
        l = 1000 - 512;
    }
    while (size!=1) {
        size = size / 2;
        if (x[l+size] < t) {
            l = l + size;
        }
    }
    int p = l + 1;
    if (p > 1000 || x[p] != t) {
        return -1;
    }
    return p;
}


int bin_search_unroll(int* x, int t) {
    int size = 512;
    int l = -1;
    if(x[511] < t) {
        l = 1000 - 512;
    }
    if (x[l+256] < t) {l += 256;}
    if (x[l+128] < t) {l += 128;}
    if (x[l+64] < t) {l += 64;}
    if (x[l+32] < t) {l += 32;}
    if (x[l+16] < t) {l += 16;}
    if (x[l+8] < t) {l += 8;}
    if (x[l+4] < t) {l += 4;}
    if (x[l+2] < t) {l += 2;}
    if (x[l+1] < t) {l+=1;}
    int p = l + 1;
    if (p > 1000 || x[p] != t) {
        return -1;
    }
    return p;
}

快速排序的partition算法，如果是只使用一个指针移动的话，那么同一元素可能会被扫描到两次，但是似乎这种算法实现上更加简单。而使用两个指针扫描然后交换的话，那么元素最多被扫描一次，效率高但是容易出错。

针对快速排序的改进，可以在范围小于某个cutoff的时候，改用插入排序。那么问题是，这个插入排序是应该在快速排序的递归里面调用呢？还是在外部使用一次插入排序。书里面给的方法是第二种。也会就是快速排序子问题中，如果范围小于cutoff那么直接终止，这样“快速排序”完成之后得到的一个每个局部块内部无序，但是块之间有序的数组。这个时候再使用一次插入排序完全排序。

插入排序对接近有序的数组上运行非常快，堆排序对小范围数组（cache locality）效果非常好，那么是否可以把这两个排序和快速排序结合起来呢？std::sort就是这么做的。http://feihu.me/blog/2014/sgi-std-sort/

我没有仔细阅读源代码，只是看了一下这个调用框架

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first != last) {
        __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
        __final_insertion_sort(first, last);
    }
}

template <class RandomAccessIterator, class T, class Size>
void __introsort_loop(RandomAccessIterator first,
                      RandomAccessIterator last, T*,
                      Size depth_limit) {
    while (last - first > __stl_threshold) {
        if (depth_limit == 0) {
            partial_sort(first, last, last);
            return;
        }
        --depth_limit;
        RandomAccessIterator cut = __unguarded_partition
          (first, last, T(__median(*first, *(first + (last - first)/2),
                                   *(last - 1))));
        __introsort_loop(cut, last, value_type(first), depth_limit);
        last = cut;
    }
}

template <class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                    RandomAccessIterator last, T*, Compare comp) {
    make_heap(first, middle, comp);
    for (RandomAccessIterator i = middle; i < last; ++i)
        if (comp(*i, *first))
            __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
    sort_heap(first, middle, comp);
}

template <class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first,
                         RandomAccessIterator middle,
                         RandomAccessIterator last, Compare comp) {
    __partial_sort(first, middle, last, value_type(first), comp);
}

整个调用框架是：

外部调用快速排序
对小范围区间特殊处理
- 如果递归深度很深的话，那么使用堆排序
- 否则不进行任何处理
对基本有序的数组进行插入排序

后缀数组很有意思。文章里面给的是查找重复子串的例子，比如 banana 那么最长重复子串是 ana : bana 和nana这两个字符串重合的。如果找到重复字符串可以使用后缀数组，比如 banana 可以保存每个字符串的后缀

banana
anana
nana
ana
na
a

然后我们排序然后比较相邻的后缀元素，就能找到ana. 第二长的是na

a
ana
anana
banana
na
nana

如果不用排序的话，其实可以将这些字符串插入trie树，来找到最长重复子串。