Ir al contenido principal

La función de Fibonacci por programación dinámica

Los primeros términos de la sucesión de Fibonacci son

   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Escribir dos definiciones (una recursiva y otra con programación dinámica) de la función

   fib :: Integer -> Integer

tal que fib n es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,

   fib 6 == 8

Comparar la eficiencia de las dos definiciones.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module La_funcion_de_Fibonacci_por_programacion_dinamica where

import Data.Array
import Test.Hspec (Spec, hspec, it, shouldBe)

-- 1ª definición (por recursión)
-- =============================

fib1 :: Integer -> Integer
fib1 0 = 0
fib1 1 = 1
fib1 n = fib1 (n-1) + fib1 (n-2)

-- 2ª definición (con programación dinámica)
-- =========================================

fib2 :: Integer -> Integer
fib2 n = vectorFib2 n ! n

-- (vectorFib2 n) es el vector con índices de 0 a n tal que el valor
-- de la posición i es el i-ésimo número de Finonacci. Por ejemplo,
--    λ> vectorFib2 7
--    array (0,7) [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13)]
vectorFib2 :: Integer -> Array Integer Integer
vectorFib2 n = v where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 0
  f 1 = 1
  f m = v!(m-1) + v!(m-2)

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> fib1 34
--    5702887
--    (11.82 secs, 3,504,944,704 bytes)
--    λ> fib2 34
--    5702887
--    (0.01 secs, 587,808 bytes)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    fib1 6 `shouldBe` 8
  it "e2" $
    fib2 6 `shouldBe` 8
  it "e3" $
    map fib1 [0..9] `shouldBe` map fib2 [0..9]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--
--    Finished in 0.0007 seconds
--    3 examples, 0 failures
--    (0.01 secs, 788,952 bytes)

Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer

import numpy as np
import numpy.typing as npt

setrecursionlimit(10**6)

# 1ª definición (por recursión)
# =============================

def fib1(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib1(n - 1) + fib1(n - 2)

# 2ª definición (con programación dinámica)
# =========================================

def fib2(n: int) -> int:
    return vectorFib2(n)[n]

# (vectorFib2 n) es el vector con índices de 0 a n tal que el valor
# de la posición i es el i-ésimo número de Finonacci. Por ejemplo,
#    >>> vectorFib2(7)
#    [0, 1, 1, 2, 3, 5, 8, 13]
def vectorFib2(n: int) -> list[int]:
    v = [0] * (n + 1)
    v[0] = 0
    v[1] = 1
    for i in range(2, n + 1):
        v[i] = v[i - 1] + v[i - 2]
    return v

# 2ª definición (con programación dinámica y array)
# =================================================

def fib3(n: int) -> int:
    return vectorFib3(n)[n]

# (vectorFib3 n) es el vector con índices de 0 a n tal que el valor
# de la posición i es el i-ésimo número de Finonacci. Por ejemplo,
#    >>> vectorFib3(7)
#    array([ 0,  1,  1,  2,  3,  5,  8, 13])
def vectorFib3(n: int) -> npt.NDArray[np.complex64]:
    v = np.zeros(n + 1, dtype=int)
    v[0] = 0
    v[1] = 1
    for i in range(2, n + 1):
        v[i] = v[i - 1] + v[i - 2]
    return v

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('fib1(34)')
#    2.10 segundos
#    >>> tiempo('fib2(34)')
#    0.00 segundos
#    >>> tiempo('fib3(34)')
#    0.00 segundos
#
#    >>> tiempo('fib2(100000)')
#    0.37 segundos
#    >>> tiempo('fib3(100000)')
#    0.08 segundos

# Verificación
# ============

def test_fib() -> None:
    assert fib1(6) == 8
    assert fib2(6) == 8
    assert fib3(6) == 8
    print("Verificado")

# La verificación es
#    >>> test_fib()
#    Verificado