实际项目中的常见算法

原文地址：http://www.infoq.com/cn/news/2013/11/Core-algorithms-deployed

【编者按】本文原始内容来源于stackexchange，遵循cc-wiki协议；

近日Emanuele Viola在Stackexchange上提了这样的一个问题，他希望有人能够列举一些目前软件、硬件中正在使用的算法的实际案例来证明算法的重要性，对于大家可能给到的回答，他还提出了几点要求：

1. 使用这些算法的软件或者硬件应该是被广泛应用的；
2. 例子需要具体，并给出确切的系统、算法的引用地址；
3. 在经典的本科生或者博士的课程中应该教过这些算法或者数据结构；

Vijay D的回复获得了最佳答案，他的具体回复内容如下：

Linux内核中的基本数据结构和算法

1. 链表、双向链表和无锁链表

2. B+ 树，代码中的注释将会告诉你一些教科书中不能学到的内容：

   这是一个简单的B+树实现，我写它的目的是作为练习，并以此了解B+树的工作原理。结果该实现发挥了它的实用价值。

   ...

   一个不经常在教科书中提及的技巧：最小值应该放在右侧，而不是左侧。一个节点内所有被使用的槽位应该在左侧，没有使用的节点应该为NUL，大部分的操作只遍历一次所有的槽位，在第一个NUL处终止。

3. 带权重的有序列表用于互斥锁、驱动等；

4. 红黑树用于调度、虚拟内存管理、跟踪文件描述符和目录条目等；
5. 区间树
6. Radix树，用于内存管理、NFS相关查找和网络相关的功能；

   radix树的一个常见的用法是保存页面结构体的指针；

7. 优先级堆，文字上的描述，主要是在教科书中实现，用于control group系统;

   包含指针的只允许简单插入的静态大小优先级堆，基于CLR（算法导论）第七章

8. 哈希函数，引用Knuth和他的一篇论文：

   Knuth建议选择与机器字长所能表达的最大整数约成黄金比例的素数来做乘法散列，Chuck Lever 证实了这个技术的有效性；

   http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

   这些选择的素数是位稀疏的，也就是说对他们的操作可以使用位移和加法来替换机器中很慢的乘法操作；

9. 有些代码，比如这个驱动，他们是自己实现的哈希函数

10. 哈希表，用于实现索引节点、文件系统完整性检查等；
11. 位数组，用于处理flags、中断等，在Knuth第四卷中有对其特性的描述；
12. Semaphores 和 spin locks
13. 二叉树搜索用于中断处理、登记缓存查找等；
14. 使用B-树进行二叉树查找；
15. 深度优先搜索和他的变体被应用于目录配置；

    在命名空间树中执行一个修改过的深度优先算法，开始（和终止于）start_handle所确定的节点。当与参数匹配的节点被发现以后，回调函数将会被调用。如果回调函数返回一个非空的值，搜索将会立即终止，这个值将会回传给调用函数；

16. 广度优先搜索用于在运行时检查锁的正确性；
17. 链表上的合并排序用于垃圾回收、文件系统管理等；
18. 在某个驱动程序的库函数里，冒泡排序居然也被实现了

19. Knuth-Morris-Pratt 字符串匹配；

    Knuth、Morris和 Pratt [1]实现了一个线性时间复杂度字符串匹配算法。该算法完全规避了对转换函数DELTA的显式计算。其匹配时间为O(n)（其中n是文本长度），只使用一个辅助函数PI[1...m]（其中m是模式的长度），模式的预处理时间是O(m)。PI这个数组允许DELTA函数在需要时能迅速运行。大体上，对任意状态q=0,1,...,m和任意SIGMA中的字符"a"，PI["q"]保存了独立于"a"的信息，并用于计算DELTA("q", "a")。由于PI这个数组只包含m个条目，而DELTA包含O(m|SIGMA|)个条目，我们通过计算PI进而在预处理时间保存|SIGMA|的系数，而非计算DELTA。

    [1] Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press

    [2] See finite automation theory

20. Boyer-Moore模式匹配，如下是引用和对其他算法的使用建议；

    Boyer-Moore字符串匹配算法:

    [1] A Fast String Searching Algorithm, R.S. Boyer and Moore. Communications of the Association for Computing Machinery, 20(10), 1977, pp. 762-772. http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

    [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

    注意：由于Boyer-Moore（BM）自右向左做匹配，有一种可能性是一个匹配分布在不同的块中，这种情况下是不能找到任何匹配的。

    如果你想确保这样的事情不会发生，使用Knuth-Pratt-Morris（KMP）算法来替代。也就是说，根据你的设置选择合适的字符串查找算法。

    如果你使用文本搜索架构来过滤、网络入侵检测（NIDS）或者任何安全为目的，那么选择KMP。如果你关乎性能，比如你在分类数据包，并应用服务质量（QoS）策略，并且你不介意可能需要在分布在多个片段中匹配，然后就选择BM。

Chromium 浏览器中的数据结构和算法

1. 伸展树

   此树会被分配策略参数化，这个策略负责在C的自由存储空间和区域中分配列表，参见zone.h

2. Demo中使用了Voronoi图
3. 基于Bresenham算法的标签管理

同时，代码中还包含了一些第三方的算法和数据结构，例如：

1. 二叉树
2. 红黑树
3. AVL树
4. 用于压缩的Rabin-Karp字符串匹配
5. 计算自动机的后缀
6. 苹果实现的布隆过滤器
7. 布氏算法

编程语言类库

1. C++ STL，包含的有列表、堆、栈、向量、排序、搜索和堆操作算法
2. Java API 非常广泛，包含的太多
3. Boost C++ 类库，包含了诸如Boyer-Moore和Knuth-Morris-Pratt字符串匹配算法等；

分配和调度算法

1. 最近最少使用算法有多种实现方式，在Linux内核中是基于列表实现的；
2. 其他可能需要了解的是先入先出、最不常用和轮询；
3. VAX、VMS系统中大量使用FIFO的变体；
4. Richard Carr的时钟算法被用于Linux中页面帧替换；
5. Intel i860处理器中使用了随机替换策略；
6. 自适应缓存替换被用于一些IBM的存储控制中，由于专利原因在PostgreSQL只有简单的应用；
7. Knuth在TAOCP第一卷中提到的伙伴内存分配算法被用于Linux内核中，FreeBSD和Facebook都在使用jemalloc并发分配器；

*nix系统中的核心组件

1. grep和awk都实现了使用Thompson-McNaughton-Yamada构建算法实现从正则表达式中创建NFA
2. tsort实现了拓扑排序
3. fgrep实现了Aho-Corasick 字符串匹配算法；
4. GNU grep，据作者Mike Haertel所说，实现了Boyer-Moore算法；
5. Unix中的crypt(1)实现了哑谜机（Enigma Machine）中的加密算法的变种；
6. Doug Mcllroy基于和James合作的原型实现的Unix diff，比用来计算Levenshtein距离的标准动态规划算法更好，Linux版本被用来计算最短编辑距离；

加密算法

1. Merkle树，尤其是Tiger Tree Hash的变种，用于点对点的程序，例如GTK Gnutella 和LimeWire;
2. MD5用于为软件包提供校验码，还用于*nix系统（Linux实现）中的完整性校验，同时他还支持Windows和OS X系统；
3. OpenSSL实现了需要加密算法，诸如AES，Blowfish，DES，SHA-1，SHA-2，RSA，DES等；

编译器

1. yacc和bison实现了LALR解析器
2. 支配算法用于基于SSA形式的最优化编译器；
3. lex和flex将正则表达式编译为NFA；

压缩和图片处理

1. 为GIF图片格式而出现的Lempel-Zivsraf算法在图片处理程序中经常被应用，从一个简单的*nix组件转化为一个复杂的程序；

2. 运行长度编码被用于生成PCX文件（用于Paintbrush这个程序中），压缩BMP文件和TIFF文件；

3. 小波压缩（Wavelet压缩）是JPEG 2000的基础，所以所有生成JPEG 2000文件的数码相机都是实现了这个算法；

4. Reed-Solomon纠错用于Linux内核、CD驱动、条形码读取，并且结合卷积从航行团队进行图片传输；

冲突驱动条款学习算法（Conflict Driven Clause Learning）

自2000年以来，在工业标准中的SAT（布尔满足性问题）求解器的运行时间每年都在成倍减少。这一发展的一个非常重要的原因是冲突驱动条款学习算法（Conflict Driven Clause Learning）的使用，它结合了Davis Logemann和Loveland的约束编程和人工智能研究技术的原始论文中关于布尔约束传播的算法。具体来说，工业建模中SAT被认为是一个简单的问题（见讨论）。对我来说，这是近代最伟大的成功故事之一，因为它结合了先进的算法、巧妙的设计思路、实验反馈，并以一致的共同努力来解决这个问题。Malik和Zhang的CACM论文是一个很好的阅读材料。许多大学都在教授这个算法，但通常是在逻辑或形式化方法的课程中。