Сообщение #6632

[mini_root]

Вот как то же на Хаскелле:

Код:

import IO
import CPUTime
import Numeric

fib = 1 : 1 : [a + b | (a, b) <- zip fib (tail fib)]

main = do
  putStrLn (show (fib!!46))
  time <- getCPUTime
  putStrLn (showFFloat (Just 6) (fromInteger time / 1e12) "")

Скомпилированный GHC код отработал 0.015625 секунд. Определение списка fib взял из Gentle Introduction. Заметьте, что это весьма лаконичное определение списка чисел Фибоначчи. А секрет быстрой работы в том, что во-первых, функция линеаризуется и раскручивается в цикл, а во-вторых, с помощью deforestation ликвидируется создание промежуточных структур. И никаких memoize не нужно.

Кстати, в отличие от всяких C, Nemerle и проч. данный вариант справится и с fib!!460 и даже с fib!!46000 (в этом случе код отрабатывает за 1.5 сек, вопреки ожиданиям :-) )

Мастер! Что еще сказать.... Я хаскелл так и не осилил пока перебиваюсь быдлоскалой...

P.S. Маленькое замечание, первым элементом списка должен быть 0.

Можно мелкий вопрос?:
fib = 0 : 1 : [a + b | (a, b) <- zip fib (tail fib)] - первые два элемента заданы явно, а третий и последующие как сумма a и b, где а и b берутся из конца списка. Я правильно понял? И еще, где указывается что нужно брать ДВА последних элемента из списка (я имею в виду конструкцию tail fib)?