接著上一篇文章繼續往下講。如果按照上一篇文章走下去的話，現在估計做了有些小軟件了吧。字符串和圖形都容易做大，而且對于潛意識上喜歡數學的最有希望的程序員們也是有吸引力的。但是這兩種東西卻不容易做好。等到程序到了一定規模的時候，維護和效率這兩大問題就會凸顯出來。心急吃不了熱豆腐，為了解決維護和效率這兩個經常會出現的問題，我們需要學習算法和架構。這兩種東西是可以同時學的，但是一篇文章說不了多少東西，那么就從算法開始吧。

    程序員是需要開闊眼界的，光C#一門也是不行的，畢竟程序運行在各種平臺上，有各種各樣的語言。譬如Win32上的native C/C++、Delphi等，.NET上的C#和VB.NET，還有自成體系的Java，然后就是運行在mainframe上的COBOL，剩下的還有各種各樣的函數式語言、腳本語言等等。熟悉了C#的人從Delphi入手不會很困難，從C/C++入手也可以了。這兩門原本是本地語言的語言在編寫程序的時候需要我們注意多一些的東西，典型的就是內存管理。這還是需要多加練習的，在這里就不多說了。

    說到算法，在這里首先向大家推薦《算法導論》第二版。一年前我去買的時候，發現了中文版，但是中文版那個時候仍然有一些章節沒有翻譯。不知道現在怎么樣了。英語好的同志們可以去買英文版。

    算法與數據結構是經常出現在一起的。每一種算法總會有在各種不同數據結構上的實現，用于處理不同的問題。在不同的語言上面，各種各樣針對實際問題的數據結構也有一些巧妙的做法和通用的做法。我們可以用STL，可以用System.Collections.Generic，也可以自己寫。這根據實際情況而定。我們并不是不能做的比STL好，只是STL已經相當好了，滿足了大多數人的需要。在特定的情況下，面對非常特殊的問題，有時候我們就要自己實現數據結構。使用上一篇文章說的辦法來聯系的話，到了這個時候已經寫了不少代碼了，用了不少并不復雜的數學知識了，鍛煉了理論與實際相聯系的基礎。有了這些基礎，我們學習算法和數據結構會比較簡單。

    常用的數據結構有鏈表、列表、堆棧、隊列、二叉樹、平衡樹、堆、哈希表和圖等，除此之外還有各種各樣的變形，但是萬變不離其宗。圍繞著這些數據結構還有各種各樣的算法。典型的有排序算法、搜索算法、尋路算法、網絡流等等。還有一些屬于策略的算法，譬如貪心算法、動態規劃等等。屬于策略的算法經常用于制造新的算法，要慢慢體會，勤加思考才行。至于這些數據結構和算法的實際內容我并不打算在這篇文章講。《算法導論》用了半本書來說這些問題，還是看書的好，文章不夠詳細。

    至于我們如何選擇算法呢？就如同我剛才強調的一樣，我們需要聯系理論與實際的經驗，我們要用數學的眼光來看待我們需要解決的問題。如果我們找到了一種簡潔的表示來描述我們的問題的話，我們同時也找到了解決問題需要的數據結構的雛形。當然這個數學并不是指數學分析這些，我覺得更接近于抽象代數。扯遠了啊，一般來說我們并不需要鉆研這些學科，我們只需要有感覺就好了。培養感覺的一個捷徑就是學習數學。當然不學習也可以，經驗也能知道我們做事情，只不過走的路要長一些。至于讀者希不希望學習數學就自己決定吧，沒有普適的道路。找到了數據結構的雛形之后，剩下的就是尋找算法了。有一些算法可以在書里面找到（譬如ACM很喜歡考的題目），有一些算法可以在論文中找到（譬如專門為了對付一些復雜問題而制造出來的不具有通用性的算法），剩下的就要靠我們自己去推導了。

    那么，我們如何學習算法呢？我們是為了解決實際問題才學習算法的，是為了為將來自己遇到問題的時候有個指導方向才學習算法的，我們并不是為了學習算法而學習算法。我見過兩種不同的學習算法的人。第一種是直覺閱讀算法并學習，以后碰到問題再尋找。另一種則是僅僅將算法稍微了解一下然后就放開，以后遇到問題的時候再翻開相應的算法來學習。兩種方法適應于兩種不同的人，并沒有什么大的優劣之分。于是我們根據自己的興趣或者需要，終于必須掌握一種算法了。那么這個時候我們可以找資料來看，就跟閱讀文章一樣消化里面的知識，然后就寫一些小程序來試驗試驗（或者叫做原型，那些做軟件工程的人都喜歡這么說）。這種小程序屬于拋棄型原型，寫完即扔的，目的是為了讓自己在了解了算法的內容之后，檢驗一下自己是否已經真的明白了執行這個算法所需要的所有細節問題。等到覺得自己已經能控制這個算法的時候，我想也就差不多了吧。

    有些人可能會覺得算法很復雜，因為書里面的算法都是非常復雜的。但是算法的目的是為了快，因此有一些好的算法跟數據結構，結合的時候可能會變得相當簡單，但是并不是很容易想到。在這里我舉幾個簡單的例子。

    喜歡做圖形的朋友們，大概都喜歡做游戲吧，嘿嘿。我們小時候在做那種簡單的2D游戲的時候，總是要計算一大堆人之間是否相互接觸，或者很多人放出的魔法是否跟敵人碰撞到。如果我們的地圖上有100個人，每個人放了兩招，兩兩檢驗是否碰撞（以便判斷是否應該實施攻擊）的話就需要檢查20000次。這顯然是不行的。那么我們可以使用分而治之的原理來做。我們可以把地圖切成很多個區域，區域包含著人和魔法。每當人和魔法的移動越過區域的邊界的時候，人和魔法就把自己從前一個區域斷開，鏈接到新的區域里面去。這個時候區域就保存了兩個鏈表，一個是人，另一個是魔法。好了，如何檢查魔法和人互相碰撞呢？只需要檢查同一個區域里面的就行了。如果這100人都在25個區域里面，平均每個區域有4個人8個魔法，那么兩兩檢驗的話只需要檢查4×8×25=800次，相對于前面的暴力算法節省了96%的時間。當然這只是理想狀態。

    在這里舉另一個例子。我們都覺得C#、VB和Java很神奇吧，東西new了都不用delete，多舒服。假設我們現在要實現這種功能的話，我們需要維護所有已經new了的內存空間，并執行一種搜索算法來判斷哪一些內存空間是再也不可能被訪問的然后標記，最后刪掉所有被標記的空間。于是我們需要一個內存管理器，用來申請、標記和釋放。如何做比較合適呢？

    我們的內存管理器需要根據設置的長度返回一段句柄來代表內存空間，然后需要可以通過句柄來訪問內存，最后標記并一起刪除這些句柄。為什么要句柄呢？因為如果直接返回指針的話，語言執行久了會產生很多內存碎片，而且new和delete也不夠快。現在，我們需要以下幾個數據結構：

    ·一個記錄所有被new了而且delete過的句柄的列表，用于迅速獲得沒有正在被使用的句柄。
    ·一個記錄了所有正在使用的句柄的列表，記錄指針以及長度。這張表是一個數組，句柄是索引。

    new的時候，我們查詢第一張表拿出一個空閑的句柄。如果列表為空的話那么將第二個表變大（這個時候所有句柄都被使用）并且將第一個空閑的（也就是原來的表接下去的第一個新空間）句柄所對應的記錄標記使用。然后我們分配的總是最末尾的地方
    delete的時候，我們查詢所有標記了使用句柄，看看是否有被mark，有的話就標記為不使用并將句柄放置入第一張表。
    mark的時候，我們查詢這個句柄所對應的記錄，然后mark。
    collect的時候，這是一個操作，將所有內存碎片清除。我們只需要順序遍歷第二章表，將有用的內容挪動到前面一大塊無用的空間里面，復制一下數據然后修改一下起始指針即可。

    圖示一下：
    空閑句柄：1 2
    句柄記錄：<0,0..9><1,NULL><2,NULL><3,40..43>
    內存空間：[第0-9個字節占用][10-39不占用][40-43被占用][此處為末尾]

    好了，我們需要申請一個內存空間，我們拿到了句柄4，需要10個字節。
    空閑句柄：1 2
    句柄記錄：<0,0..9><1,NULL><2,NULL><3,40..43><4,44..53>
    內存空間：[第0-9個字節占用][10-39不占用][40-43被占用][44-53被占用][此處為末尾]

    現在我們標記3并刪除：
    空閑句柄：1 2 3
    句柄記錄：<0,0..9><1,NULL><2,NULL><3,NULL><4,10..19>
    內存空間：[第0-9個字節占用][10-19占用，從句柄4挪過來的][此處為末尾]

    分析一下時間復雜度吧，這里分析的是絕大部分情況，根據數據結構的實際實現偶爾會有少許偏差。
    new為O(1)，因為從空閑句柄獲得內容為O(1)，分配末尾內存為O(1)，找到記錄并標記為O(1)
    mark為O(1)，因為找到記錄并標記為O(1)
    delete為O(1)，因為只需要標記
    collect為O(n)，因為遍歷句柄記錄O(n)，挪動內容，就算最多也就挪動整段內存空間，也是O(n)
    從句并獲得內存地址也是O(1)

    我們僅僅需要在內存不夠的情況下才動用win32的api分配一塊新的大內存，這樣來看的話在大部分情況下我們的內存管理器的分配比操作系統做得還快，這也是為什么C#作為托管語言并沒有明顯慢下來的一個原因。當然還有一些其他原因，譬如.NET虛擬機會把一些托管代碼臨時編譯成本地代碼等等。

    至于第三個例子，就看這里吧，為了做一個大作業而弄出來的利用動態規劃是顯得簡單尋路算法。

    說到這里本篇也快結束了。舉著兩個例子只為了說明以下問題：
    ·算法往往跟執行效率有很大關系
    ·好的數據結構才能發揮算法應有的威力
    ·要根據實際情況來選擇，甚至自己思考算法
    ·算法并不都是復雜的

    其實，對于數據結構和算法不熟悉或者根本沒聽說過的話，也并不是就不能寫出一些稍微有點規模的程序，只是寫出來的程序可能會很亂。算法在一個程序員的發展道路上看還是最好學一學。