What make function with huge list so slow
Alan Bawden
alan at csail.mit.edu
Sun Aug 25 03:28:13 EDT 2019
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
More information about the Python-list
mailing list