¿Por qué este algoritmo simple de haskell es tan lento?
lerta de @Spoiler: esto está relacionado conProblema 14 del Proyecto Euler.
El siguiente código tarda unos 15 segundos 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 crece la entrada. Porn = 100,000
e asigna @ 1gb (!), Paran = 1,000,000
13gb (!!) se asigna.
Entonces de nuevo,-sstderr
muestra que, aunque se asignaron muchos bytes, el uso total de memoria fue de 1 mb y la productividad fue del 95% +, por lo que tal vez 13 gb son arenq
Puedo pensar en algunas posibilidades:
Algo no es tan estricto como debe ser. Ya he descubiertofoldl1'
, pero ¿tal vez necesito hacer más? ¿Es posible marcarcollatz
como estricto (¿eso tiene sentido?
collatz
no está optimizando las llamadas de cola. Creo que debería ser, pero no sé cómo confirmarlo.
El compilador no está haciendo algunas optimizaciones, creo que debería, por ejemplo, solo dos resultados decollatz
necesita estar en la memoria en cualquier momento (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 rápida de Java 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 perfil:
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 del Proyecto 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 );
}
}