Проверьте, имеют ли два массива одинаковое содержимое (в любом порядке)

Я использую Ruby 1.8.6 с Rails 1.2.3, и нужно определить, имеют ли два массива одинаковые элементы, независимо от того, находятся ли они в том же порядке. Один из массивов гарантированно не содержит дубликатов (другой может, и в этом случае ответ отрицательный).

моей первой мыслью было

require 'set'
a.to_set == b.to_set

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

7 67
arrays ruby-on-rails string-comparison

7 ответов:

Это не требует преобразования в наборе:

a.sort == b.sort
105

для двух массивов A и B: A и B имеют одинаковое содержимое, если: (A-B).blank? and (B-A).blank?

или вы можете просто проверить: ((A-B) + (B-A)).blank?

также как предложено @cort3z это решение als0 работает для полиморфных массивов т. е.

 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`

::::::::::: править :::::::::::::

как было предложено в комментариях, выше решение не работает для дубликатов.Хотя в соответствии с вопросом, который даже не требуется, поскольку Аскер не заинтересован в дубликатах(он преобразует свои массивы чтобы установить перед проверкой и что маски дублирует и даже если вы посмотрите на принятый ответ он использует.оператор uniq перед проверкой и это тоже маскирует дубликаты.). Но все же ,если вас интересуют дубликаты, просто добавление проверки подсчета исправит то же самое(в соответствии с вопросом только один массив может содержать дубликаты). Так что окончательное решение будет: A.size == B.size and ((A-B) + (B-A)).blank?

35

когда элементы a и b are Comparable,

a.sort == b.sort

исправление ответа @mori на основе комментария @steenslag

14

скорость comparsions

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
13

Если вы ожидаете [: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
6

если вы знаете, что массивы имеют одинаковую длину и ни один массив не содержит дубликатов, то это тоже работает:

( array1 & array2 ) == array1

объяснение: the & оператор в этом случае возвращает копию a1 без каких-либо элементов, не найденных в a2, что совпадает с исходным A1, если оба массива имеют одинаковое содержимое без дубликатов.

анализ: учитывая, что порядок не изменился, я предполагаю, что это реализовано как двойная итерация, поэтому последовательно O(n*n), заметно хуже для больших массивов, чем a1.sort == a2.sort который должен работать с худшим случаем O(n*logn).

4

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

# assume array a has no duplicates and you want to compare to b
!a.map { |n| b.include?(n) }.include?(false)

Это возвращает массив истины. Если появляется какое-либо ложное, то внешнее include? вернет true. Таким образом, вы должны инвертировать все это, чтобы определить, соответствует ли это.

1