測試不可預知的功能

我目前正忙於在Ruby中實現有趣的數據結構，並且遇到了沒有可預測輸出的測試函數的問題。我目前工作的一個Bloom Filter，我已經包括下面的完整性實施：測試不可預知的功能

require "zlib" 

class BloomFilter 
    def initialize(size=100, hash_count=3) 
    raise(ArgumentError, "negative or zero buffer size") if size <= 0 
    raise(ArgumentError, "negative or zero hash count") if hash_count <= 0 

    @size = size 
    @hash_count = hash_count 
    @buffer = Array.new(size, false) 
    end 

    def insert(element) 
    hash(element).each { |i| @buffer[i] = true} 
    end 

    def maybe_include?(element) 
    hash(element).map { |i| @buffer[i] }.inject(:&) 
    end 

    private :hash 
    def hash(element) 
    hashes = [] 

    1.upto(@hash_count) do |i| 
     hashes << Zlib.crc32(element, i) 
    end 

    hashes.map { |h| h % @size } 
    end 
end

一個與布隆過濾器的問題是，它有虛假地返回true的返回誤報的可能性包含從未插入過濾器的元素。

有時候，過濾器行爲的方式，是容易測試：

b = BloomFilter.new(50, 5) 

b.insert("hello") 
puts b.maybe_include?("hello") # => true 
puts b.maybe_include?("goodbye") # => false

但是它有時雄鹿的趨勢，並以不可預測的方式行事。（我已經減少了緩衝區的大小，這裏迅速找到發生衝突。）

b = BloomFilter.new(5, 4) 

b.insert("testing") 
puts b.maybe_include?("testing") # => true 
puts b.maybe_include?("not present") # => false 
puts b.maybe_include?("false positive") # => true (oops)

因此突然間，我們有字符串「假陽性」提供......假陽性。我的問題是我們如何測試這個？

如果我們選擇恰好與我們的測試工作，然後我覺得測試值變得過於脆弱。例如，如果我們更改了散列函數，那麼我們可能仍然有一個完美正確的Bloom 由於我們選擇了來測試原始實現的值，所以開始失敗某些測試的篩選器。
我的第二個想法是，以測試該過濾器在預期方式僅通過檢查，我們通過改變內部緩衝區的散列函數的數量和規模得到大致從它的expected number of false positives 行爲。雖然這種方法可能會測試整個粗糙過濾器的正確性，但我擔心它將無法捕獲導致其針對個別情況報告不正確值的錯誤（例如，假負面因素）。

我是不是太悲觀測試它上面的兩種方法的效果還是我失去了一個方法來測試類，如布隆過濾器，其輸出是不可預測的？

來源

2011-12-20 xoebus

你是對的，選擇值剛剛發生工作是一個壞主意。但是，你的第二個想法並不是那麼糟糕。

您應該始終能夠測試應該在bloom過濾器中存在的值。您可以隨機生成多個字符串，並檢查閾值數量是否爲誤報。這樣，如果您更改散列函數，您的單元測試仍然可以工作，並且仍會報告過濾器具有可接受的誤判率。

來源

2011-12-20 01:37:08 Kane

-1

布隆過濾器是一種空間高效的概率數據結構，用於測試某個元素是否爲集的成員。假陽性是可能的，但是假陰性不是。

只是從布盧姆過濾器的作用的描述中，應該清楚，測試誤報是沒有意義的。它本質上沒有定義什麼是積極測試的結果，所以你不能對它進行測試，以期得到一定的結果。你能保證，因此測試的唯一的事情是：

該函數返回一個布爾值
函數不拋出任何錯誤
沒有漏報

來源

2011-12-20 01:37:57 deceze

測試是關於確認你的期望。如果你無法爲自己弄清楚布盧姆過濾器將會返回什麼（考慮到脆弱性，正如你所提到的那樣），你不能指望有這樣的期望。（我發誓我沒有試圖做一個雙關語：P）

我的第一個直覺就是確認在所有有趣的散列算法中產生的N個輸入的假陽性百分比。這使您自動爲您提供與手動執行這些測試相同的安全性。

要做到這一點，我會建議有測試代碼因素足以讓你表達簡單：

<警告>待驗證碼< /警告>

class BloomFilterTestCase << TestCase 
    def bloom_incidence(alg, pop, false_positives) 
    define_method("test_bloom_incidence_${alg}_${pop}_${false_positives}") do 
     # code code code 
    end 
    end 

    bloom_incidence :naive, 50, 0.05 
end

來源

2011-12-20 01:39:01 pkoch

測試不可預知的功能

回答

相關問題