Project Euler 14: производительность по сравнению с C и memoization

Ответ 1

После компиляции с оптимизацией все еще есть несколько отличий от программы C

• вы используете div, в то время как программа C использует разделение машины (которое усекает) [но любой уважающий себя компилятор C преобразует это в сдвиг, что делает его еще быстрее], это будет quot в Haskell; что сократило время работы примерно на 15%.
• программа C использует 64-битную (или даже 32-разрядную) с фиксированной шириной, но тогда просто удача, что она получает правильный ответ, поскольку некоторые промежуточные значения превосходят 32-битные диапазоны), программа Haskell использует произвольную точность Integer s. Если в вашем GHC (64-разрядная ОС, отличная от Windows) есть 64-разрядный Int, замените Integer на Int. Это сократило время работы примерно в 3 раза. Если вы используете 32-битную систему, вам не повезло, GHC не использует собственные 64-битные инструкции там, эти операции реализованы как C-вызовы, которые все еще довольно медленные.

Для memoisation вы можете передать его в один из пакетов memoisation для хакаса, единственный, который я помню, data-memocombinators, но есть и другие. Или вы можете сделать это самостоятельно, например, сохранить карту ранее рассчитанных значений - это будет лучше всего работать в монаде State,

import Control.Monad.State.Strict
import qualified Data.Map as Map
import Data.Map (Map, singleton)

type Memo = Map Integer Int

syr :: Integer -> State Memo Int
syr n = do
    mb <- gets (Map.lookup n)
    case mb of
      Just l -> return l
      Nothing -> do
          let m = if even n then n `quot` 2 else 3*n+1
          l <- syr m
          let l' = l+1
          modify (Map.insert n l')
          return l'

solve :: Integer -> Int -> Integer -> State Memo (Integer,Int)
solve maxi len start
    | len > 1000000 = return (maxi,len)
    | otherwise = do
         l <- syr start
         if len < l
             then solve start l (start+1)
             else solve maxi len (start+1)

p14 :: (Integer,Int)
p14 = evalState (solve 0 0 500000) (singleton 1 1)

но это, вероятно, не будет слишком большим (даже если вы добавили необходимую строгость). Проблема в том, что поиск в Map не слишком дешев, а вставка относительно дорога.

Другой метод - сохранить измененный массив для поиска. Код становится более сложным, так как вам нужно выбрать разумную верхнюю границу для кеширования значений (должно быть не намного больше, чем оценка для начальных значений) и иметь дело с частями последовательностей, выходящих за пределы памяти. Но поиск и запись массива бывают быстрыми. Если у вас есть 64-разрядный Int s, приведенный ниже код работает довольно быстро, здесь он принимает 0.03s для лимита в 1 миллион и 0,33 для лимита в 10 миллионов, соответствующего (насколько я мог бы разумно) Код C работает в 0,018 или 0.2s.

module Main (main) where

import System.Environment (getArgs)
import Data.Array.ST
import Data.Array.Base
import Control.Monad.ST
import Data.Bits
import Data.Int

main :: IO ()
main = do
    args <- getArgs
    let bd = case args of
               a:_ -> read a
               _   -> 100000
    print $ collMax bd

next :: Int -> Int
next n
    | n .&. 1 == 0  = n `unsafeShiftR` 1
    | otherwise     = 3*n + 1

collMax :: Int -> (Int,Int16)
collMax upper = runST $ do
    arr <- newArray (0,upper) 0 :: ST s (STUArray s Int Int16)
    let go l m
            | upper < m = go (l+1) $ next m
            | otherwise = do
                l' <- unsafeRead arr m
                case l' of
                  0 -> do
                      l'' <- go 1 $ next m
                      unsafeWrite arr m (l'' + 1)
                      return (l+l'')
                  _ -> return (l+l'-1)
        collect mi ml i
            | upper < i = return (mi, ml)
            | otherwise = do
                l <- go 1 i
                if l > ml
                  then collect i l (i+1)
                  else collect mi ml (i+1)
    unsafeWrite arr 1 1
    collect 1 1 2

Ответ 2

Ну, программа C использует unsigned long, но Integer может хранить произвольно большие целые числа (это bignum). Если вы импортируете Data.Word, вы можете использовать Word, который является целым числом без знака машинного слова.

После замены Integer на Word и используя ghc -O2 и gcc -O3, программа C запускается через 0,72 секунды, а программы Haskell - за 1,92 секунды. 2.6x неплохо. Однако ghc -O2 не всегда помогает, и это одна из программ, на которых это не так! Используя только -O, как и вы, время выполнения сокращается до 1,90 секунд.

Я попытался заменить div на quot (который использует тот же тип деления, что и C, они отличаются только от отрицательных входов), но, как ни странно, это фактически запустило программу Haskell для меня немного медленнее.

Вы можете ускорить функцию syr с помощью этого предыдущего вопроса о переполнении стека Я ответил о той же проблеме Project Euler.

Ответ 3

В моей текущей системе (32-разрядный Core2Duo) ваш код Haskell, включая все оптимизации, указанные в ответах, принимает 0.8s для компиляции и 1.2s для запуска.

Вы можете передать время выполнения во время компиляции и сократить время выполнения до нуля.

module Euler14 where

import Data.Word
import Language.Haskell.TH

terms :: Word -> Word
terms n = countTerms n 0
  where
    countTerms 1 acc             = acc + 1
    countTerms n acc | even n    = countTerms (n `div` 2) (acc + 1)
                     | otherwise = countTerms (3 * n + 1) (acc + 1)

longestT :: Word -> Word -> (Word, Word) 
longestT mi mx = find mi mx (0, 0)
  where
      find mi mx (ct,cn) | mi == mx  = if ct > terms mi then (ct,cn) else (terms mi, mi)
                         | otherwise = find (mi + 1) mx
                                       (if ct > terms mi then (ct,cn) else (terms mi, mi))

longest :: Word -> Word -> ExpQ
longest mi mx = return $ TupE [LitE (IntegerL (fromIntegral a)),
                               LitE (IntegerL (fromIntegral b))]
  where
    (a,b) = longestT mi mx

и

{-# LANGUAGE TemplateHaskell #-}
import Euler14

main = print $(longest 500000 999999)

В моей системе для компиляции требуется 2.3s, но время выполнения сокращается до 0.003s. Выполнение функции времени компиляции (CTFE) - это то, что вы не можете сделать в C/С++. Единственным другим языком программирования, который я знаю о поддержке CTFE, является D язык программирования. И чтобы быть полным, код C принимает 0.1s для компиляции и 0.7s для запуска.