Временная сложность zip с фибоначчи в Haskell - PullRequest
Новая
       15

Временная сложность zip с фибоначчи в Haskell

2 голосов
/ 22 марта 2019

В Haskell канонический zip с реализацией функции Фибоначчи: 

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Мне сложно проанализировать сложность этого времени (выдумки! N). Пытаясь написать это на бумаге, сначала я подумал, что это экспоненциально. Тогда O (n ^ 2), но я понятия не имею, как это происходит, чтобы быть линейным.

Почему я думаю, что это линейно: https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation

Также я написал другой код: 

fibs :: [Integer]
fibs = inc (0,1) where inc (a,b) = a : inc (b,a+b)

Это, я считаю, явно O (n). Но используя опцию: set + s в ghci, я вижу, что реализация zipWith явно превосходит мою.

Примечание: я знаю, что для сложения n-го и (n-1) -го числа Фибоначчи требуется O (n) время. Таким образом, во время тестирования я сделал базовый вариант, то есть первые два элемента 0: 0. Временные сложности упоминаются с использованием того же предположения.

Было бы здорово, если бы я мог получить некоторую помощь в отслеживании этих вызовов функций. Мне интересно узнать, когда была вызвана функция, и, возможно, напечатать что-нибудь, чтобы сообщить мне, что происходит.

Моя неудачная попытка: 

zipWith' = trace ("Called zipWith") (zipWith)
add' a b = trace (show a ++ " + " ++ (show b)) (add a b)
fibs = trace ("Called fibs") (1 : 1 : zipWith (+) fibs (tail fibs))

Это не работает. Заявления напечатаны ровно один. За исключением добавления, которое работает отлично, на удивление.

Я хочу знать, сколько раз и в каком порядке вызывались эти функции.

1 Ответ

3 голосов
/ 22 марта 2019

Я полагаю, что ваша версия медленная в первую очередь потому, что вы запускаете ее без оптимизации, и в результате вы получаете кучу ненужных кортежей.Частично оптимизированная вручную (и более идиоматическая) версия была бы 

fibs = inc 0 1
  where
    inc a b = a : inc b (a+b)

Давайте посмотрим на классику: 

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Начальное представление в памяти выглядит очень похоже на это.Это список минусов, указывающих на число 1, и второй список минусов, указывающих на число 1, и символ, представляющий zipWith (+) fibs (tail fibs).Что происходит, когда этот толчок принудительно?Ну, zipWith нужно проверить оба аргумента списка.Это так, и, видя, что они не равны NULL, выдает список минусов, указывающих на thunk, представляющий 1+1, и thunk, представляющий zipWith (+) fibs' (tail fibs'), где fibs' - указатель на second минусы в последовательности.Нет необходимости снова оценивать fibs для каждого из zipWith аргументов или чего-либо подобного.

...