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

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?. At first, I guess the reasons are 1. It took too much time looking up the value in the list (the worse case should be O(1) according to the document). However, the below function fib_dp_tem(400000) can finish in 2s, so looking up value should not be the bottleneck. def fib_dp_look(n): if n <= 1: return n dp = [0] * (n+1) dp[0], dp[1] = 0, 1 for i in range(2, n+1): # change dp[i] to tem, this function is not correct now but it return dp[-1] in 2s tem = dp[i-1] + dp[i-2] return dp[-1] 2. It took too much time setting up the value in the list (the worse case should be O(1) according to the document). Again, the below function fib_dp_set(400000) can finish in 2s, so setting value should not be the bottleneck too. def fib_dp_set(n): if n <= 1: return n dp = [0] * (n+1) dp[0], dp[1] = 0, 1 for i in range(2, n+1): # this function is not correct now but it return dp[-1] in 2s dp[i-1] = i dp[i-2] = i + 1 return dp[-1] 3. python use some kind of cache for 'pre', 'now' variable, (like 'register variable' in C, but I'm not sure how it work in CPython) I also tried to use the dis module but with no luck. Any reason to make fib_dp so much slower than fib_dp2? Please let me know, thank you. Bests, Windson

- Prev by Date:
**Newbie question about Python syntax** - Next by Date:
**What make function with huge list so slow** - Previous by thread:
**https://test.pypi.org/ internal server error** - Next by thread:
**What make function with huge list so slow** - Index(es):