红宝石中的大数组操作非常慢

Question

我有以下场景:

我需要在一个非常大的集合中找出唯一的id列表.

例如,我有6000个ID数组(关注者列表),每个数据的大小范围在1到25000之间(他们的关注者列表).

我希望在所有这些ID数组中找到唯一的id列表(追随者的独特关注者).一旦完成,我需要减去另外一个列表(另一个人跟随者列表)的ID并获得最终计数.

最后一组独特的ID增长到大约60,000,000条记录.在ruby中将数组添加到大数组时,它开始变得非常慢,只有几百万.添加到设置首先需要0.1秒,然后增加到超过4秒,达到200万(没有我需要去的地方).

我在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

你在那里使用的方法是非常低效的,所以毫不奇怪,这很慢.当您尝试跟踪唯一事物时,数组需要的处理方式多于Hash等效项.

这是一个简单的重构,可以将速度提高大约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

关于Hash的好处是它不可能有重复.如果您需要随时列出所有关注者,请使用all_followers.keys获取ID.

哈希占用的内存比其等效的阵列多,但这是您必须为性能付出的代价.我还怀疑这里的一个大内存消费者是生成并且似乎从未使用过的许多关注者列表,所以也许你可以完全跳过这一步.

这里的关键是Array |运算符效率不高,尤其是在非常大的数组上运行时.