那些演算法在哪裡？

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。

Chromium 瀏覽器中的數據結構和演算法

Chromium的(源代碼在 Google code)。我只會列出一部分。我建議使用搜索來找到你最喜歡的演算法或者數據結構。

1.伸展樹。

這個樹通過分配策略（分配器）參數化。這個策略用於C的可用存儲區的列表分配，參見zone.h。

2.Voronoi演算法用於一個示例。

3.基於Bresenham演算法的選項卡

在Chromium的第三方代碼裡面也有如下的數據結構和演算法。

1.二叉樹

2.紅黑樹

Julian Walker的總結

紅黑樹是一個有趣的小東西。他們被認為比AVL樹(它們的直接競爭對手)簡單，乍一看這似乎是由於插入是一項輕鬆的樂事。然而，當你開始刪除時，紅黑樹變得非常棘手。然而，通過複雜性的平衡，插入和刪除可以使用單通道，實現自上而下的演算法。這與AVL樹情況不一樣，插入只能自頂向下，刪除則需要自下而上。

...

紅黑樹是很流行的，像大多數數據結構一樣有一個古怪的名字。比如，在Java和c++庫映射結構通常用紅黑樹實現。紅黑樹的速度也與AVL樹相當。而AVL樹平衡性不是很好，需要保持平衡的話紅黑樹通常更好。有一些流傳的誤解，但在大多數情況下對紅黑樹的宣傳是準確的。

3.AVL 樹

4.Rabin-Karp字元串匹配用於比較。

5.自動機後綴的計算。

6.由Apple公司實現的bloom過濾器。

7.Bresenham 演算法。

編程語言庫

我想這個問題值得思考。編程語言設計者們認為值得花一些工程師的時間和精力來實現這些數據結構和演算法，這樣其他人就不必這麼做了。這些庫是我們在JAVA裡面比C更少的發現需要重新實現基本數據結構的部分原因。

1.C++ STL包含了鏈表、棧、隊列、映射、向量和排序、搜索和堆操作演算法。

2.Java API易於擴展的並且越來越多。

3.Boost C++ 庫包含了像 Boyer-Moore以及Knuth-Morris-Pratt字元串匹配演算法。

分配和調度演算法

我發現這些很有趣，因為即使他們被稱為啟發式，您使用的策略規定了演算法類型和需要的數據結構，因此，所以需要人們知道棧和隊列。

1.最近最少使用（LRU）演算法可以用不同的方法實現。Linux內核有一種基於列表的實現。

2.其他的還有先入先出（FIFO）、最常使用和輪詢。

3.FIFO的一個變種用於VAX/VMS系統。

4.Richard Carr的時鐘演算法用於Linux中的頁面替換。

5.Intel i860處理器是一種隨機替代策略。

6.自適應置換高速緩存用於一些IBM存儲控制器中，也曾經用於PostgreSQL中(雖然僅僅因為一些專利問題）。

7.Knuth在《計算機程序設計藝術 卷1》中討論過的Buddy內存分配演算法內用於Linux內核中，jemalloc並發分配器被用於FreeBSD和facebook中。

*nix系統核心工具

1.grep和awk同時從正則表達式中實現NFA的Thompson-McNaughton-Yamada構造，顯然這甚至擊敗了Perl的實現。

2.tsort實現了拓撲排序。

3.fgrep實現了Aho-Corasick字元串匹配演算法。

4.GNU grep，根據作者Mike Haertel實現了Boyer-Mooresuan演算法。

5.Unix上的crypt(1)實現了一個在Enigma機器上的不同加密演算法。

6.Unix diff由Doug McIllroy實現，基於和James Hunt合作編寫的原形。它比用於計算Levenshtein距離的標準動態規劃演算法執行地更好。Linux 版本計算最短編輯距離。

加密演算法

這本是一個非常長的列表。加密演算法在所有執行安全通信和交易的程序中都有實現。

1.Merkle 樹，特別是 Tiger Tree Hash變種，被用於點對點應用，比如GTK Gnutella和LimeWire。

2.MD5被用於提供軟體包的校驗和並被用於在*nix系統上的完整性檢測(Linux 實現)，同樣也支持Windows和OSX。

3.OpenSSL實現了很多加密演算法包括AES、Blowfish、DES、SHA-1、SHA-2、RSA、DES等等。

編譯器

1.LALR 解析在yacc和bison實現。

2.支配演算法被用於大多數基於SSA形式的編譯器優化。

3.lex和flex將正則表達式編譯為NFA。

壓縮和圖像處理

1.用於GIF圖片格式的Lempel-Ziv演算法在圖像處理程序中實現，從*unix工具轉化到複雜的程序。

2.行程長度編碼用於產生PCX文件(用於原來的畫筆程序)，它是被壓縮的BMP和TIFF文件。

3.小波壓縮是JPEG2000的基礎，所以所有生成JPEG2000文件的數碼相機會支持這個演算法。

4.Reed-Solomon糾錯在Linux內核、CD驅動器、條形碼讀取器、結合從Voyager中的卷積圖像傳輸中實現。

衝突驅動語句學習演算法 (CDCL)

自2000年以來，SAT求解器在工業標準的運行時間(通常是硬體工業，雖然其他地方也被使用)以近乎指數的方式每年下跌。這發展中很重要的一部分是衝突驅動語句學習演算法，它結合了Davis Logemann和Loveland在約束規劃和人工智慧研究中關於語句學習的原始論文中的布爾約束傳播演算法。特定地，工業造型，SAT被認為是一個簡單的問題(見這個討論)。對我而言，這個一個最近最好的成功故事，因為它結合了這幾年演算法的不斷發展、清晰的工程理念、實驗性的評估、齊心協力地解決一個問題。Malik 和 Zhang的CACM文章值得閱讀。這個演算法在許多大學中教授(我參加過的4個地方都是如此)，但是通常在一個邏輯或者形式方法課上。

SAT求解器的應用有很多。IBM，Intel和許多其他公司都有他們的SAT求解器實現。OpenSuse的包管理器同樣使用了一個SAT求解器。

via: http://cstheory.stackexchange.com/questions/19759/core-algorithms-deployed/19773#19773

譯者：geekpi 校對：wxy

本文由 LCTT 原創翻譯，Linux中國 榮譽推出

本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive