Agregar cadenas cortas a un conjunto en Ruby es lento

Question

Estoy tratando de extraer todos los caracteres únicos de mi archivo de diccionario francés utf-8 usando este código de Ruby. El diccionario es 3.7 MB. Por alguna razón, mi computadora decente tarda aproximadamente media hora en ejecutarse. ¿Algunas ideas?

c = Set.new 
f = open "dict" 
s = f.read 
f.close 

for i in 0..s.length-1 
    c << s[i] 
end 

Answer 1

La lectura en el archivo completo de una sola vez antes de realizar cualquier cálculo sobre el mismo impide IO de ser intercalada con el cálculo. Además, aumenta la presión de la memoria (potencialmente importante si se está ejecutando cerca del límite de la memoria) y reduce drásticamente cache coherency.

me escribió el siguiente pequeño script que se ejecuta en segundo .3 en mi archivo /usr/share/dict/words - menos de un megabyte, pero aún lo suficientemente grande como para ser un poco interesante:

$ cat /tmp/set.rb 
#!/usr/bin/ruby 

require 'set' 

c = Set.new 
f = open "/usr/share/dict/words" 

f.each_char do |char| 
    c << char 
end 

p c 
$ time /tmp/set.rb 
#<Set: {"A", "\n", "'", "s", "B", "M", "C", "T", "H", "I", "D", "S", "O", "L", "P", "W", "Z", "a", "c", "h", "e", "n", "l", "i", "y", "r", "o", "b", "d", "t", "u", "j", "g", "m", "p", "v", "x", "f", "k", "z", "w", "q", "ó", "ü", "á", "ö", "ñ", "E", "F", "R", "U", "N", "G", "K", "é", "ä", "Q", "è", "V", "J", "X", "ç", "ô", "í", "Y", "â", "û", "ê", "å", "Å"}> 

real 0m0.341s 
user 0m0.340s 
sys 0m0.000s 

Su programa era todavía ejecutar una minutos a más tarde, y me di por vencido.

La principal diferencia es que el mío usa los iteradores incorporados para leer en un búfer una cantidad menor del archivo (probablemente 4k-16k) y me da un carácter específico en cada iteración. Esto reutilizará las mismas pequeñas cantidades de memoria una y otra vez y permitirá que las líneas de caché relativamente pequeñas de la CPU almacenen la totalidad de los datos.

Editar

Con un caso de prueba pequeña que era capaz de aislar la diferencia de velocidad sobre todo a la each_char vs cadena de sub-secuencias de comandos. Jörg points out that string subscripting is an O(N) operation - porque las cadenas UTF-8 no se pueden indexar simplemente por multiplicación como cabría esperar, encontrar el carácter Nth significa comenzar desde el principio. Por lo tanto, su enfoque es O (N^2) y el mío fue solo O (N) y que va mucho más allá al explicar la diferencia de rendimiento. Finalmente estoy contento de que descubrimos la causa central.