项目中的常见算法-白红宇

项目中的常见算法

阅读量：6985 次

发布时间：2019-06-27

本文共 4111 字，大约阅读时间需要 13 分钟。

http://cstheory.stackexchange.com/questions/19759/core-algorithms-deployed/

本文原始内容来源于，遵循协议；

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

使用这些算法的软件或者硬件应该是被广泛应用的；

例子需要具体，并给出确切的系统、算法的引用地址；

在经典的本科生或者博士的课程中应该教过这些算法或者数据结构；

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

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

、和

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

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

...

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

　　用于、等；

调度、虚拟内存管理、跟踪文件描述符和目录条目等；

，用于内存管理、NFS 相关查找和网络相关的功能；

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

，文字上的描述，主要是在教科书中实现，用于 ;

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

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

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

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

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

，用于实现、等；

，用于处理 flags、中断等，在 Knuth 第四卷中有对其特性的描述；

二叉树搜索用于、等；

和他的变体被应用于；

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

用于在运行时检查锁的正确性；

链表上的用于、等；

在某个里，冒泡排序居然也被实现了

　　；

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(mSIGMA)个条目，我们通过计算 PI 进而在预处理时间保存 SIGMA 的系数，而非计算 DELTA。

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

[2] See finite automation theory

　　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.

[2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004

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

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

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

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

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

Demo 中使用了图

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

用于压缩的

苹果实现的

　　编程语言类库

，包含的有列表、堆、栈、向量、

非常广泛，包含的太多

，包含了诸如 Boyer-Moore 和 Knuth-Morris-Pratt 字符串匹配算法等；

　　分配和调度算法

最近最少使用算法有多种实现方式，在 Linux 内核中是基于的；

其他可能需要了解的是先入先出、最不常用和轮询；

VAX、VMS 系统中大量使用 FIFO 的变体；

的被用于 Linux 中页面帧替换；

Intel i860 处理器中使用了随机替换策略；

被用于一些 IBM 的存储控制中，由于在 PostgreSQL 只有简单的应用；

Knuth 在 TAOCP 第一卷中提到的被用于 Linux 内核中，FreeBSD 和都在使用 jemalloc 并发分配器；

　　*nix 系统中的核心组件

grep 和 awk 都实现了使用 Thompson-McNaughton-Yamada 构建算法实现从正则表达式中创建 NFA

tsort 实现了拓扑排序

fgrep 实现了；

GNU grep，据作者 Mike Haertel 所说，；

Unix 中的 crypt (1) 实现了（Enigma Machine）中的加密算法的变种；

Doug Mcllroy 基于和 James 合作的原型实现的，比用来计算 Levenshtein 距离的标准动态规划算法更好，Linux 版本被用来计算最短编辑距离；

　　加密算法

，尤其是 Tiger Tree Hash 的变种，用于点对点的程序，例如和;

用于为软件包提供校验码，还用于*nix 系统（）中的完整性校验，同时他还支持 Windows 和 OS X 系统；

实现了需要加密算法，诸如 AES，Blowfish，DES，SHA-1，SHA-2，RSA，DES 等；

　　编译器

yacc 和 bison 实现了

支配算法用于基于 SSA 形式的最优化编译器；

lex 和 flex 将正则表达式编译为 NFA；

　　压缩和图片处理

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

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

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

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

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

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

　　微博热议

　　Databricks 大数据公司联合创始人首先并在微博上传播了这个内容：

很多学生和软件工程师都会好奇自己过去学习的算法有什么实际应用的价值。这个 StackExchange 的回答列出了各种经典算法在几个开源项目中的应用。作者罗列出了从最基础的 hash table 到字符串匹配和加密算法等在 Chromium 和 Linux 内核的代码。查看开源代码是学习算法实现一个好途径。

　　大家也纷纷发表了自己的看法：

　　：