Vérifier si deux tableaux ont le même contenu (dans n'importe quel ordre)

Question

J'utilise Ruby 1.8.6 avec Rails 1.2.3, et je dois déterminer si deux tableaux ont les mêmes éléments, qu'ils soient ou non dans le même ordre. Il est garanti que l'un des tableaux ne contient pas de doublons (l'autre pourrait en contenir, auquel cas la réponse est non).

Ma première pensée a été

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

mais je me demandais s'il existait une manière plus efficace ou idiomatique de le faire.

Answer 1

Si vous attendez [:a, :b] != [:a, :a, :b] to_set ne fonctionne pas. Vous pouvez utiliser la fréquence à la place :

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

Answer 2

Si vous savez que les tableaux sont de longueur égale et qu'aucun d'entre eux ne contient de doublons, cela fonctionne également :

( array1 & array2 ) == array1

Explication : el & Dans ce cas, l'opérateur renvoie une copie de a1 sans les éléments non trouvés dans a2, qui est identique à l'original a1 si les deux tableaux ont le même contenu sans doublons.

Analyse : Étant donné que l'ordre est inchangé, je suppose que cela est implémenté comme une double itération de manière cohérente. O(n*n) est nettement plus mauvais pour les grandes matrices que a1.sort == a2.sort qui devrait fonctionner dans le pire des cas O(n*logn) .

Answer 3

Combinant & y size peut aussi être rapide.

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

Answer 4

Une approche consiste à itérer sur le tableau sans duplicatas

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

Cela renvoie un tableau de vérités. Si un faux apparaît, alors le tableau extérieur include? retournera vrai. Vous devez donc inverser l'ensemble pour déterminer s'il s'agit d'une correspondance.