манипулирование большим массивом очень медленно в ruby

Question

У меня есть следующий сценарий:

Мне нужно выяснить уникальный список идентификаторов для очень большого набора.

Так, например, у меня есть 6000 массивов идентификаторов (список подписчиков)), каждый из них может иметь размер от 1 до 25000 (их список подписчиков).

Я хочу получить уникальный список идентификаторов для всех этих массивов идентификаторов (уникальных подписчиков подписчиков).Как только это будет сделано, мне нужно вычесть другой список (список других последователей) идентификаторов и получить окончательный счет.

Финальный набор уникальных идентификаторов увеличивается примерно до 60 000 000 записей.В ruby ​​при добавлении массивов в большой массив он начинает работать очень медленно - около пары миллионов.Добавление к набору занимает сначала 0,1 секунды, а затем возрастает до 4 с 2 миллионами (не там, где мне нужно).

Я написал тестовую программу на Java, и она делает всевещь менее чем за минуту.

Возможно, я делаю это неэффективно в рубине, или есть другой способ.Так как мой основной код проприетарный, я написал простую тестовую программу для имитации проблемы:

big_array = []
loop_counter = 0
start_time = Time.now
# final target size of the big array
while big_array.length < 60000000
 loop_counter+=1
 # target size of one persons follower list
 random_size_of_followers = rand(5000)
 follower_list = []
 follower_counter = 0
   while follower_counter < random_size_of_followers
     follower_counter+=1
     # make ids very large so we get good spread and only some amt of dupes
     follower_id = rand(240000000) + 100000
     follower_list << follower_id
   end
 # combine the big list with this list
 big_array = big_array | follower_list
 end_time = Time.now

 # every 100 iterations check where we are and how long each loop and combine takes.
 if loop_counter % 100 == 0
   elapsed_time = end_time - start_time
   average_time = elapsed_time.to_f/loop_counter.to_f
   puts "average time for loop is #{average_time}, total size of big_array is #{big_array.length}"
   start_time = Time.now
 end
end

Любые предложения, пора ли перейти к jruby и переместить подобные вещи в java?

Answer 1

Метод, который вы здесь используете, ужасно неэффективен, поэтому неудивительно, что он медленный.Когда вы пытаетесь отслеживать уникальные вещи, для массива требуется намного больше обработки, чем для хеш-эквивалента.

Вот простой рефакторинг, который увеличивает скорость примерно в 100 раз:

all_followers = { }
loop_counter = 0
start_time = Time.now

while (all_followers.length < 60000000)
  # target size of one persons follower list
  follower_list = []

  rand(5000).times do
    follower_id = rand(240000000) + 100000
    follower_list << follower_id
    all_followers[follower_id] = true
  end

 end_time = Time.now

 # every 100 iterations check where we are and how long each loop and combine takes.
 loop_counter += 1

  if (loop_counter % 100 == 0)
    elapsed_time = end_time - start_time
    average_time = elapsed_time.to_f/loop_counter.to_f
    puts "average time for loop is #{average_time}, total size of all_followers is #{all_followers.length}"
    start_time = Time.now
  end
end

Хорошая вещь в хэше состоит в том, что невозможно иметь дубликаты.Если вам нужно перечислить всех подписчиков в любое время, используйте all_followers.keys для получения идентификаторов.

Хэши занимают больше памяти, чем их эквиваленты массива, но это цена, которую вы должны заплатить за производительность.Я также подозреваю, что одним из крупных потребителей памяти здесь является множество отдельных списков подписчиков, которые создаются и, по-видимому, никогда не используются, поэтому, возможно, вы могли бы полностью пропустить этот шаг.

Ключевым моментом здесь является то, что массивОператор | не очень эффективен, особенно при работе с очень большими массивами.

Answer 2

Вот пример для обработки уникальных объектов с массивом, хэшем и множеством:

require 'benchmark'
require 'set'
require 'random_token'

n = 10000

Benchmark.bm(7) do |x|
  x.report("array:") do
    created_tokens = []
    while created_tokens.size < n
      token = RandomToken.gen(10)
      if created_tokens.include?(token)
        next
      else
        created_tokens << token
      end
    end
    results = created_tokens
  end

  x.report("hash:") do
    created_tokens_hash = {}
    while created_tokens_hash.size < n
      token = RandomToken.gen(10)
      created_tokens_hash[token] = true
    end
    results = created_tokens_hash.keys
  end

  x.report("set:") do
    created_tokens_set = Set.new
    while created_tokens_set.size < n
      token = RandomToken.gen(10)
      created_tokens_set << token
    end
    results = created_tokens_set.to_a
  end
end

и их тест:

              user     system      total        real
array:    8.860000   0.050000   8.910000 (  9.112402)
hash:     2.030000   0.010000   2.040000 (  2.062945)
set:      2.000000   0.000000   2.000000 (  2.037125)

Refs:

рубин 處理 уникальный 物件