本文共 3753 字,大约阅读时间需要 12 分钟。
近日在Stackexchange上提了这样的一个,他希望有人能够列举一些目前软件、硬件中正在使用的算法的实际案例来证明算法的重要性,对于大家可能给到的回答,他还提出了几点要求:
的回复获得了最佳答案,他的具体回复内容如下:
,代码中的注释将会告诉你一些教科书中不能学到的内容:
这是一个简单的B+树实现,我写它的目的是作为练习,并以此了解B+树的工作原理。结果该实现发挥了它的实用价值。
...
一个不经常在教科书中提及的技巧:最小值应该放在右侧,而不是左侧。一个节点内所有被使用的槽位应该在左侧,没有使用的节点应该为NUL,大部分的操作只遍历一次所有的槽位,在第一个NUL处终止。
用于、等;
radix树的一个常见的用法是保存页面结构体的指针;
包含指针的只允许简单插入的静态大小优先级堆,基于CLR(算法导论)第七章
哈希函数,引用Knuth和他的一篇论文:
Knuth建议选择与机器字长所能表达的最大整数约成黄金比例的素数来做乘法散列,Chuck Lever 证实了这个技术的有效性;
这些选择的素数是位稀疏的,也就是说对他们的操作可以使用位移和加法来替换机器中很慢的乘法操作;
有些代码,比如这个,他们是自己实现的哈希函数
在命名空间树中执行一个修改过的深度优先算法,开始(和终止于)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, 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。
此树会被分配策略参数化,这个策略负责在C的自由存储空间和区域中分配列表,参见zone.h
同时,代码中还包含了一些第三方的算法和数据结构,例如:
为GIF图片格式而出现的Lempel-Zivsraf算法在图片处理程序中经常被应用,从一个简单的*nix组件转化为一个复杂的程序;
运行长度编码被用于生成PCX文件(用于Paintbrush这个程序中),压缩BMP文件和TIFF文件;
小波压缩(Wavelet压缩)是JPEG 2000的基础,所以所有生成JPEG 2000文件的数码相机都是实现了这个算法;
Reed-Solomon纠错用于、CD驱动、条形码读取,并且结合卷积从航行团队进行图片传输;
自2000年以来,在工业标准中的SAT(布尔满足性问题)求解器的运行时间每年都在成倍减少。这一发展的一个非常重要的原因是冲突驱动条款学习算法(Conflict Driven Clause Learning)的使用,它结合了Davis Logemann和Loveland的约束编程和人工智能研究技术的原始论文中关于布尔约束传播的算法。具体来说,工业建模中SAT被认为是一个简单的问题()。对我来说,这是近代最伟大的成功故事之一,因为它结合了先进的算法、巧妙的设计思路、实验反馈,并以一致的共同努力来解决这个问题。。许多大学都在教授这个算法,但通常是在逻辑或形式化方法的课程中。
Databricks大数据公司联合创始人首先并在微博上传播了这个内容:
很多学生和软件工程师都会好奇自己过去学习的算法有什么实际应用的价值。这个StackExchange的回答列出了各种经典算法在几个开源项目中的应用。 作者罗列出了从最基础的hash table到字符串匹配和加密算法等在Chromium和Linux内核的代码。查看开源代码是学习算法实现一个好途径。
大家也纷纷发表了自己的看法:
:
所谓的算法实现就跟背书一样,所以如果不是为了学习语法,千万不要看那些带代码的编程书,或者编程书里面的代码。以学习为目的的话,东西就自己做,然后自己用,用出翔了,你就知道他为什么不好了。
:
说算法没啥用的人基本上说明他只在简单的堆砌业务功能代码的井底中。
:
我一直觉得在讲述每一个技术前,最好先让大家知道这个技术能干什么,曾经干过什么,将来或许能用在什么地方。这会增加大家对技术的兴趣、理解和灵活运用,会让大家学的更好。这挺重
原始问题链接:
感谢吴峰光对本文的审校。
转载地址:http://ecrsi.baihongyu.com/