赞
踩
近日Emanuele Viola在Stackexchange上提了这样的一个问题,他希望有人能够列举一些目前软件、硬件中正在使用的算法的实际案例来证明算法的重要性,对于大家可能给到的回答,他还提出了几点要求:
Vijay D的回复获得了最佳答案,他的具体回复内容如下:
这是一个简单的B+树实现,我写它的目的是作为练习,并以此了解B+树的工作原理。结果该实现发挥了它的实用价值。
…
一个不经常在教科书中提及的技巧:最小值应该放在右侧,而不是左侧。一个节点内所有被使用的槽位应该在左侧,没有使用的节点应该为NUL,大部分的操作只遍历一次所有的槽位,在第一个NUL处终止。
这些选择的素数是位稀疏的,也就是说对他们的操作可以使用位移和加法来替换机器中很慢的乘法操作;
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字符串匹配算法:
[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。
此树会被分配策略参数化,这个策略负责在C的自由存储空间和区域中分配列表,参见zone.h
同时,代码中还包含了一些第三方的算法和数据结构,例如:
自2000年以来,在工业标准中的SAT(布尔满足性问题)求解器的运行时间每年都在成倍减少。这一发展的一个非常重要的原因是冲突驱动条款学习算 法(Conflict Driven Clause Learning)的使用,它结合了Davis Logemann和Loveland的约束编程和人工智能研究技术的原始论文中关于布尔约束传播的算法。具体来说,工业建模中SAT被认为是一个简单的问 题(见讨论)。对我来说,这是近代最伟大的成功故事之一,因为它结合了先进的算法、巧妙的设计思路、实验反馈,并以一致的共同努力来解决这个问题。Malik和Zhang的CACM论文是一个很好的阅读材料。许多大学都在教授这个算法,但通常是在逻辑或形式化方法的课程中。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。