程序設(shè)計(jì)的細(xì)節(jié)問(wèn)題，是我們編程者經(jīng)常會(huì)疏忽的問(wèn)題。本文將從一個(gè)小小的作業(yè)開(kāi)始，并結(jié)合數(shù)據(jù)結(jié)構(gòu)方面的知識(shí)，來(lái)進(jìn)行講解。

馬爾可夫鏈（Markov Chain），這是我們《程序設(shè)計(jì)方法學(xué)》課程的一個(gè)小小的作業(yè)，這個(gè)作業(yè)，主要目的并不是實(shí)現(xiàn)算法，而是“如何”實(shí)現(xiàn)算法，以及從代碼中看出每個(gè)人程序設(shè)計(jì)的“風(fēng)格”。 因?yàn)榧词故呛苌俚拇a也能暴露出一個(gè)編程者的功底和風(fēng)格。

我覺(jué)得這是個(gè)很有意思的話題，所以也在這里把我的部分代碼發(fā)出來(lái)，并加以說(shuō)明以作拋磚引玉。

目標(biāo)

先稍稍介紹下馬爾可夫鏈，簡(jiǎn)單地說(shuō)就是輸入一篇文章（其實(shí)是單詞序列），建立前綴表后綴表，然后根據(jù)前綴隨機(jī)選擇后綴，如此迭代，生成一篇“看起來(lái)像文章的隨機(jī)文本”。當(dāng)然這只是馬爾可夫鏈的一個(gè)應(yīng)用，不過(guò)也算挺典型的。我曾經(jīng)在開(kāi)發(fā)一些應(yīng)用的時(shí)候用類似的程序來(lái)生成測(cè)試數(shù)據(jù)。

程序結(jié)構(gòu)

根據(jù)我們老師的要求，程序從文件讀入樣本數(shù)據(jù)，從標(biāo)準(zhǔn)輸出打印生成的文本，其他沒(méi)有具體要求。 我選擇C#來(lái)實(shí)現(xiàn)這一程序。

我的程序流程非常簡(jiǎn)單：

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

數(shù)據(jù)結(jié)構(gòu)

根據(jù)編程經(jīng)驗(yàn)和《程序設(shè)計(jì)實(shí)踐》，前綴表采用哈希表，后綴表采用鏈表。
后綴表非常簡(jiǎn)單，每一個(gè)后綴都有一個(gè)Next，也就是說(shuō)后綴本身就是一個(gè)鏈表節(jié)點(diǎn)，也就不需要LinkedList來(lái)幫忙了。

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

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

Prefix

class Prefix {  
    #region Properties  
 
    ///   
    /// 前綴數(shù)  
    ///   
    public static int PrefixCount = 2;  
 
    ///   
    /// 前綴詞  
    ///   
    public string[] PrefixWords { get; set; }  
 
    #endregion  
 
    #region Public Methods  
 
    ///   
    /// 構(gòu)造一個(gè)空的Prefix  
    ///   
    ///   
    public static Prefix CreateEmpty() {  
        return new Prefix();  
    }  
 
    ///   
    /// 滾動(dòng)一下  
    ///   
    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;  
    }  
 
    ///   
    /// 克隆一個(gè)完全一樣的Prefix對(duì)象  
    ///   
    public Prefix Clone() {  
        return new Prefix(PrefixWords);  
    }  
 
    #endregion  
 
    #region Constructors  
 
    private Prefix() {  
        PrefixWords = new string[PrefixCount];  
    }  
 
    ///   
    /// 根據(jù)已知單詞構(gòu)造一個(gè)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  
} 

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

細(xì)節(jié)

不論是建立詞綴表還是生成文本的過(guò)程中，只要選擇了一個(gè)后綴，前綴就需要滾動(dòng)一次，所以我這里做了一種“古怪”的設(shè)計(jì)。首先是在迭代過(guò)程中，Prefix 對(duì)象始終是同一個(gè)對(duì)象的引用，只是它內(nèi)部維護(hù)的數(shù)組在滾動(dòng)，這個(gè)應(yīng)該很好理解。但是這樣會(huì)出現(xiàn)一個(gè)問(wèn)題，那就是State對(duì)Pref的引用會(huì)出現(xiàn)混亂。所以我只好給Pref設(shè)計(jì)了一個(gè)Clone方法，而事后回想，這是一個(gè)完全錯(cuò)誤的設(shè)計(jì)，因?yàn)槲铱梢杂昧硗獾姆椒▉?lái)避免這種窘境（下文會(huì)說(shuō)到）。
在生成中，涉及到一個(gè)怎么設(shè)計(jì)返回值的問(wèn)題，關(guān)于這個(gè)問(wèn)題我考慮了不少，也改了幾次。
最直接的辦法：直接向命令行輸出，因?yàn)轭}目要求最終輸出到命令行，所以這個(gè)方法的確是可行的，但是我考慮到這些代碼的重用性，沒(méi)采取這種方法。
厚道點(diǎn)的辦法：不像命令行輸出，而是傳入一個(gè)TextWriter，雖然這個(gè)方法和上一種比，完全是換湯不換藥，但是好歹也是考慮的多了一點(diǎn)點(diǎn)。

上面兩種方法都有一個(gè)問(wèn)題，就是我們?cè)谠O(shè)計(jì)函數(shù)的時(shí)候，給一個(gè)函數(shù)多大的權(quán)限呢？我們常認(rèn)為：要么就輸入輸出都自己處理，要么就都不處理，把輸入輸出交給別的函數(shù)專職處理。上面兩種方法無(wú)疑違背了這一個(gè)規(guī)律，因?yàn)門extGenerator類的構(gòu)造函數(shù)參數(shù)是IEnumerable，也就是說(shuō)，輸入是不由TextGenerator處理的，而這里卻又自作主張地處理了輸出，顯然讓人暈乎乎。

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

采用委托的方式

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

這樣做看起來(lái)已經(jīng)不錯(cuò)了，還挺現(xiàn)代的寫(xiě)法，不過(guò)我最終還是沒(méi)有選擇這樣的方法，因?yàn)槲也扇×恕?/P>

我最終的辦法：返回IEnumerable，這里可以發(fā)揮C#強(qiáng)大的語(yǔ)言特性，使用yield來(lái)返回，這樣用戶可以直接

采用迭代器的方式

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

這個(gè)也算一個(gè)迭代器模式的小小的運(yùn)用吧。其實(shí)這個(gè)方法和傳遞委托的方法相差已經(jīng)很小了，但是我個(gè)人喜歡后者。

遺憾

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

小結(jié)

雖然是一個(gè)小程序（據(jù)說(shuō)perl只用19行），基本算法也相當(dāng)簡(jiǎn)單，但是從中暴露的程序設(shè)計(jì)的問(wèn)題卻不少，接口職責(zé)的設(shè)計(jì)毫無(wú)疑問(wèn)是程序設(shè)計(jì)當(dāng)中的重要部分，“高內(nèi)聚低耦合”幾個(gè)字天天掛在嘴皮邊上，但真正干活的時(shí)候也不是那么容易實(shí)現(xiàn)的。身為程序員，難道不應(yīng)該在這些方面多動(dòng)動(dòng)腦筋嗎？

擴(kuò)展

在這個(gè)程序中，我完全沒(méi)有考慮API設(shè)計(jì)中的另一重要環(huán)節(jié)——異常。并不是疏忽，而是我從一開(kāi)始就沒(méi)有把這個(gè)列入考慮范圍，所以這也是一個(gè)可擴(kuò)展的地方。什么地方拋出異常，拋出什么異常，怎么接到異常，怎么處理，都值得設(shè)計(jì)。

原文標(biāo)題：馬爾可夫鏈——從一個(gè)編程作業(yè)中看看程序設(shè)計(jì)的一些細(xì)節(jié)問(wèn)題

鏈接：JimLiu

【編輯推薦】

1. C#語(yǔ)言讀書(shū)心得備忘
2. 詳解C#制做Active控件的五個(gè)步驟
3. 總結(jié)C#多線程的點(diǎn)點(diǎn)滴滴
4. 學(xué)習(xí)C#多線程：lock的用法
5. 各種C#數(shù)組的定義和初始化