Überprüfen Sie, ob zwei Arrays denselben Inhalt haben (in beliebiger Reihenfolge).

Ich verwende Ruby 1.8.6 mit Rails 1.2.3 und muss feststellen, ob zwei Arrays dieselben Elemente haben, unabhängig davon, ob sie in derselben Reihenfolge sind oder nicht. Eines der Arrays enthält garantiert keine Duplikate (das andere könnte, in diesem Fall lautet die Antwort nein).

Mein erster Gedanke war

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

aber ich habe mich gefragt, ob es einen effizienteren oder idiomatischeren Weg gibt, dies zu tun.

Dies erfordert keine Konvertierung, um Folgendes festzulegen:

a.sort == b.sort

für zwei Arrays A und B: A und B haben den gleichen Inhalt, wenn: (A-B).blank? and (B-A).blank?

oder Sie können einfach nachsehen: ((A-B) + (B-A)).blank?

Auch wie von @ cort3z vorgeschlagen, funktioniert diese Lösung auch für polymorphe Arrays, d. H.

 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` 

::::::::::: BEARBEITEN ::::::::::::::

Wie in den Kommentaren vorgeschlagen, schlägt die obige Lösung für Duplikate fehl. Obwohl gemäß der Frage, die nicht einmal erforderlich ist, da der Fragesteller nicht an Duplikaten interessiert ist (er konvertiert seine Arrays vor dem Überprüfen in einen Satz und maskiert Duplikate und selbst wenn Sie sich diese ansehen Die akzeptierte Antwort verwendet er vor dem Überprüfen mit einem .uniq-Operator und maskiert auch Duplikate.). Wenn Sie dennoch an Duplikaten interessiert sind, wird dies durch Hinzufügen einer Überprüfung der Anzahl behoben (gemäß der Frage kann nur ein Array Duplikate enthalten). Die endgültige Lösung lautet also: A.size == B.size and ((A-B) + (B-A)).blank?

Geschwindigkeitsvergleiche

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 wird differencein 2.6 eingeführt.

Dies ergibt hier eine sehr schnelle, sehr lesbare Lösung wie folgt:

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

Ausführen der Benchmarks:

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

Hoffe das hilft jemandem!

Wenn die Elemente von aund bsind Comparable,

a.sort == b.sort

Korrektur der Antwort von @ mori basierend auf dem Kommentar von @ steenslag

Wenn Sie erwarten, [:a, :b] != [:a, :a, :b] to_setfunktioniert nicht. Sie können stattdessen die Frequenz verwenden:

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

Wenn Sie wissen, dass die Arrays gleich lang sind und keines der Arrays Duplikate enthält, funktioniert dies auch:

( array1 & array2 ) == array1

Erläuterung:& In diesem Fall gibt der Operator eine Kopie von a1 ohne alle in a2 nicht gefundenen Elemente zurück. Dies entspricht dem Original a1, wenn beide Arrays denselben Inhalt ohne Duplikate haben.

Analyse: Da die Reihenfolge unverändert ist, wird dies vermutlich als Doppeliteration implementiert, die so konsistent ist O(n*n), insbesondere bei großen Arrays, a1.sort == a2.sortdie im schlimmsten Fall schlechter abschneiden sollten O(n*logn).

Ein Ansatz besteht darin, das Array ohne Duplikate zu durchlaufen

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

Dies gibt ein Array von Wahrheiten zurück. Wenn false angezeigt wird, gibt das äußere include?true zurück. Sie müssen also das Ganze umkehren, um festzustellen, ob es sich um eine Übereinstimmung handelt.

kombinieren &und sizekann auch schnell sein.

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