那些算法在哪裡？

在我看來，一個系統背後主要發揮作用的算法更容易在非算法課程上找到，這和應用數學中的成果比理論數學中更容易出現在應用中是一個道理。在講座中，很少有實際問題能夠精确比對到一個抽象問題。歸根結底，我認為沒有理由讓流行的算法課程，諸如strassen乘法，aks素性測試、或者moser-tardos算法與底層實際問題，如實作視訊資料庫、優化的編譯器、作業系統、網絡擁堵控制系統或者其他系統相關。這些課程的價值是學習利用錯綜複雜的方法發現問題的脈絡而找出有效的解決方案。進階算法和簡單算法的分析都不簡單。正是由于這個原因，我不會忽略簡單随機算法或者pagerank。

我想你可以選擇任何一個大型軟體，并在内部找到它所采用的基礎和進階的算法。作為一個研究案例，我選擇了linux核心，并會示例一些chromium裡面的例子。

<a target="_blank"></a>

一個相對簡單的b+樹的實作。我把它作為一個學習練習來幫助了解b+樹是如何工作的。這同樣也被證明是有用的。 ... 一個在教科書中并不常見的技巧。最小的值在右側而不是在左側。所有在一個節點裡用到的槽都在左側，所有沒有用到的槽包含了空值(nul)。大多數操作隻簡單地周遊所有的槽一次并在第一個空值時(nul)終止。

根樹的一個通用的用處是存儲指針到結構頁中。

《簡單的基于clr的隻插入的，含有指針的定長優先級堆》第七章

knuth建議，用乘法哈希的機器字來表示接近黃金比例的素數的最大整數。chuck lever驗證了該技術的有效性： <a target="_blank">http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf</a> 這些素數的選擇是位稀疏的，他們可以通過移位和加法操作，而不必使用乘法器，乘法器是很慢的。

使用了一種旋轉雜湊演算法的哈希函數 knuth, d. 《計算機程式設計藝術, 卷 3: 排序與搜尋》, 第6、7章. addison wesley, 1973

執行一個修改過的命名空間樹的深度優先周遊，以指定的start_handle節點開始（及結束）。回調函數會在任何一個參數比對的節點被發現時被調用。如果回調函數傳回了一個非0值，搜尋将會立即終止并且将其傳回給調用者。

根據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] 見有限自動機原理

實作了boyer-moore字元串比對算法: 注:由于boyer-moore(bm)從右到左搜尋比對，仍然有可能比對分布在多個塊，在這種情況下該算法并沒有優勢。 如果你希望確定這樣的事情永遠不會發生，那使用knuth-pratt-morris(kmp)實作。總之，根據您的設定适當地選擇字元串搜尋算法。 如果你正在用文本搜尋器進行過濾，nids或任何類似的注重安全的目的，那麼使用kmp。否則，如果你真的關心性能，并且你對資料包進行分類以使用服務品質(qos)政策，當你不介意比對可能分布分散，那麼用bm。

這個樹通過配置設定政策（配置設定器）參數化。這個政策用于c的可用存儲區的清單配置設定，參見zone.h。

在chromium的第三方代碼裡面也有如下的資料結構和算法。

julian walker的總結 紅黑樹是一個有趣的小東西。他們被認為比avl樹(它們的直接競争對手)簡單，乍一看這似乎是由于插入是一項輕松的樂事。然而，當你開始删除時，紅黑樹變得非常棘手。然而，通過複雜性的平衡，插入和删除可以使用單通道，實作自上而下的算法。這與avl樹情況不一樣，插入隻能自頂向下，删除則需要自下而上。 紅黑樹是很流行的，像大多數資料結構一樣有一個古怪的名字。比如，在java和c++庫映射結構通常用紅黑樹實作。紅黑樹的速度也與avl樹相當。而avl樹平衡性不是很好，需要保持平衡的話紅黑樹通常更好。有一些流傳的誤解，但在大多數情況下對紅黑樹的宣傳是準确的。

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

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

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

3.fifo的一個變種用于vax/vms系統。

5.intel i860處理器是一種随機替代政策。

2.tsort實作了拓撲排序。

5.unix上的crypt(1)實作了一個在enigma機器上的不同加密算法。

這本是一個非常長的清單。加密算法在所有執行安全通信和交易的程式中都有實作。

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

3.lex和flex将正規表達式編譯為nfa。

2.行程長度編碼用于産生pcx檔案(用于原來的畫筆程式)，它是被壓縮的bmp和tiff檔案。

3.小波壓縮是jpeg2000的基礎，是以所有生成jpeg2000檔案的數位相機會支援這個算法。

原文釋出時間為：2013-11-30

本文來自雲栖社群合作夥伴“linux中國”