grande manipolazione array è molto lento in Ruby

Question

Ho il seguente scenario:

Ho bisogno di capire la lista unica di ID in un grande set.

Così, ad esempio, ho 6000 matrici di ID (elenco seguaci), ognuna delle quali può avere una dimensione compresa tra 1 e 25000 (la loro lista di follower).

Desidero ottenere l'elenco univoco di ID su tutti questi array di ID (seguaci unici di follower). Una volta fatto, devo sottrarre un'altra lista (un'altra lista di follower di persone) di id e ottenere un conteggio finale.

Il set finale di ID univoci cresce a circa 60.000.000 di record. In ruby ​​quando si aggiungono gli array al grande array, inizia a diventare molto lento circa un paio di milioni. L'aggiunta al set richiede inizialmente 1 minuto e poi aumenta di oltre 4 secondi a 2 milioni (non dove vicino a dove devo andare).

Ho scritto un programma di test in Java e fa tutto in meno di un minuto.

Forse sto facendo questo inefficientemente in ruby, o c'è un altro modo. Dal momento che il mio codice principale è proprietario Ho scritto un semplice programma di test per simulare il problema:

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 

Eventuali suggerimenti, è il momento di passare a JRuby e spostare roba come questa per Java?

Answer 1

Il metodo che stai usando è orribilmente inefficiente, quindi non sorprende che sia lento. Quando stai cercando di tenere traccia di cose uniche, un array richiede molta più elaborazione di un equivalente di hash.

Ecco un semplice refactoring che aumenta la velocità di circa 100x:

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 

La cosa bella di un hash è che è impossibile avere duplicati. Se è necessario elencare tutti i follower in qualsiasi momento, utilizzare all_followers.keys per ottenere gli ID.

Gli hash occupano più memoria rispetto ai loro equivalenti di array, ma questo è il prezzo che devi pagare per le prestazioni. Sospetto anche che uno dei grandi consumatori di memoria qui sia le numerose liste individuali di follower che vengono generate e apparentemente non usate mai, quindi forse potresti saltare completamente questo passaggio.

L'elemento chiave qui è che l'operatore Array | non è molto efficiente, soprattutto quando si opera su array molto grandi.

Answer 2

Ecco un esempio per gestire gli oggetti unici con array, hash e impostare:

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 

e il loro punto di riferimento:

   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:

ruby處理unique物件