What make function with huge list so slow
Windson Yang
wiwindson at gmail.com
Sat Aug 24 23:43:44 EDT 2019
Thank you, Chris. I tried your suggestions. I don't think that is the
reason, fib_dp_look() and fib_dp_set() which also allocation a big list can
return in 2s.
Chris Angelico <rosuav at gmail.com> 于2019年8月25日周日 上午11:27写道:
> 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
> --
> https://mail.python.org/mailman/listinfo/python-list
>
More information about the Python-list
mailing list