What make function with huge list so slow

[Windson Yang]

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
>