測試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

這取決於您的數據大小。對於您的小數據集;幾乎每次都會有更快的速度。

但是，如果您嘗試更大的陣列。例如。 1000個元素的陣列，(a & b) == b.size相當快。

我也試過了相反的版本：(a | b) == a.size，差不多一樣。

這裏是（註釋）結果，其中a有10000元和b有5000個要素：

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) 

Answer 2

首先，要非常小心微標杆。我建議使用我的寶石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的大小，這將會很明顯。

一般的答案是：使用最清晰的，除非你確定你需要優化。