Сообщение #6630

[konsoletyper]

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

Код:

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 сек, вопреки ожиданиям :-) )