大數組操作是紅寶石

Question

我有以下情形很慢：

我需要在一個很大的集找出ID的唯一列表。因此，例如，我有6000個ID（陣列追隨者）陣列，每個隊列的大小範圍在1到25000之間（他們的追隨者列表）。

我想要獲得所有這些id數組（唯一追隨者的追隨者）的id的唯一列表。一旦完成，我需要從ID中減去另一個列表（另一個人追隨者列表）並獲得最終計數。

唯一ID的最終集合增長到約60,000,000條記錄。在將數組添加到大數組中時，在ruby中，它開始變得非常慢，數百萬。添加到集合中最初需要0.1秒，然後增長到200萬以上的4秒（不在我需要去的地方）。

我用java寫了一個測試程序，它在不到一分鐘的時間內完成了所有的事情。

也許我是在ruby中無效地做到這一點，或者有另一種方式。由於我的主要代碼是專有的我已經寫了一個簡單的測試程序來模擬問題：

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

你在那裏使用的方法效率非常低，所以這並不奇怪，這很慢。當你試圖跟蹤獨特的事物時，Array需要比哈希等價物更多的處理。

這裏有一個簡單的重構，增加約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獲取ID。

哈希佔用的內存比它們的Array等同物多，但這是您必須爲性能付出的代價。我也懷疑這裏的一個大內存消費者是許多單獨的追隨者列表，它們是生成的，似乎從未使用過，所以也許你可以完全跳過這一步。

這裏關鍵的是Array |操作符效率不高，特別是在非常大的數組上操作時。

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) 

參考文獻：

ruby處理unique物件