¿Por qué `(mapa digitToInt). show` es tan rápido?
https://stackoverflow.com/questions/4841078
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
La conversión de Integer no negativo a su lista de dígitos se hace comúnmente como esto:
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 soy incapaz de 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
Got é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 se inspiró en 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 veces más.
λ>length $ filter (>5) $ concat $ map (digits3) [1..1000000]
2400000
(7.74 secs, 1365486528 bytes)
digits3 es 4,89 el tiempo más lento. Sólo por diversión, he intentado usar solamente revDigits3 y evitar la 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)
Este es 10,43 el tiempo más lento.
Yo tenía la impresión de que sólo el uso de la aritmética y los contras que superar cualquier cosa que implica una conversión de cadenas. Al parecer, hay algo que no puede captar.
Entonces, ¿el truco? ¿Por qué es tan rápido digits?
Estoy usando GHC 6.12.3.
Solución
En vista de que no puedo añadir comentarios todavía, voy a hacer un poco más de trabajo y simplemente analizar todos ellos. Estoy poniendo el análisis en la parte superior; sin embargo, los datos pertinentes se encuentra por debajo. (Nota:. Todo esto se hace en 6.12.3, así - no hay magia GHC 7 aún)
Análisis:
Versión 1: espectáculo es bastante bueno para enteros, especialmente aquellos tan corto como lo hemos hecho. Haciendo cuerdas realidad tiende a ser decente en GHC; Sin embargo la lectura de cuerdas y escribir grandes cadenas de archivos (o la salida estándar, a pesar de que no le gustaría hacer eso) son en su código puede absolutamente rastreo. Sospecho que muchos de los detalles detrás de por qué esto es tan rápido se deben a optimizaciones inteligentes dentro de la demostración de Ints.
Versión 2: este era el más lento del grupo cuando se compila. Algunos problemas: inverso es estricta en su argumento. Lo que significa esto es que no se benefician de la posibilidad de realizar cálculos en la primera parte de la lista mientras se está calculando los siguientes elementos; usted tiene que calcular todos ellos, darles la vuelta, y luego hacer sus cálculos (es decir, ( `mod` 10)) en los elementos de la lista. Si bien esto puede parecer pequeño, puede conducir a un mayor uso de la memoria (nótese el 5 GB de memoria de almacenamiento dinámico asigna aquí también) y los cálculos más lentas. (Larga historia corta:. No utilice inversa)
Versión 3: ¿Recuerdas que acabo de decir no uso inversa? Resulta que, si se lo saca, éste cae a 1.79s tiempo total de ejecución - apenas más lento que la línea de base. El único problema aquí es que a medida que avanza más en el número, es como construir la columna vertebral de la lista en la dirección equivocada (en esencia, que está CONSING "en" la lista con la recursividad, en contraposición a CONSING "a" la lista).
Versión 4: Esta es una aplicación muy inteligente. Se beneficia de varias cosas agradables: por un lado, quotRem debe usar el algoritmo de Euclides, que es logarítmica en su argumento más amplio. (Tal vez sea más rápido, pero no creo que haya algo que es más que un factor constante más rápido que Euclides.) Además, los contras en la lista como se discutió por última vez, de modo que usted no tiene que resolver los procesadores de la lista a medida que ir - la lista ya está enteramente construida cuando vuelvas alrededor para analizarlo. Como se puede ver, los beneficios de este rendimiento.
Este código fue probablemente el más lento en GHCi porque muchas de las optimizaciones realizadas con la bandera -O3 de acuerdo con GHC hacer listas más rápido, mientras que GHCi no haría nada de eso.
Lecciones: los contras de la manera correcta en una lista, reloj 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 compilar con las banderas -O3:. Cada vez que no lo hace, todas aquellas personas que ponen un montón de horas en hacer llegar GHC súper rápido de grandes ojos de cachorro ol' en usted
Datos:
Me tomó las cuatro funciones, las puse en un archivo .hs, y luego cambiado si es necesario para reflejar la función en uso. Además, me encontré con su límite de hasta 5E6, ya que en algunos casos el código compilado se ejecuta en menos de medio segundo en 1E6, y esto puede comenzar a problemas de granularidad causa con las mediciones que estamos haciendo.
Opciones del compilador: el uso GHC --make -O3 [nombre de archivo] .hs para tener GHC hacer alguna optimización. Vamos volcado a las estadísticas de error estándar utilizando dígitos + RTS -sstderr .
Nos Dumping a -sstderr 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 tres principales estadísticas aquí:
- La memoria total en uso:. 1 MB solamente significa que esta versión es muy eficiente con el espacio
- Tiempo total:. 1.61s medios nada ahora, pero vamos a ver cómo se ve en contra de las otras implementaciones
- Productividad: Esto es sólo el 100% de recolección de basura menos; ya que estamos en el 96,3% This 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
Muy bien, así que estamos viendo un patrón interesante.
- La misma cantidad de memoria utilizada. Esto significa que este es una implementación bastante bueno, aunque podría significar que necesitamos a prueba en las entradas de muestreo más altas para ver si podemos encontrar una diferencia.
- Se tarda el doble de tiempo. Volveremos a cierta especulación en cuanto a por qué esto es más tarde.
- Es en realidad un poco más productivo, pero dado que GC no es una enorme porción de cualquiera de los programas, esto no nos ayuda nada significativo.
Version 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
Muy bien, así que estamos viendo algunos patrones extraños.
- Todavía estamos en la memoria total de 1 MB en uso. Así que no hemos golpeado la memoria ineficientes nada, lo cual es bueno.
- No estamos muy al digits1, pero tenemos ritmo digits2 con bastante facilidad.
- 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! La ruptura de lo bajó:
- Todavía estamos a 1 MB total. Esto es casi seguro que 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.
- Cortamos alrededor del 32% de nuestro tiempo original, que es bastante impresionante.
- Sospecho que los porcentajes aquí representan la granularidad en -sstderr Ha monitoreo en lugar de cualquier cálculo sobre las partículas superlumínicas.
Otros consejos
Respondiendo a la pregunta "¿por qué real, en vez de mod?" en los comentarios. Cuando 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 herramienta buen punto de referencia, he utilizado 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 este rem espectáculos es mensurable mejor 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
