Я зараз переживаю з реалізацією цікавих структур даних у Ruby і досягла проблеми з тестовими функціями, які не мають передбачуваного результату. Я зараз працюю над Блум фільтр що я включив наступну реалізацію для повноти:
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
Одна з проблем із фільтром Bloom - це те, щовона має можливість повернення помилкових спрацьовувань шляхом помилкового повернення до істинності для включення елементів, які ніколи не були вставлені в фільтр.
Іноді фільтр веде себе таким чином, що легко випробувати:
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, який непередбачуваний?
Відповіді:
2 для відповіді № 1Ви маєте право вибрати ці значення просто сталося працювати - це погана ідея. Проте ваша друга ідея не так вже й погано.
Ви завжди повинні мати можливість перевірити ці значенняякі повинні знаходитися в фільтрі розквіту. Ви можете випадково генерувати ряд рядків і перевірити, що порогова сума є помилковими. Таким чином, якщо ви зміните хеш-функцію, ваші тестові модулі все одно працюватимуть і все одно повідомлятимуть, що фільтр має прийнятне хибне позитивне співвідношення.
0 для відповіді № 2
Тестування - це підтвердження ваших сподівань. Якщо ви не можете сказати собі, що повернеться фільтр Блум (якщо врахувати крихкість, як ви вже згадували), ви не очікуєте цього очікування. (Я клянусь, що не намагався зробити каламбур: P)
Моє перше почуття кишки було б підтвердження помилковопозитивний відсоток на N створених даних на всі цікаві алгоритми хешування. Це автоматично забезпечує максимальну безпеку, оскільки ви будете виконувати ці тести вручну.
Для цього я рекомендую мати тестовий код, достатній для вас, щоб висловити це так просто, як:
<попередження> Неперевірений код </ warning>
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
-1 для відповіді № 3
Фільтр Bloom - це космічно ефективна імовірнісна структура даних, яка використовується для перевірки того, чи є елемент членом набору. Можливі помилкові спрацьовування, але помилкових негативів немає.
Просто від опису того, що Блумфільтр робить, повинно бути ясно, що немає сенсу перевіряти на наявність помилкових спрацьовувань. Він не визначає, що є результатом позитивного тесту, тому ви не можете робити тести для цього, що очікує певного результату. Єдине, що ви можете гарантувати і, отже, перевірити:
- функція повертає логічне значення
- функція не викидає помилок
- немає помилкових негативів