QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2829|回复: 7
打印 上一主题 下一主题

(来自:Linux中国) 那些算法在哪里?

[复制链接]
字体大小: 正常 放大
sdccumcm 实名认证      会长俱乐部认证 

59

主题

165

听众

5484

积分

升级  9.68%

  • TA的每日心情
    开心
    2015-9-28 12:07
  • 签到天数: 832 天

    [LV.10]以坛为家III

    2012挑战赛参赛者

    邮箱绑定达人 发帖功臣 新人进步奖 风雨历程奖 最具活力勋章

    群组MCM优秀论文解析专题

    群组2012第二期MCM/ICM优秀

    群组科学狂想曲

    群组第二届数模基础实训

    群组学术交流B

    跳转到指定楼层
    1#
    发表于 2013-12-1 18:45 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta |邮箱已经成功绑定
    本文来源于一篇stackexchange的问题回答。提问者问到,我们在计算机科学和数学课程里面学习到的那些算法,到底在什么地方用到了?结果Vijay D给出一个洋洋洒洒的深入回答,得到了提问者和众多围观。我们将这篇回答翻译过来以飨读者。




    Vijay D写到:
    在我看来,一个系统背后主要发挥作用的算法更容易在非算法课程上找到,这和应用数学中的成果比理论数学中更容易出现在应用中是一个道理。在讲座中,很少有实际问题能够精确匹配到一个抽象问题。归根结底,我认为没有理由让流行的算法课程,诸如Strassen乘法,AKS素性测试、或者Moser-Tardos算法与底层实际问题,如实现视频数据库、优化的编译器、操作系统、网络拥堵控制系统或者其他系统相关。这些课程的价值是学习利用错综复杂的方法发现问题的脉络而找出有效的解决方案。高级算法和简单算法的分析都不简单。正是由于这个原因,我不会忽略简单随机算法或者PageRank。
    我想你可以选择任何一个大型软件,并在内部找到它所采用的基础和高级的算法。作为一个研究案例,我选择了Linux内核,并会示例一些Chromium里面的例子。
    Linux内核中的基本数据结构和算法Linux内核(源代码的链接在github)。
    1.链表双向链表无锁链表
    2.B+ 树,这是一些你无法在教科书上找到的说明。
    一个相对简单的B+树的实现。我把它作为一个学习练习来帮助理解B+树是如何工作的。这同样也被证明是有用的。
    ...
    一个在教科书中并不常见的技巧。最小的值在右侧而不是在左侧。所有在一个节点里用到的槽都在左侧,所有没有用到的槽包含了空值(NUL)。大多数操作只简单地遍历所有的槽一次并在第一个空值时(NUL)终止。
    3.优先排序列表 用于 互斥量驱动等等。
    4.红黑树用于调度、虚拟内存管理、追踪文件描述符和目录项等。
    5.区间树
    6.根树用于内存管理,NFS相关查询和网络相关功能。
    根树的一个通用的用处是存储指针到结构页中。
    7.优先级堆,如其名称的教科书实现,用于cgroup
    《简单的基于CLR的只插入的,含有指针的定长优先级堆》第七章
    8.哈希函数,参考了Knuth和一篇论文。
    Knuth建议,用乘法哈希的机器字来表示接近黄金比例的素数的最大整数。Chuck Lever验证了该技术的有效性:
    http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
    这些素数的选择是位稀疏的,他们可以通过移位和加法操作,而不必使用乘法器,乘法器是很慢的。
    9.有的代码,比如这个驱动,实现了他们自己的哈希函数。
    使用了一种旋转哈希算法的哈希函数
    Knuth, D. 《计算机程序设计艺术, 卷 3: 排序与搜索》, 第6、7章. Addison Wesley, 1973
    10.哈希表用于实现inode文件系统完整性检测等等。
    11.位数组用于处理标志位、中断等等。并在Knuth那本书的卷4中阐述。
    12.信号量自旋锁
    13.二分查找用于中断处理,寄存器缓存查询等等。
    14.B树的二分查找
    15.深度优先搜索被广泛地用于目录配置中
    执行一个修改过的命名空间树的深度优先遍历,以指定的start_handle节点开始(及结束)。回调函数会在任何一个参数匹配的节点被发现时被调用。如果回调函数返回了一个非0值,搜索将会立即终止并且将其返回给调用者。
    16.广度优先搜索用于检测运行时锁定的正确性。
    17.链表中的归并排序用于垃圾收集文件系统管理等等。
    18.冒泡排序在一个驱动库中也有一个令人惊讶的实现。
    19.Knuth-Morris-Pratt 字符串匹配,
    根据Knuth、Morris和Pratt[1]实现了一个线性时间的字符串匹配算法。他们的算法避免了转换函数的显式地计算DELTA。对于长度为n的文本,其匹配时间是O(n),对于长度为m的模式(pattern),仅使用一个辅助函数PI[1 . .m],预先计算模式的时间为O(m)。数组PI允许转换函数DELTA被实时有效地计算。粗略地说,对于任何状态"q"= 0,1,…、m和在SIGMA中的任何字符"a",PI["q"]的值包含的信息是独立的"a"并需要计算DELTA("q","a") [2]。既然PI只有m个记录,而DELTA有O(m |SIGMA|)个记录,在预处理时间计算PI而不是DELTA的时候,我们可以节省一个因数|SIGMA|
    [1] Cormen, Leiserson, Rivest, Stein,算法介绍,第二版,MIT出版社
    [2] 见有限自动机原理
    20.Boyer-Moore 模式匹配是在找替代品时的参考和建议。
    实现了Boyer-Moore字符串匹配算法:
    [1] 《一个快速的字符串搜索算法》,R.S. Boyer and Moore.计算机通信协会,20(10), 1977, pp. 762-772. http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf
    [2] 《准确的字符串匹配算法手册》,Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
    注:由于Boyer-Moore(BM)从右到左搜索匹配,仍然有可能匹配分布在多个块,在这种情况下该算法并没有优势。
    如果你希望确保这样的事情永远不会发生,那使用Knuth-Pratt-Morris(KMP)实现。总之,根据您的设置适当地选择字符串搜索算法。
    如果你正在用文本搜索器进行过滤,NIDS或任何类似的注重安全的目的,那么使用KMP。否则,如果你真的关心性能,并且你对数据包进行分类以使用服务质量(QoS)政策,当你不介意匹配可能分布分散,那么用BM。

    zan
    已有 1 人评分体力 收起 理由
    woaixueshumo + 180 很不错的,鼓励共享。

    总评分: 体力 + 180   查看全部评分

    转播转播0 分享淘帖0 分享分享2 收藏收藏0 支持支持0 反对反对0 微信微信
    Learn from yesterday, live for today, hope for tomorrow. 借鉴昨天,活在今天,憧憬明天。
    sdccumcm 实名认证      会长俱乐部认证 

    59

    主题

    165

    听众

    5484

    积分

    升级  9.68%

  • TA的每日心情
    开心
    2015-9-28 12:07
  • 签到天数: 832 天

    [LV.10]以坛为家III

    2012挑战赛参赛者

    邮箱绑定达人 发帖功臣 新人进步奖 风雨历程奖 最具活力勋章

    群组MCM优秀论文解析专题

    群组2012第二期MCM/ICM优秀

    群组科学狂想曲

    群组第二届数模基础实训

    群组学术交流B

    回复

    使用道具 举报

    2

    主题

    5

    听众

    2259

    积分

    升级  8.63%

  • TA的每日心情
    开心
    2014-3-13 13:05
  • 签到天数: 273 天

    [LV.8]以坛为家I

    自我介绍
    现在开始要踏踏实实学习了哦

    群组第四届cumcm国赛实训

    群组MATLAB与数模算法实训

    群组学术交流A

    回复

    使用道具 举报

    1104

    主题

    5

    听众

    132

    积分

    升级  16%

  • TA的每日心情
    开心
    2015-5-30 18:22
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    邮箱绑定达人

    群组学术交流A

    回复

    使用道具 举报

    1104

    主题

    5

    听众

    132

    积分

    升级  16%

  • TA的每日心情
    开心
    2015-5-30 18:22
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    邮箱绑定达人

    群组学术交流A

    回复

    使用道具 举报

    sdccumcm 实名认证      会长俱乐部认证 

    59

    主题

    165

    听众

    5484

    积分

    升级  9.68%

  • TA的每日心情
    开心
    2015-9-28 12:07
  • 签到天数: 832 天

    [LV.10]以坛为家III

    2012挑战赛参赛者

    邮箱绑定达人 发帖功臣 新人进步奖 风雨历程奖 最具活力勋章

    群组MCM优秀论文解析专题

    群组2012第二期MCM/ICM优秀

    群组科学狂想曲

    群组第二届数模基础实训

    群组学术交流B

    Learn from yesterday, live for today, hope for tomorrow. 借鉴昨天,活在今天,憧憬明天。
    回复

    使用道具 举报

    2

    主题

    5

    听众

    2259

    积分

    升级  8.63%

  • TA的每日心情
    开心
    2014-3-13 13:05
  • 签到天数: 273 天

    [LV.8]以坛为家I

    自我介绍
    现在开始要踏踏实实学习了哦

    群组第四届cumcm国赛实训

    群组MATLAB与数模算法实训

    群组学术交流A

    回复

    使用道具 举报

    1

    主题

    7

    听众

    65

    积分

    升级  63.16%

  • TA的每日心情
    郁闷
    2014-2-10 09:43
  • 签到天数: 15 天

    [LV.4]偶尔看看III

    群组各种优秀论文集锦

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2025-5-12 18:29 , Processed in 0.924358 second(s), 96 queries .

    回顶部