Array Merge (Unión)

Question

Tengo dos matrices que necesito fusionar, y usar el operador Union (|) es DOLOROSAMENTE lento ... ¿hay otras formas de lograr una combinación de matrices?

Además, las matrices están llenas de objetos, no de cadenas.

Un ejemplo de los objetos dentro de la matriz

#<Article 
id: 1, 
xml_document_id: 1, 
source: "<article><domain>events.waikato.ac</domain><excerpt...", 
created_at: "2010-02-11 01:32:46", 
updated_at: "2010-02-11 01:41:28" 
> 

donde origen es una pieza corta de XML.

EDITAR

Lo sentimos! Con "fusión" quiero decir que no debo insertar duplicados.

A => [1, 2, 3, 4, 5] 
B => [3, 4, 5, 6, 7] 
A.magic_merge(B) #=> [1, 2, 3, 4, 5, 6, 7] 

Entendiendo que los números enteros son en realidad objetos artículo, y el operador de la Unión parece tomar siempre

Answer 1

Aquí hay un script que compara dos técnicas de fusión: utilizando el operador de tubería (a1 | a2) y usando concatenate-and-uniq ((a1 + a2).uniq). Dos puntos de referencia adicionales dan el tiempo de concatenar y uniq individualmente.

require 'benchmark' 

a1 = []; a2 = [] 
[a1, a2].each do |a| 
    1000000.times { a << rand(999999) } 
end 

puts "Merge with pipe:" 
puts Benchmark.measure { a1 | a2 } 

puts "Merge with concat and uniq:" 
puts Benchmark.measure { (a1 + a2).uniq } 

puts "Concat only:" 
puts Benchmark.measure { a1 + a2 } 

puts "Uniq only:" 
b = a1 + a2 
puts Benchmark.measure { b.uniq } 

En mi máquina (Ubuntu Karmic, Ruby 1.8.7), me sale una salida como ésta:

Merge with pipe: 
    1.000000 0.030000 1.030000 ( 1.020562) 
Merge with concat and uniq: 
    1.070000 0.000000 1.070000 ( 1.071448) 
Concat only: 
    0.010000 0.000000 0.010000 ( 0.005888) 
Uniq only: 
    0.980000 0.000000 0.980000 ( 0.981700) 

lo que demuestra que estas dos técnicas son muy similares en velocidad, y que es el uniq componente más grande de la operación. Esto tiene sentido de forma intuitiva, siendo O (n) (en el mejor de los casos), mientras que la concatenación simple es O (1).

Por lo tanto, si realmente desea acelerar esto, debe observar cómo se implementa el operador <=> para los objetos en sus matrices. Creo que la mayor parte del tiempo se gasta comparando objetos para asegurar la desigualdad entre cualquier par en la matriz final.

Answer 2

Utilizando el método Array#concat probablemente será mucho más rápido, de acuerdo con mis puntos de referencia iniciales usando Rubí 1.8. 7:

require 'benchmark' 

def reset_arrays! 
    @array1 = [] 
    @array2 = [] 

    [@array1, @array2].each do |array| 
    10000.times { array << ActiveSupport::SecureRandom.hex } 
    end 
end 

reset_arrays! && puts(Benchmark.measure { @array1 | @array2 }) 
# => 0.030000 0.000000 0.030000 ( 0.026677) 

reset_arrays! && puts(Benchmark.measure { @array1.concat(@array2) }) 
# => 0.000000 0.000000 0.000000 ( 0.000122) 

Answer 3

probar esto y ver si esto es más rápido

a = [1,2,3,3,2] 
b = [1,2,3,4,3,2,5,7] 
(a+b).uniq 

Answer 4

¿Necesita que los artículos estén en un orden específico dentro de las matrices? De lo contrario, es posible que desee comprobar si el uso de Set s lo hace más rápido.

actualización

Adición al código del otro responde:

require "set" 
require "benchmark" 

a1 = []; a2 = [] 
[a1, a2].each do |a| 
    1000000.times { a << rand(999999) } 
end 

s1, s2 = Set.new, Set.new 

[s1, s2].each do |s| 
    1000000.times { s << rand(999999) } 
end 

puts "Merge with pipe:" 
puts Benchmark.measure { a1 | a2 } 

puts "Merge with concat and uniq:" 
puts Benchmark.measure { (a1 + a2).uniq } 

puts "Concat only:" 
puts Benchmark.measure { a1 + a2 } 

puts "Uniq only:" 
b = a1 + a2 
puts Benchmark.measure { b.uniq } 

puts "Using sets" 
puts Benchmark.measure {s1 + s2} 

puts "Starting with arrays, but using sets" 
puts Benchmark.measure {s3, s4 = [a1, a2].map{|a| Set.new(a)} ; (s3 + s4)} 

da (por Ruby 1.8.7 (2008-08-11 Patchlevel 72) [Universal-darwin10.0])

Merge with pipe: 
    1.320000 0.040000 1.360000 ( 1.349563) 
Merge with concat and uniq: 
    1.480000 0.030000 1.510000 ( 1.512295) 
Concat only: 
    0.010000 0.000000 0.010000 ( 0.019812) 
Uniq only: 
    1.460000 0.020000 1.480000 ( 1.486857) 
Using sets 
    0.310000 0.010000 0.320000 ( 0.321982) 
Starting with arrays, but using sets 
    2.340000 0.050000 2.390000 ( 2.384066) 

Sugiere que los conjuntos pueden ser o no más rápidos, dependiendo de sus circunstancias (muchas fusiones o no muchas fusiones).