Сначала я подумал, что вы должны попробовать поставить восклицательный знак перед a в collatz:
collatz !a 1 = a
collatz !a x
| even x = collatz (a + 1) (x `div` 2)
| otherwise = collatz (a + 1) (3 * x + 1)
(вам нужно будет поставить {-# LANGUAGE BangPatterns #-} вверхувашего исходного файла, чтобы это сработало.)
Мои рассуждения сводились к следующему: проблема в том, что вы создаете массивный thunk в первом аргументе collatz: он начинается скак 1, а затем становится 1 + 1, а затем становится (1 + 1) + 1, ... все без принуждения.Этот шаблон взрыва заставляет первый аргумент collatz принудительно вызываться при каждом вызове, поэтому он начинается с 1, а затем становится 2 и т. Д., Без создания большого неоцененного thunk:он просто остается целым числом.
Обратите внимание, что шаблон взрыва - это просто сокращение для использования seq;в этом случае мы могли бы переписать collatz следующим образом:
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)
Хитрость здесь в том, чтобы заставить a в охране, которая затем всегда оценивается как Ложь (и поэтому телоне имеет значения).Затем оценка продолжается со следующего случая: a уже был оценен.Тем не менее, шаблон взрыва более ясен.
К сожалению, при компиляции с -O2 он не работает быстрее, чем оригинал!Что еще мы можем попробовать?Ну, одну вещь, которую мы можем сделать, это предположить, что эти два числа никогда не переполняют целое число машинного размера, и дать collatz эту аннотацию типа:
collatz :: Int -> Int -> Int
Мы оставим там шаблон взрыва, так как мывсе же следует избегать создания thunks, даже если они не являются причиной проблемы с производительностью.На моем (медленном) компьютере это время сокращается до 8,5 секунд.
Следующий шаг - попытаться приблизить это к решению Java.Первое, что нужно понять, это то, что в Haskell div ведет себя более математически правильно по отношению к отрицательным целым числам, но медленнее, чем «нормальное» деление C, которое в Haskell называется quot.Замена div на quot сократила время выполнения до 5,2 секунды, а замена x `quot` 2 на x `shiftR` 1 (импорт Data.Bits) для соответствия решению Java снизила его до 4,9 секунды.
Этопока что так низко, как я могу, но я думаю, что это довольно хороший результат;поскольку ваш компьютер работает быстрее, чем мой, мы надеемся, что он должен быть еще ближе к решению Java.
Вот окончательный код (я немного исправился):
{-# 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]
Глядя на ядро GHC для этой программы (с ghc-core), я думаю, что это, вероятно, примерно так же хорошо, как и получается;цикл collatz использует целые числа без коробки, а остальная часть программы выглядит нормально.Единственное улучшение, которое я могу придумать, - это исключить бокс из итерации map collatz [1..1000000].
Кстати, не беспокойтесь о значении "общего выделения";это общая память, выделенная за время жизни программы , и она никогда не уменьшается, даже когда GC освобождает эту память.Цифры нескольких терабайт являются общими.