gran manipulación de matrices es muy lento en rubí

Question

tengo el siguiente escenario:

tengo que averiguar la lista de identificadores únicos a través de un conjunto muy grande.

Así que, por ejemplo, tengo 6000 matrices de identificadores (lista de seguidores), cada una puede tener un rango de tamaño entre 1 y 25000 (su lista de seguidores).

Quiero obtener la lista única de identificadores en todas estas matrices de identificadores (seguidores únicos de seguidores). Una vez hecho esto, necesito restar otra lista (la lista de seguidores de otra persona) de los identificadores y obtener un recuento final.

El conjunto final de identificadores únicos crece a alrededor de 60,000,000 de registros. En ruby ​​cuando se agregan las matrices a la gran matriz, comienza a ser muy lento alrededor de un par de millones. Agregar al conjunto lleva .1 segundos al principio, luego crece a más de 4 segundos a 2 millones (no muy cerca de donde tengo que ir).

Escribí un programa de prueba en Java y lo hace todo en menos de un minuto.

Tal vez estoy haciendo esto ineficientemente en ruby, o hay otra manera. Desde mi código principal es propietaria he escrito un programa simple prueba para simular el tema:

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 

Cualquier sugerencia, es hora de cambiar a jruby y mover cosas como esta para java?

Answer 1

El método que está utilizando allí es terriblemente ineficiente, por lo que no sorprende que sea lento. Cuando intenta hacer un seguimiento de las cosas únicas, una matriz requiere mucho más procesamiento que un equivalente hash.

Aquí hay una refactorización simple que aumenta la velocidad de aproximadamente 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 

Lo bueno de un hash es que es imposible tener duplicados. Si necesita enumerar todos los seguidores en cualquier momento, use all_followers.keys para obtener los ID.

Los hashes ocupan más memoria que sus equivalentes de matriz, pero este es el precio que tiene que pagar por el rendimiento. También sospecho que uno de los grandes consumidores de memoria aquí es la gran cantidad de listas individuales de seguidores que se generan y aparentemente nunca se usan, por lo que quizás se salte ese paso por completo.

La clave aquí es que el operador Array | no es muy eficiente, especialmente cuando se opera en arreglos muy grandes.

Answer 2

Aquí se muestra un ejemplo para manejar objetos únicos con matriz, hash y configurar:

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 

y su referencia:

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