Почему этот простой алгоритм haskell настолько медленный?

Ответ 1

Сначала я подумал, что вы должны попробовать поставить восклицательный знак перед 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,... все без принуждения. Этот bang pattern заставляет первый аргумент collatz быть принудительным всякий раз, когда делается вызов, поэтому он начинается с 1, а затем становится 2, и т.д., не создавая большой неоценимый тон: он просто остается целым числом.

Обратите внимание, что шаблон взлома является только сокращением для использования 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 в охраннике, который тогда всегда оценивается как False (и поэтому тело не имеет значения). Затем оценка продолжается в следующем случае, уже оцененная. Тем не менее, картина взлома более ясна.

К сожалению, при компиляции с -O2 это не работает быстрее, чем оригинал! Что еще мы можем попробовать? Ну, мы можем только предположить, что два числа никогда не переполняют целое число в единице размера и дают collatz аннотацию этого типа:

collatz :: Int -> Int -> Int

Мы оставим шаблон взлома, поскольку нам все равно следует избегать наращивания громкости, даже если они не являются корнем проблемы производительности. Это сокращает время до 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 использует unboxed integers, а остальная часть программы выглядит нормально. Единственное улучшение, о котором я могу думать, это исключить бокс из итерации map collatz [1..1000000].

Кстати, не беспокойтесь о цифре "total alloc"; это общая память, выделенная за время жизни программы, и она никогда не уменьшается даже тогда, когда GC восстанавливает эту память. Цифры с несколькими терабайтами являются общими.

Ответ 2

Вы можете потерять список и шаблоны ударов и по-прежнему получать ту же производительность, используя стек.

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

Одна из проблем заключается в том, что вам придется увеличить размер стека для больших входов, например 1_000_000.

обновление:

Вот хвостовая рекурсивная версия, которая не страдает от проблемы.

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)

Обратите внимание на использование Word вместо Int. Это отличает производительность. Вы все равно можете использовать шаблоны ударов, если хотите, и это почти удвоит производительность.

Ответ 3

Одна вещь, которую я нашел, сделала удивительную разницу в этой проблеме. Я придерживался прямого рекуррентного отношения, а не складывался, вы должны простить выражение, подсчитывая его. Переписывание

collatz n = if even n then n `div` 2 else 3 * n + 1

а

collatz n = case n `divMod` 2 of
            (n', 0) -> n'
            _       -> 3 * n + 1

потребовалось 1,2 секунды от времени выполнения моей программы в системе с 2,8 ГГц Athlon II X4 430 CPU. Моя начальная более быстрая версия (через 2.3 секунды после использования 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]))

Возможно, более идиоматическая версия Haskell запускается примерно за 9,7 секунды (8.5 с divMod); он идентичен, кроме

collatzChainLen :: Int -> Int
collatzChainLen n = 1 + (length . takeWhile (/= 1) . (iterate collatz)) n

Использование Data.List.Stream должно позволить слияние потоков, которое сделает эту версию более похожей на нее с явным накоплением, но я не могу найти пакет libbc * Ubuntu, который имеет Data.List.Stream, поэтому я еще не может проверить это.