2011-01-30 15 views
12

Conversión no negativo Integer a su lista de dígitos se hace comúnmente como esto:Por qué `(map digitToInt). show` es tan rápido?

import Data.Char 

digits :: Integer -> [Int] 
digits = (map digitToInt) . show 

yo estaba tratando de encontrar una forma más directa para realizar la tarea, sin que ello suponga una conversión de cadenas, pero no soy capaz para llegar a algo más rápido.

cosas que he estado tratando hasta ahora:

La línea de base:

digits :: Int -> [Int] 
digits = (map digitToInt) . show 

Tienes ésta de otra pregunta en StackOverflow:

digits2 :: Int -> [Int] 
digits2 = map (`mod` 10) . reverse . takeWhile (> 0) . iterate (`div` 10) 

Tratando de rodar mi propia:

digits3 :: Int -> [Int] 
digits3 = reverse . revDigits3 

revDigits3 :: Int -> [Int] 
revDigits3 n = case divMod n 10 of 
       (0, digit) -> [digit] 
       (rest, digit) -> digit:(revDigits3 rest) 

Éste fue inspirado por showInt en Numeric:

digits4 n0 = go n0 [] where 
    go n cs 
     | n < 10 = n:cs 
     | otherwise = go q (r:cs) 
     where 
     (q,r) = n `quotRem` 10 

Ahora el punto de referencia. Nota: Estoy forzando la evaluación usando filter.

λ>:set +s 
λ>length $ filter (>5) $ concat $ map (digits) [1..1000000] 
2400000 
(1.58 secs, 771212628 bytes) 

Esta es la referencia. Ahora, para digits2:

λ>length $ filter (>5) $ concat $ map (digits2) [1..1000000] 
2400000 
(5.47 secs, 1256170448 bytes) 

Eso es 3,46 tiempos más largos.

λ>length $ filter (>5) $ concat $ map (digits3) [1..1000000] 
2400000 
(7.74 secs, 1365486528 bytes) 

digits3 es 4,89 vez más lento. Solo por diversión, intenté usar solo revDigits3 y evitar el reverse.

λ>length $ filter (>5) $ concat $ map (revDigits3) [1..1000000] 
2400000 
(8.28 secs, 1277538760 bytes) 

Curiosamente, esto es aún más lenta, 5.24 veces más lento.

Y la última:

λ>length $ filter (>5) $ concat $ map (digits4) [1..1000000] 
2400000 
(16.48 secs, 1779445968 bytes) 

Ésta es 10,43 vez más lento.

Tenía la impresión de que solo el uso de la aritmética y los contras superaría a cualquier cosa que implique una conversión de cadenas. Aparentemente, hay algo que no puedo comprender.

¿Cuál es el truco? ¿Por qué es digits tan rápido?

Estoy usando GHC 6.12.3.

+9

Compilar el código anterior en lugar de ejecutarlo en GHCi da resultados muy diferentes. 'digits4' es 1.8 veces más rápido que' digits' cuando se compila w/-O3. – gawi

+0

Probablemente, el compilador optimice 'showInt', mientras que ghci no hará ninguna optimización. – fuz

+0

compila el código con al menos -O2 (como dijo gawi), luego usa el criterio de referencia, y por amor a todo lo que es bueno, no uses 'mod', usa' rem' !!! –

Respuesta

30

Como no puedo agregar comentarios todavía, haré un poco más de trabajo y analizaré todos. Estoy poniendo el análisis en la parte superior; sin embargo, los datos relevantes están debajo. (Nota: todo esto se hace en 6.12.3 también - no hay magia de GHC 7 todavía.)


Análisis:

Versión 1: espectáculo es bastante bueno para enteros, especialmente aquellos tan corto como lo hemos hecho. Hacer cadenas en realidad tiende a ser decente en GHC; sin embargo, leer cadenas y escribir cadenas grandes en los archivos (o stdout, aunque no le gustaría hacer eso) es donde su código puede rastrearse completamente. Sospecho que muchos de los detalles detrás de por qué esto es tan rápido se deben a optimizaciones inteligentes dentro del show para Ints.

Versión 2: Esta fue la más lenta del grupo cuando se compiló. Algunos problemas: el reverso es estricto en su argumento. Lo que esto significa es que no se beneficia de poder realizar cálculos en la primera parte de la lista mientras está calculando los siguientes elementos; tienes que calcularlos todos, voltearlos y luego hacer tus cálculos (a saber, (`mod` 10)) en los elementos de la lista. Si bien esto puede parecer pequeño, puede conducir a un mayor uso de la memoria (tenga en cuenta los 5 GB de memoria de montón asignados aquí también) y cálculos más lentos. (Para resumir, no use el reverso.)

Versión 3: ¿Recuerda que acabo de decir que no use el reverso? Resulta que, si lo sacas, este cae a 1.79s de tiempo total de ejecución, apenas más lento que la línea de base. El único problema aquí es que a medida que profundizas en el número, estás construyendo el lomo de la lista en la dirección incorrecta (esencialmente, estás consintiendo "en" la lista con recursión, en lugar de consingrar "en" la lista).

Versión 4: Esta es una implementación muy inteligente. Se beneficia de varias cosas buenas: por un lado, Quote debería usar el algoritmo euclidiano, que es logarítmico en su argumento más amplio. (Tal vez es más rápido, pero no creo que haya nada que sea más que un factor constante más rápido que Euclid.) Además, usted está en la lista como se discutió la última vez, por lo que no tiene que resolver ningún rollo de lista como usted ir - la lista ya está completamente construida cuando vuelves a analizarla. Como puede ver, el rendimiento se beneficia de esto.

Este código fue probablemente el más lento en GHCi porque muchas de las optimizaciones realizadas con la bandera -O3 en GHC se ocupan de hacer listas más rápido, mientras que GHCi no haría nada de eso.

Lecciones: contras de la manera correcta en una lista, esté pendiente de rigurosidad intermedia que puede ralentizar los cálculos, y hacer algo de trabajo de campo en el estudio de las estadísticas de grano fino de rendimiento de su código. También compila con las banderas -O3: cuando no lo haces, todas aquellas personas que dedican muchas horas a hacer GHC súper rápido obtienen grandes ojos de cachorro para ti.


datos:

acabo de tomar todas las cuatro funciones, las puse en una .hs archivo, y luego cambiado si es necesario para reflejar la función en uso. Además, superé tu límite hasta 5e6, porque en algunos casos el código compilado se ejecutaría en menos de medio segundo en 1e6, y esto puede comenzar a causar problemas de granularidad con las medidas que estamos realizando.

Opciones del compilador: use ghc --make -O3 [nombre del archivo] .hs para que GHC haga algo de optimización. Volcaremos las estadísticas al error estándar usando dígitos + RTS -sstderr.

Dumping a -sstderr nos da salida que se parece a esto, en el caso de digits1:

digits1 +RTS -sstderr 
12000000 
    2,885,827,628 bytes allocated in the heap 
     446,080 bytes copied during GC 
      3,224 bytes maximum residency (1 sample(s)) 
      12,100 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 5504 collections,  0 parallel, 0.06s, 0.03s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 1.61s ( 1.66s elapsed) 
    GC time 0.06s ( 0.03s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 1.67s ( 1.69s elapsed) 

    %GC time  3.7% (1.5% elapsed) 

    Alloc rate 1,795,998,050 bytes per MUT second 

    Productivity 96.3% of total user, 95.2% of total elapsed 

Hay estadísticas de claves aquí:

  1. total de la memoria en uso: sólo 1 MB medios esta versión es muy eficiente en el uso del espacio.
  2. Tiempo total: 1.61s significa nada ahora, pero veremos cómo se ve en comparación con las otras implementaciones.
  3. Productividad: Esto es solo un 100% menos recolección de basura; ya que estamos en el 96,3%, esto significa que no estamos creando una gran cantidad de objetos que dejan tirados en la memoria ..

Muy bien, vamos a pasar a la versión 2.

digits2 +RTS -sstderr 
12000000 
    5,512,869,824 bytes allocated in the heap 
     1,312,416 bytes copied during GC 
      3,336 bytes maximum residency (1 sample(s)) 
      13,048 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 10515 collections,  0 parallel, 0.06s, 0.04s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 3.20s ( 3.25s elapsed) 
    GC time 0.06s ( 0.04s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 3.26s ( 3.29s elapsed) 

    %GC time  1.9% (1.2% elapsed) 

    Alloc rate 1,723,838,984 bytes per MUT second 

    Productivity 98.1% of total user, 97.1% of total elapsed 

Bien, entonces estamos viendo un patrón interesante.

  1. La misma cantidad de memoria utilizada. Esto significa que esta es una implementación bastante buena, aunque podría significar que tenemos que probar en entradas de muestra más altas para ver si podemos encontrar una diferencia.
  2. Tarda el doble de tiempo. Volveremos a algunas especulaciones sobre por qué esto es más tarde.
  3. En realidad es un poco más productivo, pero dado que GC no es una gran parte de ninguno de los programas, esto no nos ayuda en nada importante.

Versión 3:

digits3 +RTS -sstderr 
12000000 
    3,231,154,752 bytes allocated in the heap 
     832,724 bytes copied during GC 
      3,292 bytes maximum residency (1 sample(s)) 
      12,100 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 6163 collections,  0 parallel, 0.02s, 0.02s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 2.09s ( 2.08s elapsed) 
    GC time 0.02s ( 0.02s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 2.11s ( 2.10s elapsed) 

    %GC time  0.7% (1.0% elapsed) 

    Alloc rate 1,545,701,615 bytes per MUT second 

    Productivity 99.3% of total user, 99.3% of total elapsed 

bien, así que estamos viendo algunos patrones extraños.

  1. Todavía estamos en 1 MB de memoria total en uso. Así que no hemos golpeado nada de memoria ineficiente, lo cual es bueno.
  2. No estamos exactamente en digits1, pero tenemos digits2 beat con bastante facilidad.
  3. Muy poco GC. (Tenga en cuenta que cualquier cosa por encima del 95% la productividad es muy buena, así que no estamos realmente se trata de algo demasiado importante en este caso.)

Y, por último, la versión 4:

digits4 +RTS -sstderr 
12000000 
    1,347,856,636 bytes allocated in the heap 
     270,692 bytes copied during GC 
      3,180 bytes maximum residency (1 sample(s)) 
      12,100 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 2570 collections,  0 parallel, 0.00s, 0.01s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 1.09s ( 1.08s elapsed) 
    GC time 0.00s ( 0.01s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 1.09s ( 1.09s elapsed) 

    %GC time  0.0% (0.8% elapsed) 

    Alloc rate 1,234,293,036 bytes per MUT second 

    Productivity 100.0% of total user, 100.5% of total elapsed 

Wowza! Vamos a descomponerlo:

  1. Todavía estamos en 1 MB en total. Esto es casi seguro una característica de estas implementaciones, ya que permanecen en 1 MB en las entradas de 5e5 y 5e7. Un testimonio de la pereza, si se quiere.
  2. Cortamos aproximadamente el 32% de nuestro tiempo original, lo cual es bastante impresionante.
  3. Sospecho que los porcentajes aquí reflejan la granularidad en el monitoreo de -sstderr en lugar de cualquier cálculo sobre partículas superlumínicas.
+2

¡Qué buena respuesta! +1 – fuz

+0

Las métricas de "bytes asignados en la cabecera" parecen ser relevantes. A medida que se asigna más memoria, más lento se ejecuta el programa. – gawi

+2

gawi: eso afectará el rendimiento, sí, pero OP también debería preocuparse por la memoria total en uso. Si eso es demasiado grande, eso es una señal de que el programa no es lo suficientemente estricto o no es lo suficientemente lento. Y si esa memoria total supera el límite de pila de GHC, OP está en un mundo de dolor ... – dvitek

12

Respondiendo a la pregunta "¿por qué rem en lugar de mod?" en los comentariosCuando se trata de valores positivos rem x y === mod x y por lo que la única consideración de la nota es el rendimiento:

> import Test.QuickCheck 
> quickCheck (\x y -> x > 0 && y > 0 ==> x `rem` y == x `mod` y) 

Entonces, ¿cuál es el rendimiento? A menos que tenga una buena razón para no hacerlo (y ser perezoso no es una buena razón, ni es no saber Criterio) a continuación, utilizar una buena herramienta de referencia, que se utiliza Criterio:

$ cat useRem.hs 
import Criterion 
import Criterion.Main 

list :: [Integer] 
list = [1..10000] 

main = defaultMain 
     [ bench "mod" (nf (map (`mod` 7)) list) 
     , bench "rem" (nf (map (`rem` 7)) list) 
     ] 

La ejecución de esta muestra es notablemente mejor rem que mod (compilado con -O2):

$ ./useRem 
... 
benchmarking mod 
... 
mean: 590.4692 us, lb 589.2473 us, ub 592.1766 us, ci 0.950 

benchmarking rem 
... 
mean: 394.1580 us, lb 393.2415 us, ub 395.4184 us, ci 0.950 
+0

Gracias, eso es informativo e inesperado – amccausl