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
--
https://mail.python.org/mailman/listinfo/python-list
