osdir.com


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

What make function with huge list so slow


On Sun, Aug 25, 2019 at 12:56 PM Windson Yang <wiwindson at gmail.com> wrote:
>
> I have two functions to calculate Fibonacci numbers. fib_dp use a list to
> store the calculated number. fib_dp2 just use two variables.
>
>     def fib_dp(n):
>         if n <= 1:
>             return n
>         dp = [0] * (n+1)
>         dp[0], dp[1] = 0, 1
>         for i in range(2, n+1):
>             dp[i] = dp[i-1] + dp[i-2]
>         return dp[-1]
>
>     def fib_dp2(n):
>         if n <= 1:
>             return n
>         pre, now = 0, 1
>         for i in range(2, (n+1)):
>             pre, now = now, pre+now
>         return now
>
> Theoretically, both of their time complexity should be O(n). However, when
> the input n is so big (like 400000), fib_dp2(400000) can calculate it in 2s
> but fib_dp(400000) takes *more than 60s* (python3.7.3 and macOS 10.14.6).
> Why?

Memory allocation can take a long time. Try grabbing the line
initializing dp and slapping that into the body of dp2, and then
compare their times; that might make all the difference.

ChrisA