Estoy usando Ruby 1.8.6 con Rieles 1.2.3, y la necesidad de determinar si dos matrices tienen los mismos elementos, independientemente de si están o no en el mismo orden. Una de las matrices se garantiza que no contiene duplicados (el otro, en cuyo caso la respuesta es no).

Mi primer pensamiento fue

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

pero me preguntaba si había una manera más eficiente idiomáticas o forma de hacerlo.

  • posibles duplicados de Ruby – ¿Una matriz contienen todos los elementos de la matriz B
  • Trate de matriz.debe =~ another_array de verificación stackoverflow.com/questions/2978922/…
  • Usted podría haber ahorrado un montón de confusión por: 1) que indica si los elementos de las matrices son necesariamente ordenable; y 2) proporcionar un ejemplo sencillo para aclarar lo que quiere decir, «si dos matrices tienen los mismos elementos» (por ejemplo, hacer [1,2] y [2,1,1] tienen los mismos elementos?)
  • Ruby 2.6 ha introducido difference que ofrece una solución muy rápida y muy legible. Más info aquí.
InformationsquelleAutor Taymon | 2012-06-06

9 Comentarios

  1. 128

    Esto no requiere de conversión para establecer:

    a.sort == b.sort
    • De salir de la uniqs, que la máscara de duplicados.
    • La conversión No? ¿Qué es .uniq.sort entonces? Además de uniq es similar a to_set internamente, además de otras .to_a.sort
    • La aceptación de este, ya que es la más cercana a lo terminé usando, aunque sin la uniqs. En realidad terminé la creación de una de las matrices con Range#to_a, así que sólo tuve que sort el otro.
    • Esto no funcionará si la matriz contiene elementos que no pueden ser simplemente ordenados (por ejemplo, una matriz de hash). sahil dhankhar la solución parece ser una solución más general.
  2. 38

    para dos matrices a y B:
    A y B tienen el mismo contenido si:
    (A-B).blank? and (B-A).blank?

    o simplemente puede comprobar:
    ((A-B) + (B-A)).blank?

    También como sugerido por @cort3z esta solución als0 obras para polimórficos matrices yo.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` 

    ::::::::::: EDITAR :::::::::::::

    Como se sugiere en los comentarios, por encima de solución de falla para los duplicados.Aunque como por la cuestión de que no es ni siquiera necesario ya que el autor de la pregunta no está interesado en los duplicados(que es la conversión de sus matrices para establecer antes de la comprobación y que las máscaras de duplicados, incluso si nos fijamos en la accepeted respuesta es con un .uniq operador antes de comprobar y que también las máscaras de duplicados.). Pero aún si los duplicados de su interés ,Sólo la adición de un cheque de conteo de revisión de la misma(según la pregunta, una matriz puede contener duplicados). Así que la solución final será:
    A.size == B.size and ((A-B) + (B-A)).blank?

    • Esto se producirá si el array contiene duplicados. E. g., si A=[1] y B=[1,1], tanto (A-B) y (B-A) volverá en blanco. Consulte Documentación de la Matriz.
    • totalmente de acuerdo con usted. He modificado mi respuesta a incorporar sus comentarios.Pero si usted tiene un vistazo de cerca a la pregunta(o la aceptación de la respuesta), el usuario que pregunta es el uso de: a.to_set == b.to_set y la aceptación de respuesta es el uso de a.uniq.sort == b.uniq.sort y ambos dan exactamente el mismo resultado como ((A-B) + (B-A)).blank? para A=[1] y B=[1,1] de acuerdo ? Ya que él sólo estaba pidiendo una mejora con respecto a su solución original , mi solución original todavía funciona 🙂 . de acuerdo?
    • Esta solución es bastante agradable, ya que se encarga de los objetos de varios tipos. Dicen que usted tiene A = [123, "test", [], some_object, nil] y B = A#because I am lazy, entonces A.uniq.sort va a tirar error (comparación de la cadena y de la Matriz de error).
    • Sería O(n), entonces ya depende de el tamaño de la matriz? (lineal)
  3. 19

    Velocidad 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
    • por cierto, el fin de elemetns no afecta sort‘s de velocidad
    • Me sorprendió… yo esperaba que por-set comparación a superar a todos los demás, debido a los conjuntos de búsqueda O(n) tiempo de complejidad. De modo que cualquier bien implementado el tipo se requiere O(n logn). Mientras que el casting para los conjuntos y buscan los valores por lo general lo hacen en O(n) tiempo.
    • Me gustaría esperar to_set para iniciar superando con lo suficientemente grande como matrices de donde O(n logn) sería empezar a importar más que el esfuerzo que se requiere para convertir la matriz para establecer
    • Esto es útil, pero no es realmente una respuesta en sí misma? Tal vez sería mejor agregar esto a una solución existente?
  4. 14

    Cuando los elementos de a y b son Comparable,

    a.sort == b.sort

    Corrección de @mori de la respuesta basada en la @steenslag comentario de

    • Agradable y razonable.
    • …cuando a y b pueden ser ordenados.
  5. 9

    Ruby 2.6+

    Ruby introducido diferencia en 2.6.

    Esto le da una muy rápida, muy legible solución aquí, como sigue:

    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

    Ejecución de los puntos de referencia:

    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

    Espero que ayude a alguien!

    • la diferencia está rompiendo en este caso a = [1, 2, 3] b = [1, 2, 3, 4, 5] una.diferencia(b).cualquier? => false
  6. 7

    Si usted espera [:a, :b] != [:a, :a, :b] to_set no funciona. Usted puede usar la frecuencia en lugar:

    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
    • ¿por qué no a.sort == b.sort si a él le preocupa la frecuencia?
    • Lo que si los artículos no son comparables? ["", :b].frequency == [:b, ""].frequency #=> true
    • buen punto. En general el caso de que usted está en lo correcto
    • también se puede hacer algo funcional como a.group_by{|i| i} == b.group_by{|i| i}
  7. 6

    Si usted sabe que las matrices son de igual longitud y ni matriz contiene duplicados, entonces esto también funciona:

    ( array1 & array2 ) == array1

    Explicación: la & operador en este caso se devuelve una copia de a1 sans todos los elementos que no se encuentran en a2, que es el mismo que el original a1 iff ambas matrices tienen el mismo contenido sin que se repitan.

    Análisis: Dado que el orden es invariable, supongo que esto se implementa como un doble iteración tan consistentemente O(n*n), en particular, peor para grandes conjuntos de a1.sort == a2.sort que debe realizar con el peor de los casos O(n*logn).

    • No funciona siempre: a1 = [1,2,3], a2 = [2, 1, 3] a1 && a2 devuelve [2,1,3] para mí que no es igual a a1
    • no quieres decir que solo funciona cuando a1==a2? Es posible que funcione si array1 en el lado derecho de la igualdad es reemplazado por array2, pero dudo que el orden de los elementos devueltos por & está garantizada.
    • es un conjunto de operador de intersección de las matrices, && es lógico Y – son muy diferentes!
  8. 1

    Un enfoque consiste en iterar a través de la matriz sin duplicados

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

    Este devuelve una matriz de las verdades. Si cualquier falso aparece, a continuación, el exterior include? devolverá true. Por lo tanto usted tiene que invertir todo el asunto para determinar si se trata de un partido.

    • Este sería O(n^2)
    • Moroz, usted está en lo correcto, y un recuento de frecuencia simplemente sería O(n).
  9. 1

    la combinación de & y size puede ser demasiado rápido.

    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

Dejar respuesta

Please enter your comment!
Please enter your name here