實際項目中的常見算法
本文原始內容來源于 stackexchange，遵循 cc-wiki 協議；
近日 Emanuele Viola 在 Stackexchange 上提了這樣的一個問題，他希望有人能夠列舉一些目前軟件、硬件中正在使用的算法的實際案例來證明算法的重要性，對于大家可能給到的回答，他還提出了幾點要求：
- 使用這些算法的軟件或者硬件應該是被廣泛應用的；
- 例子需要具體，并給出確切的系統、算法的引用地址；
- 在經典的本科生或者博士的課程中應該教過這些算法或者數據結構； </ol>
- 鏈表、雙向鏈表和無鎖鏈表
-
B+ 樹，代碼中的注釋將會告訴你一些教科書中不能學到的內容：
這是一個簡單的B+ 樹實現，我寫它的目的是作為練習，并以此了解B+ 樹的工作原理。結果該實現發揮了它的實用價值。
...
一個不經常在教科書中提及的技巧：最小值應該放在右側，而不是左側。一個節點內所有被使用的槽位應該在左側，沒有使用的節點應該為 NUL，大部分的操作只遍歷一次所有的槽位，在第一個 NUL 處終止。
</blockquote> </li>- </li>
- 紅黑樹用于調度、虛擬內存管理、跟蹤文件描述符和目錄條目等；
- 區間樹
- Radix 樹，用于內存管理、NFS 相關查找和網絡相關的功能；
radix 樹的一個常見的用法是保存頁面結構體的指針；
</blockquote> </li>- 優先級堆，文字上的描述，主要是在教科書中實現，用于 control group 系統;
包含指針的只允許簡單插入的靜態大小優先級堆，基于 CLR（算法導論）第七章
</blockquote> </li>哈希函數，引用 Knuth 和他的一篇論文：
Knuth 建議選擇與機器字長所能表達的最大整數約成黃金比例的素數來做乘法散列，Chuck Lever 證實了這個技術的有效性；
http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
這些選擇的素數是位稀疏的，也就是說對他們的操作可以使用位移和加法來替換機器中很慢的乘法操作；
</blockquote> </li>有些代碼，比如這個驅動，他們是自己實現的哈希函數
</li>- 哈希表，用于實現索引節點、文件系統完整性檢查等；
- 位數組，用于處理 flags、中斷等，在 Knuth 第四卷中有對其特性的描述；
- Semaphores 和 spin locks
- 二叉樹搜索用于中斷處理、登記緩存查找等；
- 使用B-樹進行二叉樹查找；
- 深度優先搜索和他的變體被應用于目錄配置；
在命名空間樹中執行一個修改過的深度優先算法，開始（和終止于）start_handle 所確定的節點。當與參數匹配的節點被發現以后，回調函數將會被調用。如果回調函數返回一個非空的值，搜索將會立即終止，這個值將會回傳給調用函數；
</blockquote> </li>- 廣度優先搜索用于在運行時檢查鎖的正確性；
- 鏈表上的合并排序用于垃圾回收、文件系統管理等；
- 在某個驅動程序的庫函數里，冒泡排序居然也被實現了
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(mSIGMA)個條目，我們通過計算 PI 進而在預處理時間保存 SIGMA 的系數，而非計算 DELTA。
[1] Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press
[2] See finite automation theory
</blockquote> </li>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。
</blockquote> </li> </ol>Chromium 瀏覽器中的數據結構和算法
- 伸展樹
此樹會被分配策略參數化，這個策略負責在C的自由存儲空間和區域中分配列表，參見 zone.h
</blockquote> </li>- Demo 中使用了 Voronoi 圖
- 基于 Bresenham 算法的標簽管理
</ol>同時，代碼中還包含了一些第三方的算法和數據結構，例如：
- 二叉樹
- 紅黑樹
- AVL 樹
- 用于壓縮的 Rabin-Karp 字符串匹配
- 計算自動機的后綴
- 蘋果實現的布隆過濾器
- 布氏算法 </ol>
- C++ STL，包含的有列表、堆、棧、向量、排序、搜索和堆操作算法
- Java API 非常廣泛，包含的太多
- Boost C++ 類庫，包含了諸如 Boyer-Moore 和 Knuth-Morris-Pratt 字符串匹配算法等； </ol>
- 最近最少使用算法有多種實現方式，在 Linux 內核中是基于列表實現的；
- 其他可能需要了解的是先入先出、最不常用和輪詢；
- VAX、VMS 系統中大量使用 FIFO 的變體；
- Richard Carr 的時鐘算法被用于 Linux 中頁面幀替換；
- Intel i860 處理器中使用了隨機替換策略；
- 自適應緩存替換被用于一些 IBM 的存儲控制中，由于專利原因在 PostgreSQL 只有簡單的應用；
- Knuth 在 TAOCP 第一卷中提到的伙伴內存分配算法被用于 Linux 內核中，FreeBSD 和 非死book 都在使用 jemalloc 并發分配器； </ol>
- 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 版本被用來計算最短編輯距離； </ol>
- Merkle 樹，尤其是 Tiger Tree Hash 的變種，用于點對點的程序，例如 GTK Gnutella 和 LimeWire;
- MD5用于為軟件包提供校驗碼，還用于*nix 系統（Linux 實現）中的完整性校驗，同時他還支持 Windows 和 OS X 系統；
- OpenSSL 實現了需要加密算法，諸如 AES，Blowfish，DES，SHA-1，SHA-2，RSA，DES 等； </ol>
- yacc 和 bison 實現了 LALR 解析器
- 支配算法用于基于 SSA 形式的最優化編譯器；
- lex 和 flex 將正則表達式編譯為 NFA； </ol>
-
為 GIF 圖片格式而出現的 Lempel-Zivsraf 算法在圖片處理程序中經常被應用，從一個簡單的*nix 組件轉化為一個復雜的程序；
</li> -
運行長度編碼被用于生成 PCX 文件（用于 Paintbrush 這個程序中），壓縮 BMP 文件和 TIFF 文件；
</li> -
小波壓縮（Wavelet 壓縮）是 JPEG 2000 的基礎，所以所有生成 JPEG 2000 文件的數碼相機都是實現了這個算法；
</li> -
Reed-Solomon 糾錯用于 Linux 內核、CD 驅動、條形碼讀取，并且結合卷積從航行團隊進行圖片傳輸；
</li> </ol>沖突驅動條款學習算法（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 內核的代碼。查看開源代碼是學習算法實現一個好途徑。
</blockquote>大家也紛紛發表了自己的看法：
所謂的算法實現就跟背書一樣，所以如果不是為了學習語法，千萬不要看那些帶代碼的編程書，或者編程書里面的代碼。以學習為目的的話，東西就自己做，然后自己用，用出翔了，你就知道他為什么不好了。
</blockquote>說算法沒啥用的人基本上說明他只在簡單的堆砌業務功能代碼的井底中。
</blockquote>我一直覺得在講述每一個技術前，最好先讓大家知道這個技術能干什么，曾經干過什么，將來或許能用在什么地方。這會增加大家對技術的興趣、理解和靈活運用，會讓大家學的更好。這挺重
</blockquote>原始問題鏈接：Core algorithms deployed
感謝吳峰光對本文的審校。
來自: InfoQ<span id="shareA4" class="fl"> </span>本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
編程語言類庫
分配和調度算法
*nix 系統中的核心組件
加密算法
編譯器
壓縮和圖片處理
Vijay D 的回復獲得了最佳答案，他的具體回復內容如下：
Linux 內核中的基本數據結構和算法