测试不可预测的功能

Question

我目前正在忙于在 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 由于我们选择的值，过滤器开始无法通过某些测试 测试原始实现。

• 我的第二个想法是测试过滤器的行为是否符合预期 通过检查我们是否大致获得了预期的数量 错误的 积极因素 通过改变散列函数的数量和大小 内部缓冲区。虽然这种方法可能会测试整体粗糙度 过滤器的正确性我担心它无法捕获 导致它报告个别情况的错误值（例如 false 我

我是否对上面两种测试方法的有效性过于悲观，或者我是否缺少一种测试类（例如输出不可预测的布隆过滤器）的方法？

Answer 1

你是对的，选择恰好起作用的价值观是一个坏主意。然而，你的第二个想法还不错。

您应该始终能够测试布隆过滤器中应有的值是否存在。您可以随机生成多个字符串，并检查阈值数量是否为误报。这样，如果您更改哈希函数，您的单元测试仍然可以工作，并且仍然会报告过滤器具有可接受的误报率。

Answer 2

测试是为了确认您的期望。如果您无法自己推断布隆过滤器将返回什么（考虑到脆弱性，正如您提到的），您就不能期望有这种期望。 （我发誓我不是想搞双关语：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

Answer 3

布隆过滤器是一种节省空间的概率数据结构，用于测试元素是否是集合的成员。误报是可能的，但误报则不然。

仅从布隆过滤器功能的描述就可以清楚地看出，测试误报是没有意义的。阳性测试的结果本质上是不确定的，因此您无法对其进行预期特定结果的测试。您唯一可以保证并测试的事情是：

• 函数返回一个布尔值
• 函数不会抛出任何错误
• 没有漏报