What make function with huge list so slow

[Alan Bawden]

Windson Yang <wiwindson at gmail.com> writes:

> 'I'm just running them in succession and seeing how long they'. The full
> code looks like this, this is only an example.py here. and I run 'time
> python3 example.py' for each function.
> 
>     def fib_dp(n):
>         dp = [0] * (n+1)
>         if n <= 1:
>             return n
>         dp[0], dp[1] = 0, 1
>         for i in range(2, n+1):
>             dp[i] = dp[i-1] + dp[i-2]
>         return dp[-1]
...
>     # run the function only once
>     # fib_dp(400000) # took more than 60s
>     # fib_dp2(400000) # took about 2s

Figure out how much memory fib_dp is holding on to right before it returns
the answer.  fib(400000) is a _big_ number!  And so is fib(399999), and
fib(399998), and fib(399997), etc.  By the time you're done, you're holding
on to quite a huge pile of storage here.  Depending on how much physical
memory you have, you much actually be swapping before you're done.

-- 
Alan Bawden