程式設計師雜談

  • 發行項

科學的電腦

Ted Neward
Joe Hummel, Ph.D

下載代碼示例

Ted Neward
許多年來，已經聽到同事自己描述為"電腦科學家"。此外聽說它說，"任何領域的研究，已放在名稱中的 '科學' 真的不科學"。相當多的人在我的領域當然有沒有正式的培訓，在電腦科學和另一個較大編號看輕蔑地走出高校和高校教授辦公室的工作 — — 與一些辯解的理由。最後一次大量的希臘符號看來描述類型系統説明你什麼時候該業務線應用程式啟動並運行？

我知道一些可笑聰明的人，和其中之一是喬 · 梅爾，一個人可以理直氣壯地宣佈標題的電腦科學家，由於博士後面他的名字和所有。我問他要和我一起在撰寫此專欄，探索科學的計算。我認為它會有趣開始時，一些簡單零件的電腦科學與工作如何理解這些部件的一些背後的理論可以，事實上，通過使您的生活作為程式師很讓人更好一點。

對於本文中，我們對付經典的"大 O"討論，旨在給我們以一致的方式來描述一個簡單的概念： 多少資源 （時間、 記憶體、 電源和等等） 將電腦需要執行一個給定的程式嗎？這種決心稱為演算法分析，目標是將你所選擇的演算法放到一個特定的數學類別。為什麼？因此，您可以選擇一種局面最好的一個。有很多類別，與每個連續的類別表示資源消耗的激增。我們將重點對執行時間和剛才的首三個類別： 複雜度、 O(lgN) 和 o (n)。由於是典型，N 表示的演算法所處理的資料項目的數目。在何處執行摘要，我們將與所有此，請參閱圖 1，其中突出顯示你可以期待每個類別，隨著 N 的執行時間。

Execution Times as the Number of Items Processed (N) Grows
圖 1 執行的專案數倍處理 (N） 的增長

N 階演算法是寫 o (n)、 宣告"大 O N"，亦稱以"線性"。鑒於 N 資料項目，o (n) 演算法採用 N 次步驟的順序。訂單日誌 N 演算法寫 O(lgN)，宣告"大 O N 日誌的"，並提到，"對數"。鑒於 N 資料項目，O(lgN) 演算法採用 log2(N) 時間步驟 （許多少） 的順序。最後，訂單 1 演算法是寫複雜度、 宣告"大 O 1 的"和稱為"恒"。為 N 的資料項目，複雜度演算法需要恒定數量的時間步驟 （仍少)。花一點時間來重新審視圖1。這張圖表可能傳達什麼呢？例如，請注意當 N 的兩倍，線性演算法需要兩倍的時間。

讓我們看看如何，這適用于現實生活中，和瞭解只一點點關於演算法分析可以造成巨大衝擊的示例。假設您正在考慮要搜索可疑 IP 位址的清單匹配的日誌檔。足夠簡單：

 

List<string> suspicious = BuildList(); /* step 0 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);         /* step 1 */
  if (suspicious.Contains(ipaddr))     /* step 2 */
    matches++;                         /* step 3 */
}

我們如何分類的時間複雜度的這種做法？ 讓我們假設有 M 線中的日誌檔和 N 可疑 IP 位址。 建築的 N 個元素 （第 0 步） 未排序的清單將會招致 o (n) 的一次性費用。 迴圈將執行 M 反覆運算，所以在迴圈的成本是 O (M ＊ 一次反覆運算的成本）。 每次反覆運算執行三個基本步驟：

  1. 解析行
  2. 搜索清單
  3. 如果找到一個匹配的增量匹配

獲取與它解析

要算什麼，什麼不該計數，學習演算法分析的智慧財產權方面。 解析一線時，例如 — — 或許應用一個正則運算式或拆分為標記的線 — — 可能是昂貴，它將持續的時間相對於資料。 換句話說，是否在檔中有米或 2 米線，仍然完全保持不變，分析一線所需的時間。 也不會改變是否有 N 或 2N 可疑的 IP 位址。 因此，我們說的步驟 1 和步驟 3 以 c (持續) 時。 然而，第 2 步，其中搜索清單中時，不會更改可疑 IP 位址的次數：

if (suspicious.Contains(ipaddr))

包含方法執行線性搜索，從第一個元素開始，搜索直至找到匹配項，或到達清單的末尾。 (怎知道這？ 三種方式之一： 我們測試它，我們看的原始程式碼或 MSDN 庫文檔資料告訴我們。）

使用亂數據，平均我們會搜索半清單，需要 N/2 步驟。 這將舉行對於大多數情況，但在這個特殊的情況下，一個更有力的論據是該日誌檔中的大多數 IP 位址是可信的因為我們的 Web 服務器並不是一家銀行或總統候選人的 Web 網站。 這意味著，而不在那兒被給定用戶端是不可靠的機會，絕大多數的搜索將排氣清單中沒有找到匹配項，需要 N 步驟。

因為常數下降計算的順序的事情時，搜索中任一情況下，產生的複雜性是 o (n) O(M * N) for 迴圈。 反過來，這將生成整體的複雜性：

= O(build + loop)
= O(N + M * N)
= O( (1 + M) * N )
= O(M * N)

因此，我們的解決方案的第 1 版需要 O(MN) 的時間。

' 資料，資料，資料 ！ 我不能沒有黏土做磚!'

問問自己的第一個問題是："我們需要一個更好的演算法嗎？"M 是通常很大，以百萬計 （可能高達數十億美元） 的行。 沒有太多你能做些什麼，因為你得去觸其進行搜索的每一行。 如果 N，可疑的 IP 位址的數目很小 （說，N < 100），然後你的工作完成。 用今天的快速的機器，有小可衡量和區別是 M 時間步驟 100 米時間的步驟。 然而，作為 N 越大 （例如，N >> 100、 或明顯大於 100），是值得考慮其他的搜索演算法的。

除非你有非常大的硬體預算，當然。 （有時，即使是這樣。）

更高效的演算法是二進位搜索，跳轉到中間，然後向左或右取決於您正在尋找的元素是中間元素少於或更大的搜索。 通過削減一半每個時間搜索空間，該演算法展品 O(lgN) 的行為。 在實踐中，這意味著什麼呢？ 給定的 N = 1，000 個元素，在最壞二進位搜索需要大約 10 次步驟 （210 ≈ 1,000），線性搜索的同時會採取 1,000。 N = 100 萬，不同之處在于更具戲劇性 — — 大約 20 次步驟來對比 100 萬。 關鍵需要權衡的是該二進位搜索要求要在排序次序中的資料。 這裡是重寫，使用二進位搜索的日誌檔搜索程式：

List<string> suspicious = BuildList();      /* step 0 */
suspicious.Sort();                          /* step 0.5 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);               /* step 1 */
  if (suspicious.BinarySearch(ipaddr) >= 0)  /* step 2 */
    matches++;                               /* step 3 */
}

排序的可疑清單 （步驟 0.5） 表示一次性費用，O(NlgN)，而每次反覆運算的成本從 o (n) 減少到 O(lgN) 提供更高效的二進位搜索 （步驟 2）。 這將生成整體的複雜性：

= O(build + sort + loop)
= O(N + N * lgN + M * lgN)
= O(N * (1 + lgN) + M * lgN)
= O(N * lgN + M * lgN)
= O((N + M) * lgN)

在我們的方案，如 M >> N，N 更像一個小的常數時添加到 M，於是我們的解決方案的第 2 版需要大約 O(MlgN) 時間。 所以呢？ N = 1,000 可疑的 IP 位址，我們只是減少執行時間從 1000 米的時間步驟的順序到 10 米，哪一個更快的 100 倍。 額外的排序時間的大約 10,000 時間步驟 （O(NlgN)) 是抵銷有餘反復儲蓄在搜索時間。

讓我們去雜湊演算法

當你瞭解您要搜索的資料時，您可以 （也應該） 生成的雜湊表。 雜湊將平均搜索時間減少到 O (1) — — 你不能做任何得更好。 這是通過創建的單個值存儲在表中，此值由雜湊函數的元素的映射來實現的。 雜湊演算法的關鍵要求是一個好的雜湊函數，將搜索資料對應範圍的整數，由幾個碰撞 （重複的映射） 的存在。 我們修訂的日誌檔程式 （版本 3） 利用內置的支援，在 Microsoft.net 框架中的雜湊演算法的有效字串：

Dictionary<string, int> suspicious = BuildHashTable();  /* step 0 */
foreach (string line in logfile)
{
  string ipaddr = parse(line);                          /* step 1 */
  if (suspicious.ContainsKey(ipaddr))                   /* step 2 */
    matches++;                                          /* step 3 */
}

生成的雜湊表 （第 0 步） 會招致 o (n) 一次性、 預付費用。 這將生成整體的複雜性：

= O(build + loop)
= O(N + M * 1)
= O(N + M)

假設我們的場景中的 M >> N，版本 3 是我們最快的解決方案，在大約 O(M) 時間。 N = 1,000 可疑的 IP 位址，我們只是減少執行時間由另一個 10 倍，這是 1000 x 比我們原來的版本更快。 什麼是非凡對這種做法是為 N 的更大值 — — 說，10000，或甚至 100,000 — — 執行時間是相同的 M 時間步驟的順序。

那麼什麼是漁獲？ 第 2 版和二進位搜索，很簡單： 首先必須排序的 IP 位址的清單。 在此版本的雜湊演算法，有三個要考慮的問題： 創建一個有效的雜湊函數、 先期建設成本和更大的記憶體佔用量。 關鍵是雜湊函數。 有效的雜湊函數將資料散佈到最小的碰撞，不再需要額外搜索後最初的雜湊表中的表。 這種功能提供了先期工程造價的複雜度，每個基準或線性搜索相同的 o (n)。 然而，這種效果通常涉及附近的 10%，這意味著資料佔用的表的只有 10%的負荷因數。 雖然正式這仍然是 o (n) 也和別人一樣，雜湊因此需要 x 比線性和二進位搜索，更大的記憶體佔用量 10。

為什麼我們這樣做，再次？

之後，所有的 pseudo-math，它可能會罷工非電腦科學研究生我們做了大量的理論操縱，，雖然我們認為我們找到了一個有效的解決方案，我們肯定掉大量的一路走來的常量。 這把我們帶到萬-­美元的問題："？ 我們真的付掉在實踐中的理論分析"一個公平的問題，尤其是當你認為這篇文章的最終目標 — — 以鼓勵您使用演算法分析 （如果你不是已經） 來評估之前向代碼的競爭方法。

很多時候已經坐在我身邊看著幾個小時的爭辯的工程師的表 — — 甚至幾天，有時 — — 方法 A 是否比方法 B. 人們很少做拉出一張餐巾紙和執行快速演算法分析。

所以，現在，我們所做的分析，讓我們運行某些測試，看在實踐中發生了什麼。 要做到這一點，我們生成隨機日誌檔與 M 條目，然後搜索這些檔以防隨機生成的 N IP 位址的清單。 （完整源和輸入的檔可在 bit.ly/srchlogfiles。）

總括來說，假設 M >> N，我們派生中所示的演算法複雜性圖 2。

圖 2 演算法複雜性假設 M >> N

  時間 (t)
版本 1： 使用線性搜索 O(M * N)
使用二進位搜索版本 2： O(M * lgN)
版本 3： 使用雜湊演算法 O(M)

對於我們的測試中，我們設置 M 100 萬，以及為每個測試的雙 N： 128、 256、 512 等等。 搜索演算法的性能特點突出顯示 N 的增加了一倍。 如果我們的分析是準確的每次 N 增加了一倍，執行時間應更改，如中所示圖 3。

圖 3 預計執行時間的變化時 N 增加一倍

  2N 的時間
1 版 O (M ＊ 2 ＊ N) = > 2 ＊ O(M * N) = > 2t
2 版 O (M ＊ lg(2N)) = > O (M ＊ (lg2 + 鈮酸鎵鑭)) = > O (M ＊ (1 + 鈮酸鎵鑭) = > O (M + M ＊ 鈮酸鎵鑭) = > M + O(M * lgN) = > M t +
3 版 O(M) = > t

換句話說，版本 1 應在時間 （2t) 增加一倍，第 2 版應採取另一種 M 時間步驟 （t + M） 和版本 3 應採取任何額外的時間 (t)。 圖 4 顯示實際記錄時間 （以秒為單位）。

圖 4 實際執行時間 （秒）

許 N 1 版 2 版 3 版
1,000,000 128 3.81 2.88 2.15
  256 5.65 2.98 2.15
  512 9.39 3.11 2.17
  1,024 16.78 3.23 2.19
  2,048 31.52 3.36 2.19
  4,096 61.18 3.49 2.28
  8,192 120.63 3.68 2.39
  16,384 238.86 3.95 2.54
  32,768 473.91 4.34 2.89

正如您看到的圖 4，版本 1 — — 基於線性搜索 — — 不會在時間為 N 雙打確實雙。 這可能是一件壞事，大多數情況。

第 2 版 — — 基於二進位搜索 — — 數量級比跑得快的版本 1 和增長緩慢得多。 增長速度難量化，因為它取決於 TM，它執行 M 操作，似乎任何地方從 0.1 至 0.3 秒的時間。 根據我們的分析，第 2 版應作為 N 雙打 TM 的恒定速度增長，但這似乎並沒有出現這種情況 ； 這可能會增加快取記憶體壓力的結果 （和因此快取記憶體未命中） 隨著 N。

最後， 圖 4 證實該版本 3 的確是速度最快的演算法，本質上是同一執行時間無論 N （但又不是很常數）。

尋求平衡

從一個實用主義者的角度看，尚不清楚從第 2 版第 3 版的增強是值得任何超過大量瑣碎的努力 — — 儘管一秒多的儲蓄。 潛在的節約並不真的要作出很大的差異，除非我們開始看到真正的大或值的 M N （銘記雜湊演算法可能需要更多記憶體來存儲 IP 位址 x 10)。 這引發了最後一點： 知道什麼時候停止尋求以優化。 它可能是令人興奮和令人信服的程式師可以找到的絕對速度最快的演算法，以執行某種操作，但除非此操作是前端--中心中使用者的臉上，嘗試去優化所花費的時間最後第二遠往往能更好用了別的工作。 從版本 1 到版本 2 的跳顯然是值得的時間 （即儲蓄 10,000%左右），但與所有事情一樣，程式師必須尋求平衡。 有時理論必須讓路的做法，但在其他時候，理論有助於聽寫，我們應該把我們的努力付諸實施。

編碼愉快 ！

Ted Neward 是 Neudesic LLC 建築顧問。他已經寫一百多篇和編著或合著了十幾本書，包括"專業 F # 2.0"（Wrox，2010年）。他是 C# MVP，在世界各地的會議上發言。他諮詢、 定期指導 — — 達到他在 ted@tedneward.com 或 Ted.Neward@neudesic.com 如果你感興趣讓他來和你的團隊工作或閱讀他在博客上的 blogs.tedneward.com。

Joe Hummel 是私人顧問公司，在 Pluralsight LLC 的技術人員、 一個 MVP Training.net 的訓練師和客座研究員在電腦科學系，加州大學歐文分校的部的成員。他獲得了博士學位 在高性能計算領域的加州大學歐文和平行的所有東西感都興趣。他居住在芝加哥地區，並在達成時，他並不航行 joe@joehummel.net。