Разбираюсь с хвостовой рекурсией.
Реализовал алгоритм поиска пирамидального числа:
-- recursion version
--
fermaPyr 0 = 0
fermaPyr n = fermaTria n + fermaTria (n - 1)
fermaTria 0 = 0
fermaTria n = n + fermaTria (n - 1)
-- tail recursion version
--
fermaPyrAcc n = let fAcc 0 a = a
fAcc n a = fAcc (n - 1) (fermaTriaAcc n + a)
in fAcc n 0
fermaTriaAcc n = let fAcc 0 a = a
fAcc n a = fAcc (n - 1) (n + a)
in fAcc n 0
-- tail recursion ver.2
--
fermaPyrAcc2 0 = 0
fermaPyrAcc2 n = fermaTriaAcc n + fermaTriaAcc (n - 1)
main = do
let a = fermaPyr 1000000
b = fermaPyrAcc 10000
c = fermaPyrAcc2 1000000
putStrLn $ show a
--putStrLn $ show b
--putStrLn $ show c
Запуск варианта а:
177,963,104 bytes allocated in the heap
187,666,896 bytes copied during GC
36,388,928 bytes maximum residency (8 sample(s))
36,384 bytes maximum slop
82 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 237 colls, 0 par 0.13s 0.13s 0.0005s 0.0014s
Gen 1 8 colls, 0 par 0.09s 0.10s 0.0119s 0.0285s
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.10s ( 0.10s elapsed)
GC time 0.22s ( 0.22s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.01s ( 0.01s elapsed)
Total time 0.33s ( 0.33s elapsed)
%GC time 67.7% (67.7% elapsed)
Alloc rate 1,831,837,945 bytes per MUT second
Productivity 32.3% of total user, 31.9% of total elapsed
Всё нормально, расход памяти, как и ожидалось, немалый, время исполнения тоже.
Запускаю вариант b:
3,201,017,336 bytes allocated in the heap
697,536 bytes copied during GC
46,240 bytes maximum residency (2 sample(s))
23,392 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 6104 colls, 0 par 0.03s 0.03s 0.0000s 0.0000s
Gen 1 2 colls, 0 par 0.00s 0.00s 0.0001s 0.0002s
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.96s ( 1.98s elapsed)
GC time 0.03s ( 0.03s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.99s ( 2.01s elapsed)
%GC time 1.7% (1.7% elapsed)
Alloc rate 1,635,694,726 bytes per MUT second
Productivity 98.3% of total user, 97.4% of total elapsed
Здесь, памяти расходуется гораздо меньше, но время исполнения… при аргументе на 2 порядка меньше, чем в других вариантах, работает в несколько раз медленнее. Увеличив аргумент на порядок, я уже не дожидался окончания расчётов.
Вариант с:
128,057,440 bytes allocated in the heap
29,752 bytes copied during GC
46,240 bytes maximum residency (2 sample(s))
23,392 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 243 colls, 0 par 0.00s 0.00s 0.0000s 0.0001s
Gen 1 2 colls, 0 par 0.00s 0.00s 0.0001s 0.0002s
INIT time 0.00s ( 0.00s elapsed)
MUT time 0.08s ( 0.09s elapsed)
GC time 0.00s ( 0.00s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.08s ( 0.09s elapsed)
%GC time 2.0% (2.1% elapsed)
Alloc rate 1,571,481,972 bytes per MUT second
Productivity 97.8% of total user, 94.8% of total elapsed
Самый быстрый и меньше всего расходует память.
Для меня не очевидна разница между вариантами b и с. Почему оно так? Я ожидал, что вариант b будет самым лучшим т.к. в функции fermaPyrAcc2 нет хвостовой рекурсии, она только в её внутреннем цикле.
