Haskell Фибоначчи кажется медленным

Я учусь Haskell, и я написал простую функцию Фибоначчи:Haskell Фибоначчи кажется медленным

fib :: Int -> Int 

fib 1 = 1 
fib 0 = 0 
fib n = (fib (n-1)) + (fib (n-2))

Кажется, компилировать нормально, и загрузку этого сценария в GHCI РЕПЛ я мог возиться с несколькими номерами , Я попытался

fib 33

и был удивлен, что она занимает около 4 секунд, чтобы дать результат. (Извините, я не знаю, как еще раз выполнить функцию в Haskell, так что считал себя).

Fib 33 не особо облагается налогом. Ответ составляет менее 4 миллионов. Итак, я предполагаю, что мой код не очень хорошо написан или есть некоторые проблемы с тем, как я делаю рекурсию (ну, это не так хорошо написано, что она не учитывает отрицательные целые числа). Вопрос в том, почему он медленный? Любая помощь приветствуется.

источник

2014-12-17 Anonymous

Этот вопрос кажется хорошей для Просмотра Кода. – Alexander

Когда вы смотрите на свой код, представьте себе, как часто вычисляется 'fib (5)'. На каждой итерации вы снова вычисляете все «внутренние» числа фибоначчи. – WeSt

Вы должны использовать классическую ленивую версию бесконечного списка: 'fibs = 0: 1: zipWith (+) fibs (tail fibs)' с 'fib n = fibs !! n'. См. [Вики о haskell о последовательности Фибоначчи] (https://www.haskell.org/haskellwiki/The_Fibonacci_sequence).Забавно, что Фибоначчи славится этой последовательностью, которая была всего лишь небольшим упражнением в книге, в которой он должен быть знаменит, что ввело ценность для Западной Европы. – AndrewC

Оценка заняла больше времени, чем вы ожидали, потому что ваша функция не использует memoization. См. this question или that question для ответов на вопрос о том, как определить функцию фибоначчи в Haskell с использованием memoization.

источник

2014-12-17 15:59:24

Ссылка memoization очень хорошо объяснила проблему. –

Оба вопроса и их ответы довольно эзотеричны. Как насчет * метода учебника? –

@ н.м. В зависимости от того, какой учебник вы используете, вы можете обнаружить, что ссылка haskellwiki показывает «метод учебника» (в разделе «Воспоминание с рекурсией»). –

Вы сравнили это время с другими языками?

Это рекурсивный алгоритм, который имеет сложность O (2^n). При n = 33, что дает ошеломляющее количество вызовов. Если вы посчитаете, сколько миллисекунд или наносекунд было за такой звонок, вы останетесь с очень замечательным ответом относительно фактической производительности.

Помните, что некоторые компиляторы/среда выполнения могут кэшировать возвращаемые значения функции (у Frerich была лучшая память, как это называется: memoization), что значительно повышает производительность в случае этого алгоритма. В этом случае этого не происходит, поэтому все эти 2^n рекурсивные вызовы происходят.

источник

2014-12-17 16:00:54 Gerino

Технически его сложность - «O (fib n)», следовательно, грубо «O (1.68^n)», что немного лучше, чем «O (2^n)». Это не влияет на вашу точку зрения: ее сложность все еще экспоненциальна, поэтому количество рекурсивных вызовов быстро становится непрактичным. – chi

Ваш алгоритм не очень хорош. Вы можете немного улучшить его, используя memoization, вплоть до O (n). Использование разделяй и властвуй, вы можете получить до O (журнал N):

import Data.Matrix 

fib :: Integer -> Integer 
fib n = ((fromLists [[1,1],[1,0]])^n) ! (1,2)

Идея заключается в том, что умножение ассоциативно, так что вы можете поместить свои брекеты на стратегически важных местах:

5^10 = (5 * 5 * 5 * 5 * 5) * (5 * 5 * 5 * 5 * 5) = (5 * 5 * 5 * 5 * 5)^2 = ((5 * 5) * (5 * 5) * 5)^2 = ((5 * 5)^2 * 5)^2 = (((5^2)^2) * 5)^2

Та же картина может быть применена к матричному умножению. И у Haskell уже реализовано это в своей библиотеке по умолчанию для (^).

Это действительно работает:

map fib [1..21] 
--! [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]

источник

2014-12-17 17:02:59

Haskell Фибоначчи кажется медленным

ответ

Смежные вопросы