Сообщение #6639

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

Сделал свой аналог на скале:
def fib(_n : BigInt): List[BigInt] =
 {
  if (_n ==0 ) {List[BigInt](0);}
  else if ( _n == 1 ) {List[BigInt](1,0);}
  else {val l = fib(_n-1); List[BigInt](l.head + l.tail.head) ::: l;}
 }

val startTm : long = System.currentTimeMillis();
Console.println(fib(460).head);
val endTm : long = System.currentTimeMillis();
Console.println("Total time: "+(endTm - startTm));

Результат:

60929766364353089279195197999021720669389417532925504644464121947359
6270869815908465388209600595
Total time: 29


Впрочем, это по сути тот же Memoize - то же сохранения результатов