Выражение Фибоначчи в замкнутой форме, монада ST и Хаскелл

Question

Два недавних вопроса о выражении Фибоначчи в замкнутой форме ( здесь и здесь ), а также страница HaskellWiki о монаде ST побудили меня попробовать и Сравните два способа вычисления чисел Фибоначчи.

Первая реализация использует выражение закрытой формы вместе с рациональными значениями, как видно из ответа Хаммара здесь (где Fib - это тип данных, абстрагирующий числа в форме a + b * √5):

fibRational :: Integer -> Integer
fibRational n = divSq5 $ phi^n - (1-phi)^n
  where
    phi = Fib (1/2) (1/2)
    divSq5 (Fib 0 b) = numerator b

Вторая реализация взята со страницы HaskellWiki о монаде ST, с некоторой дополнительной строгостью, необходимой для предотвращения переполнения стека:

fibST :: Integer -> Integer
fibST n | n < 2 = n
fibST n = runST $ do
    x <- newSTRef 0
    y <- newSTRef 1
    fibST' n x y
  where
    fibST' 0 x _ = readSTRef x
    fibST' !n x y = do
      x' <- readSTRef x
      y' <- readSTRef y
      y' `seq` writeSTRef x y'
      x' `seq` writeSTRef y (x'+y')
      fibST' (n-1) x y

Для справки, вот также полный код, который я использовал для тестирования:

{-# LANGUAGE BangPatterns #-}

import Data.Ratio
import Data.STRef.Strict
import Control.Monad.ST.Strict
import System.Environment

data Fib =
  Fib !Rational !Rational
  deriving (Eq, Show)

instance Num Fib where
  negate (Fib a b) = Fib (-a) (-b)
  (Fib a b) + (Fib c d) = Fib (a+c) (b+d)
  (Fib a b) * (Fib c d) = Fib (a*c+5*b*d) (a*d+b*c)
  fromInteger i = Fib (fromInteger i) 0
  abs = undefined
  signum = undefined

fibRational :: Integer -> Integer
fibRational n = divSq5 $ phi^n - (1-phi)^n
  where
    phi = Fib (1/2) (1/2)
    divSq5 (Fib 0 b) = numerator b

fibST :: Integer -> Integer
fibST n | n < 2 = n
fibST n = runST $ do
    x <- newSTRef 0
    y <- newSTRef 1
    fibST' n x y
  where
    fibST' 0 x _ = readSTRef x
    fibST' !n x y = do
      x' <- readSTRef x
      y' <- readSTRef y
      y' `seq` writeSTRef x y'
      x' `seq` writeSTRef y (x'+y')
      fibST' (n-1) x y

main = do
  (m:n:_) <- getArgs 
  let n' = read n
      st = fibST n'
      rt = fibRational n'
  case m of
    "st" -> print st
    "rt" -> print rt
    "cm" -> print (st == rt)

Теперь выясняется, что версия ST значительно медленнее, чем версия закрытой формы, хотя я не уверен на сто процентов, почему:

# time ./fib rt 1000000 >/dev/null
./fib rt 1000000 > /dev/null  0.23s user 0.00s system 99% cpu 0.235 total

# time ./fib st 1000000 >/dev/null
./fib st 1000000 > /dev/null  11.35s user 0.06s system 99% cpu 11.422 total

Итак, мой вопрос: Может кто-нибудь помочь мне понять, почему первая реализация намного быстрее? Это алгоритмическая сложность, накладные расходы или что-то совсем другое? (Я проверил, что обе функции дают одинаковый результат). Спасибо!

Answer 1

Вы сравниваете очень разные версии здесь.Если честно, вот реализация, которая эквивалентна предоставленному вами решению ST, но в чистом Haskell:

fibIt :: Integer -> Integer
fibIt n | n < 2 = n
fibIt n = go 1 1 (n-2)
  where go !_x !y  0 = y
        go !x  !y  i = go y (x+y) (i-1)

Кажется, что эта производительность работает точно так же хорошо или плохо, как STверсия (обе 10с здесь).В среде выполнения, скорее всего, преобладают все дополнения Integer, поэтому накладные расходы слишком малы, чтобы их можно было измерить.

Answer 2

Во-первых, в двух реализациях используются два совершенно разных алгоритма с разной асимптотической сложностью (ну, в зависимости от сложности операций Integer).Во-вторых, первая реализация использует ссылки.Ссылки (сравнительно) медленно в GHC.(Поскольку обновление ссылки требует барьера записи GC из-за сборщика мусора поколений.)

Итак, вы сравниваете две функции, которые различаются алгоритмом и техникой реализации.Вы должны переписать второй, чтобы не использовать ссылки, чтобы вы могли сравнивать только алгоритмы.Или перепишите первый, чтобы использовать ссылки.Но зачем использовать ссылки, когда это неправильно?:)

Answer 3

Вы можете сравнить алгоритмические сложности.

Первый - O (1);

второй O (n)