wielka manipulacja tablica jest bardzo powolny w Ruby

Question

Mam następujący scenariusz:

I potrzeba, aby dowiedzieć się unikalną listę identyfikatorów całej bardzo dużego zestawu.

Na przykład mam 6000 tablic identyfikatorów (lista obserwatorów), każda może mieć rozmiar od 1 do 25000 (lista ich obserwatorów).

Chcę uzyskać unikalną listę identyfikatorów we wszystkich tych tablicach identyfikatorów (unikalnych obserwatorów). Kiedy już to zrobię, muszę odjąć kolejną listę (kolejną listę osób obserwujących) identyfikatorów i uzyskać końcową liczbę.

Ostateczny zestaw unikalnych identyfikatorów rośnie do około 60 000 000 rekordów. W rubinach dodając tablice do dużej tablicy, zaczyna się bardzo powoli około kilku milionów. Dodanie do zestawu trwa początkowo 1 sekundę, a następnie rośnie do 4 sekund na poziomie 2 milionów (brak miejsca w pobliżu miejsca, w którym muszę się udać).

Napisałem program testowy w języku Java i robi to wszystko w mniej niż minutę.

Może robię to nieefektywnie w rubinie lub jest inny sposób. Ponieważ mój główny kod jest zastrzeżona ja napisałem prosty program testowy do symulacji problem:

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 

Wszelkie sugestie, nadszedł czas, aby przełączyć się jruby i przenieść rzeczy jak to Java?

Answer 1

Metoda, której używasz jest okropnie nieefektywna, więc nie jest zaskoczeniem, że jest powolna. Kiedy próbujesz śledzić unikalne rzeczy, tablica wymaga znacznie więcej przetwarzania niż odpowiednik skrótu.

Oto prosty refaktoring który zwiększa prędkość o 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 

Zaletą o Hash jest to, że można mieć duplikaty. Jeśli chcesz wyświetlić listę wszystkich obserwujących w dowolnym momencie, użyj numeru all_followers.keys, aby uzyskać identyfikatory.

Hashe zajmują więcej pamięci niż ich odpowiedniki w tablicy, ale jest to cena, którą trzeba zapłacić za wydajność. Podejrzewam też, że jednym z wielkich konsumentów pamięci jest wiele indywidualnych list obserwujących, które są generowane i pozornie nigdy nie używane, więc być może mógłbyś całkowicie pominąć ten krok.

Kluczową sprawą jest to, że operator Array | nie jest bardzo wydajny, szczególnie podczas pracy na bardzo dużych tablicach.

Answer 2

Oto przykład do obsługi unikalnych obiektów z tablicy, hash i ustawić:

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 

i ich odniesienia:

   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物件