使用組合改進軟件測試用例的生成

原文出處：Using Combinations to Improve Your Software Test Case Generation（July 2004）

　　javascript:tagshow(event, '%B2%E2%CA%D4');" href="javascript:;" target=_self>測試已經成為軟件開發過程中一個至關重要的部分，但近來有三個因素使之扮演了一個甚至更加重要的角色。第一，Microsoft®.NET 開發環境的 誕生戲劇性地改進了開發人員編寫定制測試自動化的能力。那些在 .NET 框架面世以前需要花費數周時間創建的測試程序現在僅用幾小時就可以寫好。第二，正在建立的日益復雜的系統需要更精益求精的測試。最后，軟件安全在軟件開發過程中已不再是事后才 關注的事情，它已成為一個絕對要素。曾經一度推出可能沒有經過完全測試的產品，但這已不再是一個生存選擇。為了幫助你迎接當今測試的挑戰，本專欄將在隨后幾個月的 內容里討論一些關于軟件測試的原則、技巧和最佳實踐。
　　本月我將從組合在軟件測試中的作用講起。通過編程產生組合的能力使你能有一種強有力的方法來生成測試用例輸入。為了弄清楚什么是組合，現在假定你正在寫一個撲克 牌游戲程序。用手工生成所有可能的五張套測試輸入將是一件令人很不爽的事情。但是用本文的示例代碼，你便可以在分分鐘內做好它：

string[] deck = new string[] { "Ac", "Ad", "Ah", "As", "Kc", (...) };
Combination c = new Combination(52,5); // 52 cards, 5 at a time
string[] pokerHand = new string[5];
        
while (c != null)
{
  pokerHand = c.ApplyTo(deck);
  PrintHand(pokerHand);
  c = c.Successor();
}      

　　屏幕的截屏是最佳示范方式。Figure 1 是一個基于 Windows® 的應用程序屏幕，它演示了組合的使用。正如你所看到的，條目（items）的組合是這些條目的一個子集，它們的順序并不重要。在這個例子中我有5個條目——名字 分別為 Adam、Barb、Carl、Dave 和 Eric，——而我感興趣的是大小為3的組合。這里5選3有10種可能的子集：

{ Adam, Barb, Carl }, { Adam, Barb, Dave }, . . . { Carl, Dave, Eric }

        { 0, 1 }{ 1, 2 }
        { 0, 2 } { 1, 3 }
        { 0, 3 } { 2, 3 }

組合

　　數學組合的三個基本操作如 Figure 2 所示。輸出告訴你當 n = 4，k = 2 時，有六種組合：

        { 0, 1 } { 1, 2 }
        { 0, 2 } { 1, 3 }
        { 0, 3 } { 2, 3 }

一個組合類

　　數學組合非常適宜用一個類來實現。你需要數據成員存儲 n 的值（條目總數），k（每個子集元素的條目個數）的值，以及一個數組來保存每個組合元素的“原子”。Figure 3 是表述某個Combination（組合）對象的基本代碼和創建該組合對象第一個詞典元素的構造函數，以及將它表示為一個字符串的代碼。我決定使用C#，但你可以 輕松地將它改編為你所選的任意一種基于 .NET的編程語言。
　　我將這個代碼放入類庫（Class Library）編譯后，我可以給它增加一個工程選項參數（Project Reference），并從 .NET 控制臺 程序調用它，就象我在此所做的這樣：

Combination c = new Combination(5,3);
Console.WriteLine("\nCombination c(5,3) is initially " + c.ToString());      

Combination c(5,3) is initially { 0 1 2 }

Combination c = new Combination(5,3);

　　我在內存中獲得一個對象，它表示五個條目中一次取三個的最初的詞典排序的數學組合元素。內存中的對象可以被表示為如 Figure 4 所示。

Figure 4 內存中的對象

　　構造函數代碼創建最初的組合元素時是相當簡單的。兩個代表條目總數和子集大小的參數被分別存儲在數據成員 n 和 k 中。因為我處理的數值可能會很大， 所以我決定使用 C# 的 long 類型代替int 類型。如果我愿意的話，我可以用 ulong 類型（無符號 long）獲得雙倍的數值范圍。我用子集的大小 k 來為一個 long 類型的命名數組分配空間，然后用 0 到 k-1 范圍的整數填充每個數據單元。

計算組合元素的個數

　　現在我已經確定了如何創建一個組合對象，讓我們看看組合的三個基本操作的第二個——根據某個給定的條目總數 n 及子集大小 k 來計算組合元素的總數。舉個例子，如果你處理一次從 n＝5 條目中取 k＝3，這里有10種可能的組合元素：

        { 0, 1, 2 } { 0, 3, 4 }
        { 0, 1, 3 } { 1, 2, 3 }
        { 0, 1, 4 } { 1, 2, 4 }
        { 0, 2, 3 } { 1, 3, 4 }
        { 0, 2, 4 } { 2, 3, 4 }

　　我想實現一個 Choose(n,k) 函數，它返回組合元素的個數；Choose(5,3) 返回10。查找現有的Choose 實現，我驚訝地發現 Internet 上的大多數算法都很不耐用。在我向你展示我的 Choose 實現之前，讓我們簡要地審視一下 Choose 函數的標準實現。
　　編寫 Choose(n,k) 函數的標準方法是直接使用其定義公式。這是一個明顯的但是拙劣解決方案。這里是一個用 C# 編碼的典型 Choose(n,k) 函數 ：

// poor implementation of Choose(n,k)
static int Choose(int n, int k)
{
  int numerator = Factorial(n);
  int denominator = Factorial(k) * Factorial(n-k);
  return ( numerator / denominator );
}      

static int Factorial(int m)
{
  int ans = 1;
  for (int i = m; i >= 1; —i)
  {
    ans = ans * i;
  }
  return ans;
}        

　　這里的 Choose(n,k) 實現有幾個問題：最嚴重的是它會因為當 n 和 k 的值十分小時而溢出。注意這個 Choose(n,k) 首先計算 Factorial(n)， 即便 n 是一個很小的值，它也會迅速增大到一個非常大的數 ( 比如，21! 將溢出一個無符號的 64 位數)。其次 Choose(n,k) 的值由兩個階乘的乘積 來除，這也可能成為一個非常大的數，得出的結果可能非常小。關鍵是即使 Choose(n,k) 返回的結果很小，中間計算結果很容易溢出。
　　一個更好的 Choose(n,k) 實現使用一個不同的方法計算其答案。改版的 Choose(n,k) 使用以下不同的公式來計算：

        Choose(n,k) = (n * (n-1) * (n-2) * ... * (n-k+1)) / ( 1 * 2 * ... * k) 

        Choose(7,3) = (7 * 6 * 5) / (1 * 2 * 3)

　　這個算法取代了原來計算分子（一個大數），然后計算分母（一個大數），然后相除，你可以計算部分乘積法并隨意進行除法運算。對于 Choose(7,3) 例子，你 先計算 7 * 6 并除以 2，得到 21（譯注：原文為“getting 24”顯然不對，7 * 6/2＝21）(跳過此分數下面部分的第1項，因為被1除是沒有作用的)。這時用5乘以部分乘積并用3除，你可以得到答案35， 和前面的結果一樣。
　　 這里對 Choose(n,k) 的第二次優化是由以下特性產生的：

        Choose(n,k) = Choose(n, n-k).

生成所有組合元素

　　組合的第三個基本操作是根據給定條目個數 n 和子集大小 k 生成一個所有組合元素的清單。正如前面所示的 Choose 函數的問題一樣，Internet 上找到的 并不是最優方案。讓我們簡單看看一個典型的情況：給定 n 和 k 值，生成所有組合元素的解決方案，并且我將改進它。
　　假定你有四個姓名條目——Adam, Barb, Carl, Dave——你想得到所有這四個條目中每次選出兩個元素的組合。下面所示的 C# 代碼片斷將生成這個組合的六個元素：

// naive technique to generate all combinations
Console.WriteLine("\nAll elements of 4 names, 2 at a time: ");
string[] names = {"Adam", "Barb", "Carl", "Dave"};
for (int i = 0; i < names.Length; ++i)
{
 for (int j = i+1; j < names.Length; ++j)
 {
  Console.WriteLine( "{ " + names[i] + ", " + names[j] + " }" );
 }
}

如果你執行這個代碼，（正確的）結果將是：

        { Adam, Barb }, { Adam, Carl }, { Adam, Dave }, { Barb, Carl }, 
        { Barb, Dave }, { Carl, Dave }.

　　但是這里有三個問題。首先，如果你想要生成組合的所有元素時，這個方法運行很正常，但是如果你只想得到部分元素或一個特別元素呢？第二，這是一個對于特定問題的特定 解法，它并不具有普遍性。第三，只有當每個子集元素的條目個數 k 很小時，它才能工作得較好。
　　但是如果 k 非常大時會怎樣呢？如果你想一次從 n = 100 個的條目中挑出 50 個，你就不得不編寫50個循環或使用遞歸。
　　對于生成所有組合元素的一個更好的解決方案是實現一個 Successor（繼承）方法，它返回給定元素的下一個按詞典排序的元素。如果你將 Successor 和 ApplyTo 方法聯合使用，它 將某個數學組合映射到一個字符數組上，你將會具備一個有效的、具有普遍性的方法來生成所有組合元素。
　　Figure 6 的代碼表示了 Successor 方法。Successor 一開始就檢查這里是否存在下一個組合元素。舉個例子，假設你正在處理每次從 n＝5 個條目中取 k＝3 個元素。這里 有 10 種組合情況：

        { 0, 1, 2 } { 0, 3, 4 }
        { 0, 1, 3 } { 1, 2, 3 }
        { 0, 1, 4 } { 1, 2, 4 }
        { 0, 2, 3 } { 1, 3, 4 }
        { 0, 2, 4 } { 2, 3, 4 }

　　注意你可以確定詞典序列的最后一個元素，{ 2, 3, 4 }，因為這里只有一個元素它有第一個原子2——它等于 n－k 的值，或者換句話說，它有一個 n-k 的值在第0個位置上。這個關系一般來說對于所有的組合都是正確的。同樣地，你可以確定詞典序列的第一個元素，{ 0, 1, 2 }，因為這里只有一個元素的最后一個原子為 2，或者換句話說，這里有 n-k 的值在第 k－1 位置上。而且，一般來說這總是正確的。如果這里沒有有效的下一個元素 Successor 方法就返回 null。選擇返回 null 將導致拋出一個異�；蚍祷匾粋�錯誤代碼。
　　生成 Successor 元素的算法沒有使用任何特別的技巧。實質上你從最右邊的元素開始向左移動直到你定位于應該增加的最左邊的原子。這時你以索引 i 增加原子并重新安排所有原子到 i 的右邊比左邊的值大 1。舉個例子，設 n = 5 和 k = 3 并且你想得到組合{ 0, 3, 4 }的后繼者。索引 i 開始于地址 2（指向值為 4 的原子），并且左移直到它到地址 0（指向值為 0 的原子）。原子值被加1，并且右邊（3 和 4）的所有原子從數組左邊的值增加，得到結果{ 1, 2, 3 }。
　　一旦你有了 Successor 方法，便需要一個 ApplyTo 方法，它將某個組合元素放到一個字符串數組中。ApplyTo 方法很簡單：

public string[] ApplyTo(string[] strarr)
{
 if (strarr.Length != this.n)
  throw new Exception("Bad array size");
 string[] result = new string[this.k];
 for (long i = 0; i < result.Length; ++i)
  result[i] = strarr[this.data[i]];
 
 return result;
}

　　通過對字符串數組輸入參數的檢查，確保字符串個數的正確性之后，用子集 k 的大小創建一個結果數組。然后遍歷輸入字符串 ，并將一個引用存儲到結果數組相應的單元中。與組合所實現的許多操作一樣，如果你不從頭到尾跟蹤一兩個例子，所發生的事情并不是那么顯而易見。
　　根據適當的條目數和子集大小實例化一個 Combination 對象之后，創建一個字符串數組來保存結果組合元素。用一個 While 循環來遍歷所有組合元素——回想一下我們曾說過，當 不存下一個元素時，Successor 方法返回 null——并且 ApplyTo 方法將當前元素映射到原始字符串數組上。

結束語

　　在計劃和進行配置測試的過程中，組合是一個不可或缺的工具，尤其是在被稱為交互式分析的子領域里。舉個例子，假設你需要在一臺安裝了多個瀏覽器和多媒體播放器 的機器上測試產品。你想要從八個瀏覽器集合中選裝三個瀏覽器，從六個多媒體播放器集合中選裝兩個播放器來進行系統結合測試。這里有多少配置的組合呢？你怎樣才能 編寫程序列出這些配置？本文呈現的技術使得你很容易就計算出有 Choose(8,3) * Choose(6,2) = 840 個可能的測試配置。它也讓你很容易編程列出所有這些配置。
　　在檢查和測試執行路徑時，組合是很有用的。我將用一個經典的問題來舉例說明，它是一個分析執行路徑的代理（微軟常用這種例子問題來對測試工程師候選 人進行面試）。假設你在開發一個游戲。玩家進入一個鋪了地板磚的房間的西南角。玩家必須通過移動一塊地磚到東邊或移動一塊地磚到北邊以便自己移動到房間的東北角（換句話說玩家總是向出口方向移動并且不能 走回頭路）。如果這個房間很�。�只有 10 塊地磚長 6 塊地磚那么寬——玩家會有多少種不同的路徑走法？你能測試所有這些路徑嗎？如果移動到東邊用字母 E 代表而移動到北邊用字母 N 代表，一個到出口的可能路徑就是玩家先向東移動所有步然后一直向北：

        E E E E E E E E E E N N N N N N

        E N E N E N E N E N E N E E E E

如果你有問題和建議給 James，請發送到 testrun@microsoft.com