What make function with huge list so slow
Windson Yang
wiwindson at gmail.com
Sun Aug 25 02:41:36 EDT 2019
'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]
def fib_dp2(n):
# add dp here just for calculating memory allocation time
dp = [0] * (n+1)
if n <= 1:
return n
pre, now = 0, 1
for i in range(2, (n+1)):
pre, now = now, pre+now
return now
# run the function only once
# fib_dp(400000) # took more than 60s
# fib_dp2(400000) # took about 2s
More information about the Python-list
mailing list