Я использую Ruby 1.8.6 с Rails 1.2.3, и мне нужно определить, имеют ли два массива одни и те же элементы, независимо от того, находятся они в одном порядке. Один из массивов гарантированно не содержит дубликатов (другой может, и в этом случае ответ отрицательный).
Моя первая мысль была
require 'set'
a.to_set == b.to_set
но мне было интересно, был ли более эффективный или идиоматический способ сделать это.
Для этого не требуется преобразование:
a.sort == b.sort
для двух массивов A и B:
A и B имеют одинаковое содержимое, если:
(A-B).blank? and (B-A).blank?
или вы можете просто проверить:
((A-B) + (B-A)).blank?
Также, как было предложено @cort3z, это решение als0 работает для полиморфных массивов i.e
A = [1 , "string", [1,2,3]]
B = [[1,2,3] , "string", 1]
(A-B).blank? and (B-A).blank? => true
# while A.uniq.sort == B.uniq.sort will throw error `ArgumentError: comparison of Fixnum with String failed`
::::: EDIT:::::
Как было предложено в комментариях, решение выше для дубликатов. Хотя вопрос не требуется даже потому, что его не интересуют дубликаты (он преобразует свои массивы для установки перед проверкой, и это маскирует дубликаты и даже если вы смотрите на accepeted ответ, который он использует оператором .uniq перед проверкой, и это слишком маскирует дубликаты.). Но все же, если вас интересуют дубликаты, просто добавление проверки количества будет исправлять то же самое (по одному вопросу только один массив может содержать дубликаты). Таким образом, окончательное решение будет:
A.size == B.size and ((A-B) + (B-A)).blank?
Сравнения скорости
require 'benchmark/ips'
require 'set'
a = [1, 2, 3, 4, 5, 6]
b = [1, 2, 3, 4, 5, 6]
Benchmark.ips do |x|
x.report('sort') { a.sort == b.sort }
x.report('sort!') { a.sort! == b.sort! }
x.report('to_set') { a.to_set == b.to_set }
x.report('minus') { ((a - b) + (b - a)).empty? }
end
Warming up --------------------------------------
sort 88.338k i/100ms
sort! 118.207k i/100ms
to_set 19.339k i/100ms
minus 67.971k i/100ms
Calculating -------------------------------------
sort 1.062M (± 0.9%) i/s - 5.389M in 5.075109s
sort! 1.542M (± 1.2%) i/s - 7.802M in 5.061364s
to_set 200.302k (± 2.1%) i/s - 1.006M in 5.022793s
minus 783.106k (± 1.5%) i/s - 3.942M in 5.035311s
Когда элементы a и b Comparable,
a.sort == b.sort
Коррекция ответа @mori на основе комментария @steenslag
Если вы ожидаете, что [:a, :b] != [:a, :a, :b] to_set не работает. Вместо этого вы можете использовать частоту:
class Array
def frequency
p = Hash.new(0)
each{ |v| p[v] += 1 }
p
end
end
[:a, :b].frequency == [:a, :a, :b].frequency #=> false
[:a, :b].frequency == [:b, :a].frequency #=> true
Если вы знаете, что массивы имеют одинаковую длину и ни один из них не содержит дубликатов, то это тоже работает:
( array1 & array2 ) == array1
Объяснение: оператор & в этом случае возвращает копию a1 без любых элементов, не найденных в a2, что совпадает с исходным a1, если оба массива имеют одинаковое содержимое без дубликатов.
Анализ: Учитывая, что порядок неизменен, я предполагаю, что это реализовано в виде двойной итерации, поэтому последовательно O(n*n), что заметно хуже для больших массивов, чем a1.sort == a2.sort который должен работать в худшем случае. O(n*logn).
Один из подходов - перебирать массив без дубликатов
# assume array a has no duplicates and you want to compare to b
!a.map { |n| b.include?(n) }.include?(false)
Возвращает массив истин. Если появится какое-либо ложное сообщение, внешний include? вернет true. Таким образом, вы должны инвертировать все это, чтобы определить, соответствует ли оно.
комбинируя & и size может быть слишком быстро.
require 'benchmark/ips'
require 'set'
Benchmark.ips do |x|
x.report('sort') { a.sort == b.sort }
x.report('sort!') { a.sort! == b.sort! }
x.report('to_set') { a.to_set == b.to_set }
x.report('minus') { ((a - b) + (b - a)).empty? }
x.report('&.size') { a.size == b.size && (a & b).size == a.size }
end
Calculating -------------------------------------
sort 896.094k (±11.4%) i/s - 4.458M in 5.056163s
sort! 1.237M (± 4.5%) i/s - 6.261M in 5.071796s
to_set 224.564k (± 6.3%) i/s - 1.132M in 5.064753s
minus 2.230M (± 7.0%) i/s - 11.171M in 5.038655s
&.size 2.829M (± 5.4%) i/s - 14.125M in 5.010414s
Рубин 2. 6+
Руби внес difference в 2.6.
Это дает очень быстрое, очень удобочитаемое решение здесь, а именно:
a = [1, 2, 3, 4, 5, 6]
b = [1, 2, 3, 4, 5, 6]
a.difference(b).any?
# => false
a.difference(b.reverse).any?
# => false
a = [1, 2, 3, 4, 5, 6]
b = [1, 2, 3]
a.difference(b).any?
# => true
Запуск тестов:
a = Array.new(1000) { rand(100) }
b = Array.new(1000) { rand(100) }
Benchmark.bmbm do |x|
x.report('sort') { a.sort == b.sort }
x.report('sort!') { a.sort! == b.sort! }
x.report('to_set') { a.to_set == b.to_set }
x.report('minus') { ((a - b) + (b - a)).empty? }
x.report('difference') { a.difference(b).any? }
end
user system total real
sort 0.000157 0.000033 0.000190 ( 0.000186)
sort! 0.000106 0.000002 0.000108 ( 0.000104)
to_set 0.000278 0.000002 0.000280 ( 0.000277)
minus 0.000089 0.000002 0.000091 ( 0.000087)
difference 0.000051 0.000002 0.000053 ( 0.000049)
Надеюсь, что это помогает кому-то!