¿Por qué este simple algoritmo haskell es tan lento?
collatz (3)
Alerta de spoiler: esto está relacionado con el Problema 14 del Proyecto Euler.
El siguiente código tarda alrededor de 15s en ejecutarse. Tengo una solución Java no recursiva que se ejecuta en 1s. Creo que debería poder acercar este código mucho más a eso.
import Data.List
collatz a 1 = a
collatz a x
| even x = collatz (a + 1) (x `div` 2)
| otherwise = collatz (a + 1) (3 * x + 1)
main = do
print ((foldl1'' max) . map (collatz 1) $ [1..1000000])
He perfilado con +RHS -p y noté que la memoria asignada es grande, y crece a medida que la entrada crece. Para n = 100,000 se asigna 1gb (!), Para n = 1,000,000 asigna 13gb (!!).
Entonces, nuevamente, -sstderr muestra que aunque se asignaron muchos bytes, el uso total de memoria fue de 1mb, y la productividad fue del 95%, por lo que tal vez 13gb sea de la pista roja.
Puedo pensar en algunas posibilidades:
Algo no es tan estricto como debe ser. Ya he descubierto
foldl1'', pero ¿quizás necesito hacer más? ¿Es posible marcarcollatzcomo estricto (eso tiene sentido?collatzno es la optimización de llamadas de cola. Creo que debería ser, pero no sé una forma de confirmar.El compilador no está haciendo algunas optimizaciones, creo que debería hacerlo; por ejemplo, solo dos resultados de
collatzdeben estar en la memoria al mismo tiempo (máximo y actual)
¿Alguna sugerencia?
Esto es prácticamente un duplicado de ¿Por qué esta expresión de Haskell es tan lenta? , aunque señalaré que la solución Java rápida no tiene que realizar ninguna memorización. ¿Hay alguna forma de acelerar esto sin tener que recurrir a él?
Para referencia, aquí está mi salida de perfiles:
Wed Dec 28 09:33 2011 Time and Allocation Profiling Report (Final)
scratch +RTS -p -hc -RTS
total time = 5.12 secs (256 ticks @ 20 ms)
total alloc = 13,229,705,716 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
collatz Main 99.6 99.4
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 1 0 0.0 0.0 100.0 100.0
CAF Main 208 10 0.0 0.0 100.0 100.0
collatz Main 215 1 0.0 0.0 0.0 0.0
main Main 214 1 0.4 0.6 100.0 100.0
collatz Main 216 0 99.6 99.4 99.6 99.4
CAF GHC.IO.Handle.FD 145 2 0.0 0.0 0.0 0.0
CAF System.Posix.Internals 144 1 0.0 0.0 0.0 0.0
CAF GHC.Conc 128 1 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.Internals 119 1 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding.Iconv 113 5 0.0 0.0 0.0 0.0
Y -sstderr:
./scratch +RTS -sstderr
525
21,085,474,908 bytes allocated in the heap
87,799,504 bytes copied during GC
9,420 bytes maximum residency (1 sample(s))
12,824 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 40219 collections, 0 parallel, 0.40s, 0.51s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 35.38s ( 36.37s elapsed)
GC time 0.40s ( 0.51s elapsed)
RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 35.79s ( 36.88s elapsed) %GC time 1.1% (1.4% elapsed) Alloc rate 595,897,095 bytes per MUT second
Productivity 98.9% of total user, 95.9% of total elapsed
Y la solución Java (no la mía, tomada de los foros de Project Euler con la memoria eliminada):
public class Collatz {
public int getChainLength( int n )
{
long num = n;
int count = 1;
while( num > 1 )
{
num = ( num%2 == 0 ) ? num >> 1 : 3*num+1;
count++;
}
return count;
}
public static void main(String[] args) {
Collatz obj = new Collatz();
long tic = System.currentTimeMillis();
int max = 0, len = 0, index = 0;
for( int i = 3; i < 1000000; i++ )
{
len = obj.getChainLength(i);
if( len > max )
{
max = len;
index = i;
}
}
long toc = System.currentTimeMillis();
System.out.println(toc-tic);
System.out.println( "Index: " + index + ", length = " + max );
}
}
Al principio, pensé que deberías intentar poner un signo de exclamación antes de un collatz :
collatz !a 1 = a
collatz !a x
| even x = collatz (a + 1) (x `div` 2)
| otherwise = collatz (a + 1) (3 * x + 1)
(Necesitará colocar {-# LANGUAGE BangPatterns #-} en la parte superior de su archivo fuente para que esto funcione.)
Mi razonamiento fue el siguiente: el problema es que estás acumulando un thunk masivo en el primer argumento de collatz: comienza como 1 , y luego se convierte en 1 + 1 , y luego se convierte en (1 + 1) + 1 ,. .. todo sin ser forzado nunca. Este patrón de fuerza collatz a collatz el primer argumento de collatz cada vez que se realiza una llamada, por lo que comienza como 1, y luego se convierte en 2, y así sucesivamente, sin generar un gran impulso no evaluado: simplemente permanece como un entero.
Tenga en cuenta que un patrón de explosión es solo una abreviatura para usar seq ; En este caso, podríamos reescribir collatz siguiente manera:
collatz a _ | seq a False = undefined
collatz a 1 = a
collatz a x
| even x = collatz (a + 1) (x `div` 2)
| otherwise = collatz (a + 1) (3 * x + 1)
El truco aquí es forzar a un en la guardia, que luego siempre se evalúa como Falso (y por lo tanto el cuerpo es irrelevante). Luego la evaluación continúa con el siguiente caso, habiendo sido ya evaluado. Sin embargo, un patrón de explosión es más claro.
Desafortunadamente, cuando se compila con -O2 , ¡esto no se ejecuta más rápido que el original! Que mas podemos probar? Bueno, una cosa que podemos hacer es asumir que los dos números nunca desbordan un número entero del tamaño de una máquina y dar a collatz esta anotación de tipo:
collatz :: Int -> Int -> Int
Dejaremos el patrón de explosión allí, ya que todavía deberíamos evitar la creación de thunks, incluso si no son la raíz del problema de rendimiento. Esto reduce el tiempo a 8.5 segundos en mi computadora (lenta).
El siguiente paso es intentar acercar esto a la solución Java. Lo primero que hay que darse cuenta es que en Haskell, div comporta de una manera matemáticamente más correcta con respecto a los enteros negativos, pero es más lento que la división C "normal", que en Haskell se llama quot . Reemplazar div con quot bajó el tiempo de ejecución a 5.2 segundos, y reemplazando x `quot` 2 con x `shiftR` 1 (importando Data.Bits) para que coincida con la solución Java bajó a 4.9 segundos.
Esto es lo más bajo que puedo obtener por ahora, pero creo que este es un resultado bastante bueno; dado que su computadora es más rápida que la mía, es de esperar que esté aún más cerca de la solución Java.
Aquí está el código final (hice un poco de limpieza en el camino):
{-# LANGUAGE BangPatterns #-}
import Data.Bits
import Data.List
collatz :: Int -> Int
collatz = collatz'' 1
where collatz'' :: Int -> Int -> Int
collatz'' !a 1 = a
collatz'' !a x
| even x = collatz'' (a + 1) (x `shiftR` 1)
| otherwise = collatz'' (a + 1) (3 * x + 1)
main :: IO ()
main = print . foldl1'' max . map collatz $ [1..1000000]
Mirando el Core de GHC para este programa (con ghc-core ), creo que esto es probablemente lo mejor que se pueda; el bucle de collatz usa enteros sin caja y el resto del programa se ve bien. La única mejora que se me ocurre sería eliminar el boxeo de la iteración de map collatz [1..1000000] del map collatz [1..1000000] .
Por cierto, no te preocupes por la cifra de "asignación total"; es la memoria total asignada durante la vida útil del programa y nunca disminuye incluso cuando el GC recupera esa memoria. Las figuras de terabytes múltiples son comunes.
Podría perder la lista y los patrones de bang y seguir obteniendo el mismo rendimiento usando la pila en su lugar.
import Data.List
import Data.Bits
coll :: Int -> Int
coll 0 = 0
coll 1 = 1
coll 2 = 2
coll n =
let a = coll (n - 1)
collatz a 1 = a
collatz a x
| even x = collatz (a + 1) (x `shiftR` 1)
| otherwise = collatz (a + 1) (3 * x + 1)
in max a (collatz 1 n)
main = do
print $ coll 100000
Un problema con esto es que tendrá que aumentar el tamaño de la pila para entradas grandes, como 1_000_000.
actualizar:
Aquí hay una versión recursiva de cola que no sufre el problema de desbordamiento de pila.
import Data.Word
collatz :: Word -> Word -> (Word, Word)
collatz a x
| x == 1 = (a,x)
| even x = collatz (a + 1) (x `quot` 2)
| otherwise = collatz (a + 1) (3 * x + 1)
coll :: Word -> Word
coll n = collTail 0 n
where
collTail m 1 = m
collTail m n = collTail (max (fst $ collatz 1 n) m) (n-1)
Note el uso de Word lugar de Int . Hace una diferencia en el rendimiento. Si lo desea, aún podría usar los patrones de explosión, y eso casi duplicaría el rendimiento.
Una cosa que encontré hizo una sorprendente diferencia en este problema. Me quedé con la relación de recurrencia directa en lugar de doblar, debes perdonar la expresión, la cuenta con ella. Reescritura
collatz n = if even n then n `div` 2 else 3 * n + 1
como
collatz n = case n `divMod` 2 of
(n'', 0) -> n''
_ -> 3 * n + 1
Tomé 1.2 segundos del tiempo de ejecución de mi programa en un sistema con una CPU Athlon II X4 430 de 2.8 GHz. Mi versión inicial más rápida (2.3 segundos después del uso de divMod):
{-# LANGUAGE BangPatterns #-}
import Data.List
import Data.Ord
collatzChainLen :: Int -> Int
collatzChainLen n = collatzChainLen'' n 1
where collatzChainLen'' n !l
| n == 1 = l
| otherwise = collatzChainLen'' (collatz n) (l + 1)
collatz:: Int -> Int
collatz n = case n `divMod` 2 of
(n'', 0) -> n''
_ -> 3 * n + 1
pairMap :: (a -> b) -> [a] -> [(a, b)]
pairMap f xs = [(x, f x) | x <- xs]
main :: IO ()
main = print $ fst (maximumBy (comparing snd) (pairMap collatzChainLen [1..999999]))
Una versión de Haskell quizás más idiomática se ejecuta en aproximadamente 9.7 segundos (8.5 con divMod); es idéntico excepto para
collatzChainLen :: Int -> Int
collatzChainLen n = 1 + (length . takeWhile (/= 1) . (iterate collatz)) n
El uso de Data.List.Stream debe permitir una fusión de secuencias que haría que esta versión se ejecute más así con la acumulación explícita, pero no puedo encontrar un paquete libghc * de Ubuntu que tenga Data.List.Stream, así que no puedo sin embargo, verificar que.