Array Merge (Union)

Question

Mam dwie tablice muszę scalić, a przy użyciu operatora Unii (|) jest PAINFULLY powolny .. czy istnieją inne sposoby do osiągnięcia scalania tablicy?

Ponadto tablice są wypełniane obiektami, a nie ciągami.

Przykładem obiektów w tablicy

#<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" 
> 

Jeżeli źródło to fragment XML.

EDIT

Niestety! Przez "scalenie" rozumiem, że nie muszę wstawiać duplikatów.

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

Zrozumienie, że liczby całkowite są rzeczywiście Artykuł obiekty, a operator Unia wydaje się zawsze

Answer 1

Oto skrypt, w którym porównano dwie techniki łączenia: za pomocą operatora potoku (a1 | a2) i za pomocą konkatenacji-i-uniq ((a1 + a2).uniq). Dwa dodatkowe benchmarki dają czas indywidualny i niepowtarzalny.

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 } 

Na moim komputerze (Ubuntu Karmic, Ruby 1.8.7), mam wyjścia tak:

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) 

który pokazuje, że te dwie techniki są bardzo podobne pod względem szybkości i że jest uniq większy składnik operacji. Ma to sens intuicyjnie, będąc O (n) (w najlepszym wypadku), podczas gdy proste konkatenacja to O (1).

Tak więc, jeśli naprawdę chcesz przyspieszyć, musisz sprawdzić, w jaki sposób jest wdrażany operator <=> dla obiektów w twoich tablicach. Uważam, że większość czasu spędza się porównując obiekty, aby zapewnić nierówność pomiędzy dowolną parą w ostatecznej tablicy.

Answer 2

Stosując metodę Array#concat prawdopodobnie będzie dużo szybciej, według moich wstępnych wskaźników z wykorzystaniem Ruby 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

Spróbuj i zobacz, czy to szybciej

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

Answer 4

Czy chcesz, aby pozycje były w określonej kolejności w tablicach? Jeśli nie, możesz sprawdzić, czy użycie numeru Set s przyspiesza działanie.

Aktualizacja

Dodawanie do innego kodu odpowiadającego za:

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)} 

daje (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) 

Sugeruje, że zestawy mogą być lub nie mogą być szybsze, w zależności od okoliczności (wiele scaleń lub nie wiele połączeń).