常见算法在实际项目中的应用

标签: 程序员 算法 | 发表时间:2013-12-04 09:26 | 作者:wangjuanjuan
出处:http://blog.jobbole.com

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

  • 使用这些算法的软件或者硬件应该是被广泛应用的;
  • 例子需要具体,并给出确切的系统、算法的引用地址;
  • 在经典的本科生或者博士的课程中应该教过这些算法或者数据结构;

Vijay D的回复获得了最佳答案,他的具体回复内容如下:

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

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

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

  • 红黑树 用于调度、虚拟内存管理、跟踪文件描述符和目录条目等;
  • 区间树
  • Radix树,用于内存管理、NFS相关查找和网络相关的功能;

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

  • 优先级堆,文字上的描述,主要是在教科书中实现,用于 control group系统;

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

  • 哈希函数,引用Knuth和他的一篇论文:

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

    http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

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

  • 有些代码,比如这个 驱动,他们是自己实现的哈希函数。
  • 哈希表,用于实现 索引节点文件系统完整性检查等;
  • 位数组,用于处理flags、中断等,在Knuth第四卷中有对其特性的描述;
  • Semaphoresspin locks
  • 二叉树搜索用于 中断处理登记缓存查找等;
  • 使用B-树进行二叉树查找
  • 深度优先搜索和他的变体被应用于 目录配置

    在命名空间树中执行一个修改过的深度优先算法,开始(和终止于)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. 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。

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

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

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

编程语言类库

分配和调度算法

  • 最近最少使用算法有多种实现方式,在Linux内核中是基于 列表实现的;
  • 其他可能需要了解的是先入先出、最不常用和轮询;
  • VAX、VMS系统中大量使用FIFO的变体;
  • Richard Carr时钟算法被用于Linux中页面帧替换;
  • Intel i860处理器中使用了随机替换策略;
  • 自适应缓存替换被用于一些IBM的存储控制中,由于 专利原因在PostgreSQL只有简单的应用;
  • Knuth在TAOCP第一卷中提到的 伙伴内存分配算法被用于Linux内核中,FreeBSD和 Facebook都在使用jemalloc并发分配器;

*nix系统中的核心组件

  • grep和awk都实现了使用Thompson-McNaughton-Yamada构建算法实现从正则表达式中创建NFA;
  • tsort实现了拓扑排序;
  • fgrep实现了 Aho-Corasick 字符串匹配算法
  • GNU grep,据作者Mike Haertel所说, 实现了Boyer-Moore算法
  • Unix中的crypt(1)实现了 哑谜机(Enigma Machine)中的加密算法的变种;
  • Doug Mcllroy基于和James合作的原型实现的 Unix diff,比用来计算Levenshtein距离的标准动态规划算法更好,Linux版本被用来计算最短编辑距离;

加密算法

  • Merkle树,尤其是Tiger Tree Hash的变种,用于点对点的程序,例如 GTK GnutellaLimeWire;
  • MD5用于为软件包提供校验码,还用于*nix系统( Linux实现)中的完整性校验,同时他还支持Windows和OS X系统;
  • OpenSSL实现了需要加密算法,诸如AES,Blowfish,DES,SHA-1,SHA-2,RSA,DES等;

编译器

  • yacc和bison实现了 LALR解析器;
  • 支配算法用于基于SSA形式的最优化编译器;
  • lex和flex将正则表达式编译为NFA;

压缩和图片处理

  • 为GIF图片格式而出现的Lempel-Zivsraf算法在图片处理程序中经常被应用,从一个简单的*nix组件转化为一个复杂的程序;
  • 运行长度编码被用于生成PCX文件(用于Paintbrush这个程序中),压缩BMP文件和TIFF文件;
  • 小波压缩(Wavelet压缩)是JPEG 2000的基础,所以所有生成JPEG 2000文件的数码相机都是实现了这个算法;
  • Reed-Solomon纠错用于 Linux内核、CD驱动、条形码读取,并且结合卷积从航行团队进行图片传输;

冲突驱动条款学习算法(Conflict Driven Clause Learning)

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

微博热议

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

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

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

@GeniusVczh

所谓的算法实现就跟背书一样,所以如果不是为了学习语法,千万不要看那些带代码的编程书,或者编程书里面的代码。以学习为目的的话,东西就自己做,然后自己用,用出翔了,你就知道他为什么不好了。

@左耳朵耗子

说算法没啥用的人基本上说明他只在简单的堆砌业务功能代码的井底中。

@薛正华-中国科学院

我一直觉得在讲述每一个技术前,最好先让大家知道这个技术能干什么,曾经干过什么,将来或许能用在什么地方。这会增加大家对技术的兴趣、理解和灵活运用,会让大家学的更好。这挺重

常见算法在实际项目中的应用,首发于 博客 - 伯乐在线

相关 [算法 项目 应用] 推荐:

常见算法在实际项目中的应用

- - 博客 - 伯乐在线
近日Emanuele Viola在Stackexchange上提了这样的一个问题,他希望有人能够列举一些目前软件、硬件中正在使用的算法的实际案例来证明算法的重要性,对于大家可能给到的回答,他还提出了几点要求:. 使用这些算法的软件或者硬件应该是被广泛应用的;. 例子需要具体,并给出确切的系统、算法的引用地址;.

xssProject在java web项目中应用

- - Java - 编程语言 - ITeye博客
1.项目引入xssProtect-0.1.jar、antlr-3.0.1.jar、antlr-runtime-3.0.1.jar包. * 覆盖getParameter方法,将参数名和参数值都做xss过滤. * 如果需要获得原始的值,则通过super.getParameterValues(name)来获取<br/>.

在 Web 项目中应用 Apache Shiro

- - 企业架构 - ITeye博客
Apache Shiro 是功能强大并且容易集成的开源权限框架,它能够完成认证、授权、加密、会话管理等功能. 认证和授权为权限控制的核心,简单来说,“认证”就是证明你是谁. Web 应用程序一般做法通过表单提交用户名及密码达到认证目的. “授权”即是否允许已认证用户访问受保护资源. 关于 Shiro 的一系列特征及优点,很多文章已有列举,这里不再逐一赘述,本文重点介绍 Shiro 在 Web Application 中如何实现验证码认证以及如何实现单点登录.

Mozilla的新项目 —— 把 OpenGL 应用导出成 WebGL

- - HTML5研究小组
1月28日,Mozilla的工程师Ehsan Akhgari通过 WebGL公共邮件列表发布了他们正在做的一个新项目,它可以自动将使用C/C++编写的OpenGL应用导出成为使用JavaScript的WebGL应用. 这个项目是建立在一个免费开源的C/C++到JavaScript编译器—— Emscripten的基础上的,Mozilla的计划是将其扩展从而支持OpenGL.

《孙子兵法》在敏捷项目管理中的应用

- - 博客 - 伯乐在线
来源: 黄文海@ibm_developerWorks. 简介: 《孙子兵法》中的论述虽然是关于战争的,但是其思想在项目管理领域对我们也是有借鉴意义的. 本文以笔者的实际项目管理经验为基础,分享了《孙子兵法》在敏捷项目管理中的应用. 希望能够对读者的实际项目管理工作有所启发. 成为“敏捷”,而不是做“敏捷”.

再看知名应用背后的第三方开源项目

- - 移动开发 - ITeye博客
知名应用程序的设计和技术一直都是开发者需要学习的,同样这些应用所使用的开源框架也是不可忽视的一部分. 此前《 iOS第三方开源库的吐槽和备忘》中作者ibireme列举了国内多款知名应用所使用的开源框架,并对其中一些框架进行了分析,同样国外开发者 @iOSCowboy也在博客中给我们列出了国外多款知名应用使用的开源框架.

Java自定义异常在项目中的应用

- - Java - 编程语言 - ITeye博客
在Java的一些项目中,在需要提供对外接口时,常常会有必要自定义响应一些code和message(例:0000:Success,500:Error),特别是在对接移动端项目中最为常见. 为更加方便提供这些接口的程序员的开发,可以应用Java的自定义异常处理来实现. 现有一移动端应用,需要对接我们项目,其中有一个用户登录接口,其接口的请求和响应参数如下:.

浅谈Vue组件在实际项目中的应用

- - JDC | 京东设计中心
Vue.js 是一套构建用户界面的渐进式框架,目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件. 虽然目前 Vue 已经很火了,但不可否认的是,仍有很多人刚刚开始学习使用 Vue 来构建前端项目,从生疏的初学者到熟练运用 Vue 的过程中,不可避免地会走一些弯路. 为了实现某个功能,也许尝试过很多方法,最终蓦然回首,才发现当初犯下的错误是那么幼稚.

Android开发者应该深入学习的10个开源应用项目

- zjzxzhang - ITeye资讯频道
  Android开发带来新一轮热潮让很多移动开发者都投入到这个浪潮中去了,创造了许许多多相当优秀的应用. 其中也有许许多多的开发者提供了应用开 源项 目,贡献出他们的智慧和创造力. 学习开源代码是掌握技术的一个最佳方式. 下面推荐几个应用开源项目,这些项目不仅提供了优秀的创意,也可以直接掌握 Android内核的接口使用.