Sprawdź, czy dwie tablice mają tę samą zawartość (w dowolnej kolejności)

Używam Ruby 1.8.6 z Railsami 1.2.3 i muszę określić, czy dwie tablice mają te same elementy, niezależnie od tego, czy są w tej samej kolejności. Jedna z tablic na pewno nie zawiera duplikatów (druga może, w takim przypadku odpowiedź brzmi nie).

Moja pierwsza myśl była taka

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

ale zastanawiałem się, czy istnieje bardziej skuteczny lub idiomatyczny sposób na zrobienie tego.

Nie wymaga to konwersji, aby ustawić:

a.sort == b.sort

dla dwóch tablic A i B: A i B mają tę samą zawartość, jeśli: (A-B).blank? and (B-A).blank?

lub możesz po prostu sprawdzić: ((A-B) + (B-A)).blank?

Również, jak sugeruje @ cort3z, to rozwiązanie als0 działa dla tablic polimorficznych, tj

 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` 

::::::::::: EDYTOWAĆ :::::::::::::

Jak zasugerowano w komentarzach, powyższe rozwiązanie zawodzi dla duplikatów, chociaż zgodnie z pytaniem, które nawet nie jest wymagane, ponieważ pytający nie jest zainteresowany duplikatami (konwertuje swoje tablice na zestaw przed sprawdzeniem i maskuje duplikaty, nawet jeśli spojrzysz na zaakceptowana odpowiedź, przed sprawdzeniem używa operatora .uniq, co również maskuje duplikaty). Ale nadal, jeśli interesują Cię duplikaty, samo dodanie sprawdzenia liczby naprawi to samo (zgodnie z pytaniem tylko jedna tablica może zawierać duplikaty). Tak więc ostatecznym rozwiązaniem będzie: A.size == B.size and ((A-B) + (B-A)).blank?

Porównanie prędkości

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

Ruby 2.6+

Ruby został wprowadzony differencew 2.6.

Daje to bardzo szybkie, bardzo czytelne rozwiązanie, takie jak:

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

Uruchamianie testów porównawczych:

a = Array.new(1000) { rand(100) }
b = Array.new(1000) { rand(100) }

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('difference') { a.difference(b).any? }
end

      sort     13.908k (± 2.6%) i/s -     69.513k in   5.001443s
     sort!     14.656k (± 3.0%) i/s -     73.736k in   5.035744s
    to_set     5.125k  (± 2.9%) i/s -     26.023k in   5.082083s
     minus     16.398k (± 2.2%) i/s -     83.181k in   5.074938s
difference     27.839k (± 5.2%) i/s -    141.048k in   5.080706s

Mam nadzieję, że to komuś pomoże!

Kiedy elementy ai bsą Comparable,

a.sort == b.sort

Korekta odpowiedzi @ mori na podstawie komentarza @ steenslag

Jeśli oczekujesz [:a, :b] != [:a, :a, :b] to_set, nie działa. Zamiast tego możesz użyć częstotliwości:

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

Jeśli wiesz, że tablice mają równą długość i żadna z nich nie zawiera duplikatów, to też działa:

( array1 & array2 ) == array1

Objaśnienie:& operator w tym przypadku zwraca kopię a1 sans jakieś elementy nie znaleziono w A2, która jest taka sama jak oryginalna a1 IFF obie tablice mają takie same treści bez żadnych duplikatów.

Analiza: Biorąc pod uwagę, że kolejność pozostaje niezmieniona, domyślam się, że jest to implementowane jako podwójna iteracja tak konsekwentnie O(n*n), co jest szczególnie gorsze w przypadku dużych tablic niż te, a1.sort == a2.sortktóre powinny działać w najgorszym przypadku O(n*logn).

łączenie &i sizemoże być również szybkie.

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

Jednym ze sposobów jest iteracja po tablicy bez duplikatów

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

Zwraca tablicę prawd. Jeśli pojawi się jakiekolwiek fałsz, to zewnętrzne include?zwróci wartość true. Dlatego musisz odwrócić całość, aby określić, czy pasuje.