2011-03-30 203 views
4

我想測試的一些算法如何測試算法的實現?

如果你想想一個TDD/BDD重點實施...一個考驗將是

Scenario: doubling search 
Given an ordered array "[2,3,4,5,6,7]" 
When I look for "4" with "doubling search" in it 
Then the result must be "2" 

我想確保我的算法是做得很好...那麼,你將如何測試算法實現?

回答

3

你測試的算法的每個執行同樣的方式:採取輸入,通過手工計算你的預期產出,並比較其算法爲您提供的輸出。

如果你在使用接口的語言,這樣做,你可以有一個通用的測試採取類型接口的參數,並將它通過傳遞你實現你的實際測試中被調用。這確保所有算法都基於其接口進行相同的測試。

// double search implemented by using the search and multiplying by 2 
algorithm multDoubleSearch 
    define input array 
    define input search 

    for each i in array 
     if i = search * 2 
      return index of i 
    end 
    return -1 
end. 

// double search implemented by dividing the values by 2 
algorithm divDoubleSearch 
    define input array 
    define input search 

    for each i in array 
     if i/2 = search 
      return index of i 
    end 
    return -1 
end. 


test mytest 
    define array {2 3 4 5 6 7} 
    define search 2 

    define resultMult = multDoubleSearch(array,search) 
    assert resultMult == 2 // 4 is index 2, assuming 0 indexed 

    define resultDiv = divDoubleSearch(array,search) 
    assert resultDiv == 2 // 4 is index 2, assuming 0 indexed 
end. 
2

那麼這取決於你手頭有什麼。

除了手動提供輸入和輸出以測試角落案例和少量其他輸入的常見測試(請參閱JUnit或任何流行語言中的類似框架)之外,您還可以編寫低效但簡單的版本你的算法(或者是產生相同的結果,通常是不完全一樣的算法精確的任何東西)和測試針對的版本,無論是對所有可能的輸入或者如果使用Fuzztester和一些隨機化是不可能的。爲後來

一個例子是測試一個複雜的排序算法(假設堆排序)對選擇排序。如果你優化了代碼,並且手邊已經有一個經過驗證和測試的版本(這本身就是一個遞歸問題),那也可以。

你的具體情況,你可以只是比較您的版本對一個簡單的二進制搜索 - 其標準庫肯定已經有 - 隨機輸入產生隨機大小的數組不應該是問題。