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

Je suis en utilisant Ruby 1.8.6 avec des Rails 1.2.3, et la nécessité de déterminer si deux matrices ont les mêmes éléments, indépendamment de si oui ou non ils sont dans le même ordre. L'un des tableaux est la garantie de ne pas contenir de doublons (l'autre pourrait, dans ce 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 si il y avait une plus efficace ou idiomatiques façon de faire.

  • double possible de Ruby - N'tableau contient tous les éléments de la matrice B>
  • Essayez de tableau.devrait - = ~ another_array case stackoverflow.com/questions/2978922/...
  • Vous pourriez avoir sauvé beaucoup de confusion par: 1) indiquant si les éléments des tableaux sont nécessairement sortable; et 2) de fournir un exemple simple pour clarifier ce que vous entendez par "si deux matrices ont les mêmes éléments" (par exemple, ne [1,2] et [2,1,1] ont les mêmes éléments?)
  • Ruby 2.6 a introduit difference qui offre une solution à la fois très rapide et très lisible. Plus d'infos ici.
InformationsquelleAutor Taymon | 2012-06-06
  1. 133

    Cela ne nécessite pas de conversion à définir:

    a.sort == b.sort
    • Pas de conversion? Qu'est-ce que .uniq.sort alors? En outre uniq est similaire à to_set en interne ainsi que des .to_a.sort
    • Accepter cela, car il est plus proche de ce que j'ai utilisé, mais sans le uniqs. En fait j'ai fini la création de l'un des tableaux avec des Range#to_a, donc je n'avais qu'à sort l'autre.
    • Cela ne fonctionnera pas si le tableau contient des éléments qui ne peuvent pas être simplement triés (par exemple, un tableau de hachages). sahil dhankhar la solution apparaît de plus de solution générale.
    InformationsquelleAutor Mori
  2. 38

    pour deux matrices A et B:
    A et B ont le même contenu, si:
    (A-B).blank? and (B-A).blank?

    ou vous pouvez vérifier:
    ((A-B) + (B-A)).blank?

    Aussi comme suggéré par @cort3z cette solution als0 fonctionne pour polymorphes tableaux j'.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`

    ::::::::::: MODIFIER :::::::::::::

    Comme suggéré dans les commentaires, solution ci-dessus échoue pour les doublons.Bien que, comme pour la question qui n'est même pas nécessaire, puisque la personne n'est pas intéressée par les doublons(il est la conversion de ses tableaux à la vérification et que les masques des doublons et même si vous regardez la accepté de répondre qu'il est à l'aide d'un .uniq opérateur avant de vérifier et que trop de masques doublons.). Mais encore si des doublons vous intéresse ,Juste l'ajout d'une case de nombre de fixer le même(comme par la question d'une seule table peut contenir des doublons). Donc, la solution finale sera:
    A.size == B.size and ((A-B) + (B-A)).blank?

    • Ceci ne fonctionnera pas si le tableau contient des doublons. E. g., si A=[1] et B=[1,1], à la fois (A-B) et (B-A) sera de retour vide. Voir Array Documentation.
    • tout à fait d'accord avec vous. J'ai modifié ma réponse à intégrer vos commentaires.Mais si vous avez un oeil de près à la question(ou la accepté de réponse), le demandeur est à l'aide de: a.to_set == b.to_set et l'on a accepté la réponse est à l'aide de a.uniq.sort == b.uniq.sort et les deux donnent exactement le même résultat que ((A-B) + (B-A)).blank? pour A=[1] et B=[1,1] d'accord ? Depuis qu'il a juste poser une amélioration par rapport à sa solution originale , ma solution fonctionne toujours 🙂 . d'accord?
    • Cette solution est très agréable, car il traite les objets de plusieurs types. Disons que vous avez A = [123, "test", [], some_object, nil] et B = A#because I am lazy, puis A.uniq.sort lèvera une erreur (comparaison de chaînes de caractères et tableaux a échoué).
    • Serait-ce le O(n) alors, puisque ça dépend de la taille de la matrice? (linéaire)
    • Il ne fonctionnera pas si les tableaux ont la même taille mais les éléments répétés ne sont pas les mêmes. Par exemple A = [1, 1, 2] et B = [1, 2, 2]
    InformationsquelleAutor Sahil Dhankhar
  3. 19

    Vitesse 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
    • btw, afin de elemetns n'affecte pas sort's de vitesse
    • Surpris moi... je m'attendais à par-set comparaison de surpasser tous les autres en raison de jeux de recherche de O(n) le temps de la complexité. De sorte que tout est bien mis en application tri aurait besoin de O(n logn). Alors que la coulée de jeux et la recherche de valeurs serait globalement en O(n) fois.
    • Je m'attends à to_set pour commencer à surperformer avec d'assez grands tableaux où O(n logn) serait de commencer à compter plus de l'effort nécessaire pour convertir le tableau d'ensemble
    • Ceci est utile, mais pas vraiment une réponse en elle-même? Peut-être mieux d'ajouter ce point à une solution existante?
    InformationsquelleAutor Morozov
  4. 16

    Lorsque les éléments de a et b sont Comparable,

    a.sort == b.sort

    Correction de @mori de la réponse repose sur @steenslag commentaire

    • Agréable et raisonnable.
    • ...quand a et b peuvent être triées.
    InformationsquelleAutor Jared Beck
  5. 12

    Ruby 2.6+

    Ruby introduit différence 2.6.

    Cela donne une très rapide, très lisible solution ici, comme suit:

    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

    De l'exécution de l'indice de référence:

    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

    Espère que ça aide quelqu'un!

    • la différence est la rupture dans ce cas, a = [1, 2, 3] b = [1, 2, 3, 4, 5] un.différence(b).tout? => false
    InformationsquelleAutor SRack
  6. 7

    Si vous 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
    • pourquoi ne pas simplement a.sort == b.sort si il se soucie de la fréquence?
    • Que faire si les articles ne sont pas comparables? ["", :b].frequency == [:b, ""].frequency #=> true
    • aussi, vous pouvez faire quelque chose de fonctionnel comme a.group_by{|i| i} == b.group_by{|i| i}
    InformationsquelleAutor Victor Moroz
  7. 6

    Si vous connaissez les tableaux sont de longueur égale et ni tableau contient des doublons, alors cela fonctionne aussi:

    ( array1 & array2 ) == array1

    Explication: la & opérateur dans ce cas renvoie une copie de a1 sans tous les éléments ne trouve pas dans a2, qui est le même que l'original a1 iff deux tableaux ont le même contenu avec pas de doublons.

    Analyse: étant Donné que la commande est inchangé, je devine que ce est implémenté sous la forme d'un double itération de manière cohérente O(n*n), notamment pis pour les grands tableaux de a1.sort == a2.sort qui doit effectuer avec le pire des cas O(n*logn).

    • Ne fonctionne pas toujours: a1 = [1,2,3], a2 = [2, 1, 3] a1 && a2 retourne [2,1,3] pour moi qui n'est pas égal à a1
    • ne pas vous dire qu'il ne fonctionne que lorsque a1==a2? Il peut fonctionner si array1 sur le côté droit de l'égalité est remplacé par array2, mais je doute que l'ordre des éléments retournés par & est garanti.
    • est un jeu opérateur d'intersection pour les tableaux, && est logique ET qu'ils sont très différents!
    InformationsquelleAutor Nat
  8. 1

    Une approche consiste à parcourir le tableau avec pas de doublons

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

    Cette fonction retourne un tableau de trues. Si tout faux s'affiche, puis l'extérieur include? retournera true. Ainsi, vous devez inverser le tout afin de déterminer si c'est un match.

    • Moroz, vous avez raison, et une fréquence de comptage serait tout simplement O(n).
    InformationsquelleAutor Ron
  9. 1

    combinant & et size peut être trop 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
    InformationsquelleAutor Todoroki