Тестирование непредсказуемых функций - PullRequest
Новая
       18

Тестирование непредсказуемых функций

3 голосов
/ 20 декабря 2011

В настоящее время я работаю над реализацией интересных структур данных в 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)

Итак, внезапно у нас есть строка «ложное срабатывание», обеспечивающая ... ложное срабатывание. Мой вопрос: как мы можем это проверить?

  • Если мы выберем значения, которые просто произойдут для работы с нашими тестами, тогда я чувствую, что тесты становятся слишком хрупкими. Например, если мы изменим функция хеширования, то мы все еще можем иметь совершенно правильный Блум Фильтр, который начинает проваливать некоторые тесты из-за значений, которые мы выбрали проверить оригинальную реализацию.

  • Моей второй мыслью было проверить, что фильтр ведет себя ожидаемым образом. кстати, просто проверяя, что мы получаем примерно ожидаемое число ложный позитивы из него, варьируя количество хэш-функций и размер внутренний буфер. Хотя этот подход может проверить общую грубость Правильность фильтра волнуюсь, что он не сможет отловить ошибки, которые приводят к тому, что он сообщает неверные значения для отдельных случаев (например, ложные негативы).

Я слишком пессимистично оцениваю эффективность двух методов тестирования, описанных выше, или мне не хватает способа протестировать классы, такие как фильтр Блума, результаты которого непредсказуемы?

Ответы [ 3 ]

2 голосов
/ 20 декабря 2011

Вы правы, что выбор значений, которые просто случаются для работы, является плохой идеей. Однако ваша вторая идея не так уж и плоха.

Вы всегда должны иметь возможность проверить наличие значений, которые должны быть в фильтре Блума. Вы можете случайным образом сгенерировать количество строк и проверить, что пороговое количество ложных срабатываний. Таким образом, если вы измените хеш-функцию, ваши модульные тесты будут по-прежнему работать и сообщать, что фильтр имеет приемлемое отношение ложных срабатываний.

0 голосов
/ 20 декабря 2011

Тестирование - это подтверждение ваших ожиданий.Если вы не можете сами понять, что будет возвращать фильтр Блума (учитывая хрупкость, как вы уже упоминали), вы не можете ожидать такого ожидания.(Клянусь, я не пытался сделать каламбур: 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
0 голосов
/ 20 декабря 2011

Фильтр Блума - это компактная вероятностная структура данных, которая используется для проверки того, является ли элемент членом набора.Ложные срабатывания возможны, но ложные отрицания не возможны.

Только из описания того, что делает фильтр Блума, должно быть ясно, что нет смысла проверять наличие ложных срабатываний.По сути, это не определено, каков результат положительного теста, поэтому вы не можете сделать для него тесты, которые ожидают определенного результата.Единственное, что вы можете гарантировать и, следовательно, проверить:

  • функция возвращает логическое значение
  • функция не выдает никаких ошибок
  • нетложные негативы
...