структуры данных: итерация по двум массивам против преобразования в наборы и выполнение операции пересечения в ruby

Question

Допустим, у меня есть a1 и a2:

a1 = [1,2,3]
a2 = [4,2,5]

Чтобы узнать, разделяет ли a1 какие-либо элементы с a2, я могу зациклить каждый элемент и сравнить каждый элемент:

def intersect?(x,y)
  a1.each do |x|
    a2.each do |y|
      if x == y return true
    end
  end
  false
end

Но еще проще, (a1.to_set & a2.to_set).present? дает мне тот же ответ.

Я предполагаю, что операция установки быстрее и эффективнее?Если это так, то верно ли это, учитывая накладные расходы (если таковые имеются) операции .to_set на каждом массиве?

tia

Answer 1

Ответ

steenslag содержал интересное наблюдение, что array & array был быстрее, чем set & set. Похоже, что большая часть этого штрафа связана с получением ключей из базового хеша первого набора для перечисления. Гибридный подход с использованием массива для левой стороны операции и установки для правой руки еще быстрее. Если вы хотите знать только, есть ли пересечение, такой же подход с #any? еще быстрее:

#!/usr/bin/env ruby

require 'set'
require 'benchmark'

f = 10_000
ar1 = (1..(10*f)).to_a # 100_000 elements
ar2 = ((5*f)..(15*f)).to_a # also 100_000 elements
set1 = ar1.to_set
set2 = ar2.to_set
n = 10

Benchmark.bm(10) do |testcase|
  testcase.report('Array'){ n.times{ ar1 & ar2 } }
  testcase.report('Set'){ n.times{ set1 & set2 } }
  testcase.report('Set2'){ n.times{ ar1.select{ |element| set2.include? element } } }
  testcase.report('Set2present'){ n.times{ ar1.any?{ |element| set2.include? element } } }
end


$ ruby -v => ruby 1.9.2p290 (2011-07-09 revision 32553) [x86_64-darwin10.8.0]

                user     system      total        real
Array       0.680000   0.030000   0.710000 (  0.720882)
Set         1.130000   0.020000   1.150000 (  1.150571)
Set2        0.430000   0.000000   0.430000 (  0.434957)
Set2present  0.210000   0.010000   0.220000 (  0.220990)

Answer 2

Удивительно, но метод & для Array быстрее, чем метод Set для довольно больших коллекций:

require 'set'
require 'benchmark'
f = 10_000
ar1 = (1..(10*f)).to_a # 100_000 elements
ar2 = ((5*f)..(15*f)).to_a # also 100_000 elements
set1 = ar1.to_set
set2 = ar2.to_set
n = 10

Benchmark.bm(10) do |testcase|
  testcase.report('Array'){ n.times{ ar1 & ar2 } }
  testcase.report('Set'){ n.times{ set1 & set2 } }
end

Результат:

                 user     system      total        real
Array        1.380000   0.030000   1.410000 (  1.414634)
Set          2.310000   0.020000   2.330000 (  2.359317)

Answer 3

Я просто хочу остановиться на превосходных ответах Стинслага и Дбенхура. В частности, я хотел знать, будет ли SortedSet работать лучше. Сначала меня удивило, что тип Ruby Set не был реализован как отсортированный набор, так как я пришел из C ++; STL по умолчанию использует упорядоченный набор, и вам обычно нужно указать unordered_set, если вы не хотите упорядочивать.

Я также хотел знать, имел ли размер набор, как предлагалось в некоторых других ответах.

require 'set'
require 'benchmark'

f = 20 # 10_000
ar1 = (1..(10*f)).to_a # 100_000 elements
ar2 = ((5*f)..(15*f)).to_a # also 100_000 elements
set1 = ar1.to_set
set2 = ar2.to_set
sset1 = SortedSet.new(ar1)
sset2 = SortedSet.new(ar2)
n = 20000 # 10

Benchmark.bm(10) do |testcase|
  testcase.report('Array'){ n.times{ ar1 & ar2 } }
  testcase.report('Set'){ n.times{ set1 & set2 } }
  testcase.report('SortedSet') { n.times{ sset1 & sset2 } }
  testcase.report('Set2'){ n.times{ ar1.select{ |element| set2.include? element } } }
  testcase.report('Set2present'){ n.times{ ar1.any?{ |element| set2.include? element } } }

  testcase.report('SortedSet2'){ n.times{ ar1.select{ |element| sset2.include? element } } }
  testcase.report('SortedSet2present'){ n.times{ ar1.any?{ |element| sset2.include? element } } }
end

Вот результаты для f=20; n=20000:

$ ruby set.rb
                 user     system      total        real
Array        1.950000   0.010000   1.960000 (  1.963030)
Set          3.330000   0.040000   3.370000 (  3.374105)
SortedSet    3.810000   0.040000   3.850000 (  3.860340)
Set2         1.410000   0.010000   1.420000 (  1.427221)
Set2present  0.760000   0.000000   0.760000 (  0.759447)
SortedSet2   1.420000   0.000000   1.420000 (  1.446559)
SortedSet2present  0.770000   0.010000   0.780000 (  0.770939)

А вот результаты для f=10000; n=10:

$ ruby set.rb
                 user     system      total        real
Array        0.910000   0.020000   0.930000 (  0.939325)
Set          1.270000   0.010000   1.280000 (  1.293581)
SortedSet    1.220000   0.010000   1.230000 (  1.229650)
Set2         0.550000   0.000000   0.550000 (  0.552708)
Set2present  0.290000   0.010000   0.300000 (  0.291845)
SortedSet2   0.550000   0.000000   0.550000 (  0.561049)
SortedSet2present  0.330000   0.000000   0.330000 (  0.339950)

Так, для больших наборов, похоже, что Set лучше, чем SortedSet; и для небольших наборов SortedSet лучше, чем Set. При использовании обозначения &, Array быстрее, чем любой. Похоже, SortedSet2present работает значительно эффективнее с большими наборами, тогда как Set2present работает более эффективно с маленькими наборами.

Принимая во внимание, что Set реализовано с использованием Hash, SortedSet - это RBTree (реализовано в C). В обоих случаях & реализован в Ruby, а не в C.

Answer 4

Должно быть быстрее для больших массивов.Ваш метод выполняется за O (m * n) времени, потому что он должен зацикливаться на обоих массивах.Для таблиц из 3-х элементов это, в основном, незначительно, но для больших таблиц это может быть очень дорого.

Второй метод будет использовать поиск по хешу, который выполняется намного быстрее, но сначала массивы нужно помещать в наборы.

Что вы должны сделать, это попробовать оба метода, используя массивы размеров, которые вы ожидаете увидеть в своем приложении, и посмотреть, какой из них быстрее.Если они примерно одинакового размера, вы можете выбрать тот, который, по вашему мнению, будет более понятным.

Answer 5

Правда в том, что с такими маленькими массивами они либо будут практически одинаковыми, либо списки будут быстрее, чем наборы.

Достойная реализация множеств выполнит операции над множествами быстрее, чем вы можете выполнять операции над списками, НОесть некоторые накладные расходы.Если вы хотите знать, что будет делать ваша реализация, используйте большие наборы / списки и протестируйте.