ruby on rails Array Merge(Union)




ruby hash (4)

Usare il metodo Array#concat della Array#concat sarà probabilmente molto più veloce, secondo i miei benchmark iniziali usando 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)

Ho due array che ho bisogno di unire, e usare l'operatore Union (|) è PAINFULLY slow .. ci sono altri modi per realizzare un array merge?

Inoltre, gli array sono pieni di oggetti, non di stringhe.

Un esempio degli oggetti all'interno dell'array

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

Dove la fonte è un breve pezzo di XML.

MODIFICARE

Scusate! Per "unione" intendo che non è necessario inserire duplicati.

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

Capire che gli interi sono in realtà oggetti dell'articolo e l'operatore dell'Unione sembra prendere per sempre


Answer #1

Prova questo e vedi se questo è più veloce

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

Answer #2

Ecco uno script che confronta due tecniche di unione: utilizzando l'operatore di pipe ( a1 | a2 ) e usando concatenate-and-uniq ( (a1 + a2).uniq ). Due benchmarks aggiuntivi danno il tempo di concatenare e 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 }

Sulla mia macchina (Ubuntu Karmic, Ruby 1.8.7), ottengo l'output in questo modo:

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)

Il che dimostra che queste due tecniche sono molto simili nella velocità e che uniq è il componente più grande dell'operazione. Ciò ha un senso intuitivo, essendo O (n) (nella migliore delle ipotesi), mentre la semplice concatenazione è O (1).

Quindi, se si vuole veramente accelerare, è necessario considerare come l'operatore <=> è implementato per gli oggetti nei propri array. Credo che la maggior parte del tempo venga spesa per confrontare gli oggetti per garantire la disuguaglianza tra qualsiasi coppia nell'array finale.


Answer #3

Avete bisogno che gli articoli siano in un ordine specifico all'interno degli array? In caso contrario, è possibile verificare se l'utilizzo di Set s lo rende più veloce.

Aggiornare

Aggiunta al codice di un altro risponditore:

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

dà (per 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)

Suggerisce che i set possono essere o meno più veloci, a seconda delle circostanze (molte fusioni o non molte fusioni).





arrays