常见算法在实际项⽬中的应⽤
近⽇Emanuele Viola在Stackexchange上提了这样的⼀个问题，他希望有⼈能够列举⼀些⽬前软件、硬件中正在使⽤的算法的实际案例来证明算法的重要性，对于⼤家可能给到的回答，他还提出了⼏点要求：
使⽤这些算法的软件或者硬件应该是被⼴泛应⽤的；
例⼦需要具体，并给出确切的系统、算法的引⽤地址；
marry什么意思
在经典的本科⽣或者博⼠的课程中应该教过这些算法或者数据结构；
Vijay D的回复获得了最佳答案，他的具体回复内容如下：
Linux内核中的基本数据结构和算法
、和
，代码中的注释将会告诉你⼀些教科书中不能学到的内容：
这是⼀个简单的B+树实现，我写它的⽬的是作为练习，并以此了解B+树的⼯作原理。结果该实现发挥了
它的实⽤价值。
怎么了英文
…
⼀个不经常在教科书中提及的技巧：最⼩值应该放在右侧，⽽不是左侧。⼀个节点内所有被使⽤的槽位应该在左侧，没有使⽤的节点应该为NUL，⼤部分的操作只遍历⼀次所有的槽位，在第⼀个NUL处终⽌。
⽤于、等；
马耳他英语调度、虚拟内存管理、跟踪⽂件描述符和⽬录条⽬等；
，⽤于内存管理、NFS相关查找和⽹络相关的功能；
radix树的⼀个常见的⽤法是保存页⾯结构体的指针；
，⽂字上的描述，主要是在教科书中实现，⽤于
包含指针的只允许简单插⼊的静态⼤⼩优先级堆，基于CLR（算法导论）第七章
哈希函数，引⽤Knuth和他的⼀篇论⽂：
Knuth建议选择与机器字长所能表达的最⼤整数约成黄⾦⽐例的素数来做乘法散列，Chuck Lever 证实了这个技术的有效性；
这些选择的素数是位稀疏的，也就是说对他们的操作可以使⽤位移和加法来替换机器中很慢的乘法操作；
manhunt有些代码，⽐如这个，他们是⾃⼰实现的哈希函数。
，⽤于实现、等；
，⽤于处理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(m|SIGMA|)个条⽬，我们通过计算PI进⽽在预处理时间保存|SIGMA|的系 数，⽽⾮计算DELTA。
[1] Cormen, Leirson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press
[2] See finite automation theory
南京青少年夏令营
Boyer-Moore模式匹配，如下是引⽤和对其他算法的使⽤建议；
Boyer-Moore字符串匹配算法:
注意：由于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处理器中使⽤了随机替换策略；why so rious什么梗
被⽤于⼀些IBM的存储控制中，由于在PostgreSQL只有简单的应⽤；
Knuth在TAOCP第⼀卷中提到的被⽤于Linux内核中，FreeBSD和都在使⽤jemalloc并发分配器；
*nix系统中的核⼼组件
grep和awk都实现了使⽤Thompson-McNaughton-Yamada构建算法实现从正则表达式中创建NFA；
tsort实现了拓扑排序；over the love
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 Clau Learning）
⾃2000年以来，在⼯业标准中的SAT（布尔满⾜性问题）求解器的运⾏时间每年都在成倍减少。这⼀发展的⼀个⾮常重要的原因是冲突驱动条款学习算 法（Conflict Driven Clau Learning）的使⽤，它结合了Davis Logemann和Loveland的约束编程和⼈⼯智能研究技术的原始论⽂中关于布尔约束传播的算法。具体来说，⼯业建模中SAT被认为是⼀个简单的问 题（）。对我来说，这是近代最伟⼤的成功故事之⼀，因为它结合了先进的算法、巧妙的设计思路、实验反馈，并以⼀致的共同努⼒来解决这个问题。。许多⼤学都在教授这个算法，但通常是在逻辑或形式化⽅法的课程中。
微博热议
Databricks⼤数据公司联合创始⼈⾸先并在微博上传播了这个内容：
⼤家也纷纷发表了⾃⼰的看法：
：
所谓的算法实现就跟背书⼀样，所以如果不是为了学习语法，千万不要看那些带代码的编程书，或者编程书⾥⾯的代码。以学习为⽬的的话，东西就⾃⼰做，然后⾃⼰⽤，⽤出翔了，你就知道他为什么不好了。
：
说算法没啥⽤的⼈基本上说明他只在简单的堆砌业务功能代码的井底中。
：
我⼀直觉得在讲述每⼀个技术前，最好先让⼤家知道这个技术能⼲什么，曾经⼲过什么，将来或许能⽤在什么地⽅。这会增加⼤家对技术的兴趣、理解和灵活运⽤，会让⼤家学的更好。这挺重要
