测试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

首先,要非常小心微基准测试.我建议使用我的宝石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.

一般的答案是:除非您确定需要优化,否则请使用最清晰的.