Объединение массива (Union)

У меня есть два массива, которые мне нужно объединить, и использование оператора Union (|) PAINFULLY slow.. есть ли другие способы достижения слияния массива?

Кроме того, массивы заполняются объектами, а не строками.

Пример объектов в массиве

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

Где источник - короткая часть XML.

ИЗМЕНИТЬ

Извините! Под "merge" я подразумеваю, что мне не нужно вставлять дубликаты.

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

Понимание того, что целые числа являются объектами Article, и оператор Union, кажется, принимает навсегда

Ответ 1

Здесь a script, который сравнивает два метода слияния: используя оператор трубы (a1 | a2) и используя concatenate-and-uniq ((a1 + a2).uniq). Два дополнительных теста дают время конкатенации и uniq индивидуально.

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 }

На моей машине (Ubuntu Karmic, Ruby 1.8.7) я получаю вывод следующим образом:

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)

Что показывает, что эти два метода очень похожи по скорости и что uniq является более крупным компонентом операции. Это имеет смысл интуитивно, будучи O (n) (в лучшем случае), тогда как простая конкатенация O (1).

Итак, если вы действительно хотите ускорить это, вам нужно посмотреть, как реализован оператор <=> для объектов в ваших массивах. Я считаю, что большую часть времени тратится на сравнение объектов для обеспечения неравенства между любой парой в конечном массиве.

Ответ 2

Вам нужны элементы, которые должны быть в определенном порядке внутри массивов? Если нет, вы можете проверить, ускоряет ли использование Set.

Обновление

Добавление к другому коду ответа:

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

дает (для 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)

Предлагает, чтобы наборы могли или не быть быстрее, в зависимости от ваших обстоятельств (много слияний или не много слияний).

Ответ 3

Использование метода Array#concat, скорее всего, будет намного быстрее, в соответствии с моими исходными критериями с использованием 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)

Ответ 4

Попробуйте это и посмотрите, быстрее ли это

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