ruby - 在 Ruby 中测试数组包含的最快方法

Question

我在想。在 Ruby 中测试一个数组是否包含另一个数组的最快方法是什么？所以我构建了这个小基准脚本。很想听听您对比较方法的看法。您是否知道其他一些 - 也许更好的方法？

require 'benchmark'
require 'set'

a = ('a'..'z').to_a.shuffle
b = ["b","d","f"]

Benchmark.bm do |x|
  x.report do
      10000.times do
          Set[b].subset?(a.to_set)
      end
  end
  x.report do
      10000.times do
          (a & b).count == b.size
      end
  end
    x.report do
      10000.times do
          (a.inject(0) {|s,i| s += b.include?(i)?1:0 } == b.size)
      end
    end
    x.report do
      10000.times do
          (b - a).empty?
      end
    end
    x.report do
      10000.times do
          b.all? { |o| a.include? o }
      end
    end
end

和结果:

     user     system      total        real
 0.380000   0.010000   0.390000 (  0.404371)
 0.050000   0.010000   0.060000 (  0.075062)
 0.140000   0.000000   0.140000 (  0.140420)
 0.130000   0.000000   0.130000 (  0.136385)
 0.030000   0.000000   0.030000 (  0.034405)

Answer 1

首先，要非常小心地进行微观基准测试。我推荐使用我的 gem fruity为此，请参阅文档了解原因。

其次，你想比较你的数组的创建加上比较，还是只是比较？

第三，您的数据太小，您将无法理解正在发生的事情。例如，您的 b 变量包含 3 个元素。如果将 O(n^2) 中的算法与 O(n) 中的算法进行比较，那么小的 n (3) 它不会很明显。

您可能希望从:

require 'fruity'
require 'set'

a = ('a'..'z').to_a.shuffle
b = %w[b d f]
a_set = a.to_set
b_set = b.to_set

compare do
  subset        { b_set.subset?(a_set) }
  intersect     { (a & b).size == b.size }
  subtract      { (b - a).empty? }
  array_include { b.all?{|o| a.include? o} }
  set_include   { b.all?{|o| a_set.include? o} }
end

给予:

Running each test 2048 times. Test will take about 2 seconds.
set_include is faster than subset by 1.9x ± 0.1
subset is faster than intersect by 60% ± 10.0%
intersect is faster than array_include by 40% ± 1.0%
array_include is faster than subtract by 1.9x ± 0.1

请注意，Array#& 和 Array#- 基本上会在内部将参数转换为 Set。数组上的all?和include?应该是最差的方案，因为会是O(n^2)……这个如果您增加 b 的大小，这一点会很明显。

一般答案是:使用最清晰的，除非您确定需要优化。