В настоящее время я занимаюсь реализацией интересных структур данных в 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
Одна из проблем, с фильтром Блум является то, что он имеет возможность возвращения ложных срабатываний, ложно возвращает истину для включение элементов, которые никогда не были вставлены в фильтр.
Иногда фильтр ведет себя таким образом, что это легко проверяемым:
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 от него, изменяя количество хеш-функций и размер внутреннего буфера . Хотя этот подход может протестировать общую грубую правильность фильтра, я беспокоюсь, что он не сможет поймать ошибки , которые заставляют сообщать о неправильных значениях для отдельных случаев (например, false минус).
Am Я слишком пессимистично по поводу эффективности двух методов тестирования выше, или я пропускаю способ проверить такие классы, как фильтр Блума, который на выходе непредсказуема?