那些算法在哪里？

在我看来，一个系统背后主要发挥作用的算法更容易在非算法课程上找到，这和应用数学中的成果比理论数学中更容易出现在应用中是一个道理。在讲座中，很少有实际问题能够精确匹配到一个抽象问题。归根结底，我认为没有理由让流行的算法课程，诸如strassen乘法，aks素性测试、或者moser-tardos算法与底层实际问题，如实现视频数据库、优化的编译器、操作系统、网络拥堵控制系统或者其他系统相关。这些课程的价值是学习利用错综复杂的方法发现问题的脉络而找出有效的解决方案。高级算法和简单算法的分析都不简单。正是由于这个原因，我不会忽略简单随机算法或者pagerank。

我想你可以选择任何一个大型软件，并在内部找到它所采用的基础和高级的算法。作为一个研究案例，我选择了linux内核，并会示例一些chromium里面的例子。

<a target="_blank"></a>

一个相对简单的b+树的实现。我把它作为一个学习练习来帮助理解b+树是如何工作的。这同样也被证明是有用的。 ... 一个在教科书中并不常见的技巧。最小的值在右侧而不是在左侧。所有在一个节点里用到的槽都在左侧，所有没有用到的槽包含了空值(nul)。大多数操作只简单地遍历所有的槽一次并在第一个空值时(nul)终止。

根树的一个通用的用处是存储指针到结构页中。

《简单的基于clr的只插入的，含有指针的定长优先级堆》第七章

knuth建议，用乘法哈希的机器字来表示接近黄金比例的素数的最大整数。chuck lever验证了该技术的有效性： <a target="_blank">http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf</a> 这些素数的选择是位稀疏的，他们可以通过移位和加法操作，而不必使用乘法器，乘法器是很慢的。

使用了一种旋转哈希算法的哈希函数 knuth, d. 《计算机程序设计艺术, 卷 3: 排序与搜索》, 第6、7章. addison wesley, 1973

执行一个修改过的命名空间树的深度优先遍历，以指定的start_handle节点开始（及结束）。回调函数会在任何一个参数匹配的节点被发现时被调用。如果回调函数返回了一个非0值，搜索将会立即终止并且将其返回给调用者。

根据knuth、morris和pratt[1]实现了一个线性时间的字符串匹配算法。他们的算法避免了转换函数的显式地计算delta。对于长度为n的文本，其匹配时间是o(n)，对于长度为m的模式(pattern)，仅使用一个辅助函数pi[1 . .m]，预先计算模式的时间为o(m)。数组pi允许转换函数delta被实时有效地计算。粗略地说，对于任何状态"q"= 0,1,…、m和在sigma中的任何字符"a",pi["q"]的值包含的信息是独立的"a"并需要计算delta("q","a") [2]。既然pi只有m个记录，而delta有o(m |sigma|)个记录，在预处理时间计算pi而不是delta的时候，我们可以节省一个因数|sigma| [1] cormen, leiserson, rivest, stein，算法介绍，第二版，mit出版社 [2] 见有限自动机原理

实现了boyer-moore字符串匹配算法: 注:由于boyer-moore(bm)从右到左搜索匹配，仍然有可能匹配分布在多个块，在这种情况下该算法并没有优势。 如果你希望确保这样的事情永远不会发生，那使用knuth-pratt-morris(kmp)实现。总之，根据您的设置适当地选择字符串搜索算法。 如果你正在用文本搜索器进行过滤，nids或任何类似的注重安全的目的，那么使用kmp。否则，如果你真的关心性能，并且你对数据包进行分类以使用服务质量(qos)政策，当你不介意匹配可能分布分散，那么用bm。

这个树通过分配策略（分配器）参数化。这个策略用于c的可用存储区的列表分配，参见zone.h。

在chromium的第三方代码里面也有如下的数据结构和算法。

julian walker的总结 红黑树是一个有趣的小东西。他们被认为比avl树(它们的直接竞争对手)简单，乍一看这似乎是由于插入是一项轻松的乐事。然而，当你开始删除时，红黑树变得非常棘手。然而，通过复杂性的平衡，插入和删除可以使用单通道，实现自上而下的算法。这与avl树情况不一样，插入只能自顶向下，删除则需要自下而上。 红黑树是很流行的，像大多数数据结构一样有一个古怪的名字。比如，在java和c++库映射结构通常用红黑树实现。红黑树的速度也与avl树相当。而avl树平衡性不是很好，需要保持平衡的话红黑树通常更好。有一些流传的误解，但在大多数情况下对红黑树的宣传是准确的。

我想这个问题值得思考。编程语言设计者们认为值得花一些工程师的时间和精力来实现这些数据结构和算法，这样其他人就不必这么做了。这些库是我们在java里面比c更少的发现需要重新实现基本数据结构的部分原因。

我发现这些很有趣，因为即使他们被称为启发式，您使用的策略规定了算法类型和需要的数据结构，因此，所以需要人们知道栈和队列。

2.其他的还有先入先出（fifo）、最常使用和轮询。

3.fifo的一个变种用于vax/vms系统。

5.intel i860处理器是一种随机替代策略。

2.tsort实现了拓扑排序。

5.unix上的crypt(1)实现了一个在enigma机器上的不同加密算法。

这本是一个非常长的列表。加密算法在所有执行安全通信和交易的程序中都有实现。

2.支配算法被用于大多数基于ssa形式的编译器优化。

3.lex和flex将正则表达式编译为nfa。

2.行程长度编码用于产生pcx文件(用于原来的画笔程序)，它是被压缩的bmp和tiff文件。

3.小波压缩是jpeg2000的基础，所以所有生成jpeg2000文件的数码相机会支持这个算法。

原文发布时间为：2013-11-30

本文来自云栖社区合作伙伴“linux中国”