Ответ 1
Функция maximumBy будет многократно проверять один и тот же номер в вашем списке несколько раз - и каждый раз, когда он проверяет номер, он должен будет повторно вычислить cycleLength. И это дорогая операция!
Таким образом, алгоритм wiki использует метод, известный как decorate-sort-undecorate. Теперь, здесь вы не сортируете, но это достаточно близко. Сначала вы прекомпретируете значения cycleLength для всех чисел (т.е. Вы создаете "кеш" ), тогда вы выполняете максимальную операцию, а затем их декомпозицию (используя fst.) Таким образом, вы экономите себя на множестве вычислений
EDIT: чтобы проиллюстрировать это, посмотрите на функцию maximumBy в источнике Data.List:
-- | The 'maximumBy' function takes a comparison function and a list
-- and returns the greatest element of the list by the comparison function.
-- The list must be finite and non-empty.
maximumBy :: (a -> a -> Ordering) -> [a] -> a
maximumBy _ [] = error "List.maximumBy: empty list"
maximumBy cmp xs = foldl1 maxBy xs
where
maxBy x y = case cmp x y of
GT -> x
_ -> y
Он перемещается в окне 2; каждый номер запрашивается (и в вашем случае вычислено) дважды.
Это означает, что для 999 итераций ваша версия вызовет cycleLength d 1996 раз (n * 2-2), тогда как версия wiki будет называть ее 999 (n) раз.
Это не объясняет полную задержку - всего в 2 раза, но фактор был ближе к примерно 10.
Вот профиль вашей версии,
COST CENTRE entries %time %alloc %time %alloc
MAIN 0 0.0 0.0 100.0 100.0
CAF 0 0.0 0.0 100.0 100.0
main 1 0.0 0.0 100.0 100.0
f 1 0.0 0.0 100.0 100.0
maximumBy 1 0.0 0.0 100.0 99.9
maximumBy.maxBy 998 0.0 0.1 100.0 99.9
cycleLength 1996 0.1 0.2 100.0 99.8
remainders 581323 99.3 94.4 99.9 99.7
remainders.r' 581294 0.7 5.2 0.7 5.2
и версия wiki:
COST CENTRE entries %time %alloc %time %alloc
MAIN 0 0.0 0.0 100.0 100.0
CAF 0 0.0 0.0 100.0 99.9
main 1 0.0 0.1 100.0 99.9
f' 1 0.0 0.8 100.0 99.8
cycleLength 999 0.2 0.5 100.0 98.6
remainders 95845 98.3 93.0 99.8 98.2
remainders.r' 95817 1.5 5.2 1.5 5.2
maximumBy 1 0.0 0.1 0.0 0.4
maximumBy.maxBy 998 0.0 0.2 0.0 0.2
Если посмотреть на профиль здесь, кажется, что ваша версия проходит намного больше распределений (примерно в 10-12 раз больше), но не использует намного больше ОЗУ в целом. Поэтому нам нужно объяснить о совокупном коэффициенте 5 или 6 с точки зрения распределения.
Остатки рекурсивны. В вашем примере это называется 581294 раз. В примере wiki он называется 95817 раз. Там наш 5-6-кратный рост!
Итак, я думаю, что вызов compare здесь также является проблемой. Поскольку он применяет cycleLength к обоим вещам, которые мы хотим сравнить, также! В wiki-проблеме cycleLength применяется к каждому числу, но здесь мы применяем его к каждому числу дважды, и сравнение, кажется, применяется чаще, и это проблема, особенно с большими числами, поскольку remainders имеет плохую сложность (это кажется экспоненциальным, но я не уверен.)
Поскольку максимальное потребление памяти для обеих программ не так сильно отличается, я не думаю, что это имеет какое-то отношение к куче.