1

我想知道。在 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)
4

2 回答 2

7

首先，对微基准测试要非常小心。我建议为此使用我的 gem fruity，请参阅文档了解原因。

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

第三，你的数据太小了，你无法理解发生了什么。例如，您的b变量包含 3 个元素。如果您将算法 inO(n^2)与 one in进行比较O(n)，那么 (3) 这么小n就不会很明显。

你可能想从：

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#&andArray#-基本上会在Set内部将参数转换为 a。数组上的all?andinclude?应该是最糟糕的解决方案，因为它会O(n^2)......如果你增加b.

一般的答案是：除非您确定需要优化，否则使用最易读的。

于 2013-02-08T18:07:23.457 回答
1

这取决于您的数据大小。对于您拥有的小型数据集；b.all? { |o| a.include? o }几乎每次都更快。

但是，如果您尝试使用更大的数组。例如 1000 个元素的数组，(a & b) == b.size速度要快得多。

我还尝试了相反的版本：(a | b) == a.size，它或多或少是相同的。

以下是（注释的）结果，其中a有 10000 个元素和b5000 个元素：

    user     system      total        real
0.010000   0.000000   0.010000 (  0.004445) # subset
0.000000   0.000000   0.000000 (  0.003073) # & (intersection)
1.620000   0.000000   1.620000 (  1.625472) # inject
0.000000   0.000000   0.000000 (  0.004485) # difference
0.530000   0.000000   0.530000 (  0.529042) # include
0.010000   0.000000   0.010000 (  0.004416) # | (union)
于 2013-02-08T17:33:38.493 回答