程序設計的細節問題，是我們編程者經常會疏忽的問題。本文將從一個小小的作業開始，并結合數據結構方面的知識，來進行講解。

馬爾可夫鏈（Markov Chain），這是我們《程序設計方法學》課程的一個小小的作業，這個作業，主要目的并不是實現算法，而是“如何”實現算法，以及從代碼中看出每個人程序設計的“風格”。 因為即使是很少的代碼也能暴露出一個編程者的功底和風格。

我覺得這是個很有意思的話題，所以也在這里把我的部分代碼發出來，并加以說明以作拋磚引玉。

目標

先稍稍介紹下馬爾可夫鏈，簡單地說就是輸入一篇文章（其實是單詞序列），建立前綴表后綴表，然后根據前綴隨機選擇后綴，如此迭代，生成一篇“看起來像文章的隨機文本”。當然這只是馬爾可夫鏈的一個應用，不過也算挺典型的。我曾經在開發一些應用的時候用類似的程序來生成測試數據。

程序結構

根據我們老師的要求，程序從文件讀入樣本數據，從標準輸出打印生成的文本，其他沒有具體要求。 我選擇C#來實現這一程序。

我的程序流程非常簡單：

讀取樣本 -> 建立前綴、后綴表 -> 生成 -> 輸出

數據結構

根據編程經驗和《程序設計實踐》，前綴表采用哈希表，后綴表采用鏈表。
后綴表非常簡單，每一個后綴都有一個Next，也就是說后綴本身就是一個鏈表節點，也就不需要LinkedList來幫忙了。

Suffix  
class Suffix {  
    public string Word { get; set; }  
    public Suffix Next { get; set; }  
} 

相比之下，前綴就稍微麻煩一點了。首先“前綴”是一個單詞序列，存儲上不管用數組還是.NET FCL中的各種集合都沒問題，但是這二者都無法方便地哈希。所以我采取了一個投機取巧的方法，就是把前綴拼接成一個字符串，用string做哈希表的Key。
由于前綴涉及到一些具體操作，我把它單獨提出來寫成Prefix，而以整合了Prefix與Suffix的State來做迭代中的算子，所以我的前綴表就是Dictionary，這個前綴表的設計，顯然有點寒磣，而后綴表就是由Suffix構成的鏈表。

Prefix

class Prefix {  
    #region Properties  
 
    ///   
    /// 前綴數  
    ///   
    public static int PrefixCount = 2;  
 
    ///   
    /// 前綴詞  
    ///   
    public string[] PrefixWords { get; set; }  
 
    #endregion  
 
    #region Public Methods  
 
    ///   
    /// 構造一個空的Prefix  
    ///   
    ///   
    public static Prefix CreateEmpty() {  
        return new Prefix();  
    }  
 
    ///   
    /// 滾動一下  
    ///   
    public Prefix Roll(string suf) {  
        if (PrefixCount == 1) {  
            PrefixWords[0] = suf;  
        } else {  
            Array.Copy(PrefixWords, 1, PrefixWords, 0, PrefixCount - 1);  
            PrefixWords[PrefixCount - 1] = suf;  
        }  
        return this;  
    }  
 
    ///   
    /// 克隆一個完全一樣的Prefix對象  
    ///   
    public Prefix Clone() {  
        return new Prefix(PrefixWords);  
    }  
 
    #endregion  
 
    #region Constructors  
 
    private Prefix() {  
        PrefixWords = new string[PrefixCount];  
    }  
 
    ///   
    /// 根據已知單詞構造一個Prefix  
    ///   
    /// 前綴單詞序列  
    public Prefix(params string[] words) {  
        if (words.Length != PrefixCount) {  
            throw new ArgumentException("Prefix count error!", "words");  
        }  
        PrefixWords = new string[PrefixCount];  
        Array.Copy(words, PrefixWords, PrefixCount);  
    }  
 
    #endregion  
} 

重寫GetHashCode()的代碼我就省略了。

細節

不論是建立詞綴表還是生成文本的過程中，只要選擇了一個后綴，前綴就需要滾動一次，所以我這里做了一種“古怪”的設計。首先是在迭代過程中，Prefix 對象始終是同一個對象的引用，只是它內部維護的數組在滾動，這個應該很好理解。但是這樣會出現一個問題，那就是State對Pref的引用會出現混亂。所以我只好給Pref設計了一個Clone方法，而事后回想，這是一個完全錯誤的設計，因為我可以用另外的方法來避免這種窘境（下文會說到）。
在生成中，涉及到一個怎么設計返回值的問題，關于這個問題我考慮了不少，也改了幾次。
最直接的辦法：直接向命令行輸出，因為題目要求最終輸出到命令行，所以這個方法的確是可行的，但是我考慮到這些代碼的重用性，沒采取這種方法。
厚道點的辦法：不像命令行輸出，而是傳入一個TextWriter，雖然這個方法和上一種比，完全是換湯不換藥，但是好歹也是考慮的多了一點點。

上面兩種方法都有一個問題，就是我們在設計函數的時候，給一個函數多大的權限呢？我們常認為：要么就輸入輸出都自己處理，要么就都不處理，把輸入輸出交給別的函數專職處理。上面兩種方法無疑違背了這一個規律，因為TextGenerator類的構造函數參數是IEnumerable，也就是說，輸入是不由TextGenerator處理的，而這里卻又自作主張地處理了輸出，顯然讓人暈乎乎。

最簡單的辦法：直接返回一個生成的字符串，我想這會是大多數人的方案。但是也有明顯的缺陷：對于英文，很自然地我們會在每個單詞后面加上一個空格，但是如果處理的是中文呢？加上個空格顯然很郁悶。也就是說這樣設計就完全沒有給用戶（函數的調用者，下同）選擇格式的機會。難免有自作聰明之嫌。雖然我***的程序中保留了這段代碼，但也是覺得聊勝于無了。
較自由的辦法：調用的時候，傳入一個Action，也就是一個委托，決定每一個被選中的單詞做怎么操作，在這個例子中，也就是

采用委托的方式

s => {  
    Console.Write(s);  
    Console.Write(" ");  
} 

這樣做看起來已經不錯了，還挺現代的寫法，不過我最終還是沒有選擇這樣的方法，因為我采取了——

我最終的辦法：返回IEnumerable，這里可以發揮C#強大的語言特性，使用yield來返回，這樣用戶可以直接

采用迭代器的方式

foreach (string s in gen.Generate(maxWordCount)) {  
    Console.Write(s);  
    Console.Write(" ");  
} 

這個也算一個迭代器模式的小小的運用吧。其實這個方法和傳遞委托的方法相差已經很小了，但是我個人喜歡后者。

遺憾

這就不得不說文中提到的那個我***的錯誤了。
首先就是我從數據的定義上就出現了問題，因為State里保留的Prefix引用根本沒有發揮作用，而Suffix也只是一個頭指針，也就是說與其如此復雜還弄出個Prefix.Clone()，還不如直接就把State的小命給革掉。Prefix直接就能映射到Suffix，也省的一個State在中間耽擱著。而Prefix采用了一種“猥瑣”的哈希方式，也是有待改進。

小結

雖然是一個小程序（據說perl只用19行），基本算法也相當簡單，但是從中暴露的程序設計的問題卻不少，接口職責的設計毫無疑問是程序設計當中的重要部分，“高內聚低耦合”幾個字天天掛在嘴皮邊上，但真正干活的時候也不是那么容易實現的。身為程序員，難道不應該在這些方面多動動腦筋嗎？

擴展

在這個程序中，我完全沒有考慮API設計中的另一重要環節——異常。并不是疏忽，而是我從一開始就沒有把這個列入考慮范圍，所以這也是一個可擴展的地方。什么地方拋出異常，拋出什么異常，怎么接到異常，怎么處理，都值得設計。

原文標題：馬爾可夫鏈——從一個編程作業中看看程序設計的一些細節問題

鏈接：JimLiu

【編輯推薦】

1. C#語言讀書心得備忘
2. 詳解C#制做Active控件的五個步驟
3. 總結C#多線程的點點滴滴
4. 學習C#多線程：lock的用法
5. 各種C#數組的定義和初始化