Re: What make function with huge list so slow
> Figure out how much memory fib_dp is holding on to right before it returns > the answer. fib(40) is a _big_ number! And so is fib(39), and > fib(38), and fib(37), etc. By the time you're done, you're holding > on to quite a huge pile of storage here. Depending on how much physical > memory you have, you much actually be swapping before you're done. > > -- > Alan Bawden > -- > T Thank you Alan. You are right! we use too much memeoy to save the answer in the dp list. Now I get it, thank you so much. -- https://mail.python.org/mailman/listinfo/python-list
Re: What make function with huge list so slow
Windson Yang writes: > '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] ... > # run the function only once > # fib_dp(40) # took more than 60s > # fib_dp2(40) # took about 2s Figure out how much memory fib_dp is holding on to right before it returns the answer. fib(40) is a _big_ number! And so is fib(39), and fib(38), and fib(37), etc. By the time you're done, you're holding on to quite a huge pile of storage here. Depending on how much physical memory you have, you much actually be swapping before you're done. -- Alan Bawden -- https://mail.python.org/mailman/listinfo/python-list
Re: What make function with huge list so slow
'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(40) # took more than 60s # fib_dp2(40) # took about 2s -- https://mail.python.org/mailman/listinfo/python-list
Re: What make function with huge list so slow
On Sun, Aug 25, 2019 at 1:43 PM Windson Yang wrote: > > 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. (Please don't top-post) Are you running each function more than once, or just running them in succession and seeing how long they take? Show the full code you're using for the timing tests so we can recreate it. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: What make function with huge list so slow
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 于2019年8月25日周日 上午11:27写道： > On Sun, Aug 25, 2019 at 12:56 PM Windson Yang 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 40), fib_dp2(40) can calculate it in > 2s > > but fib_dp(40) 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 > -- https://mail.python.org/mailman/listinfo/python-list
Re: What make function with huge list so slow
On Sun, Aug 25, 2019 at 12:56 PM Windson Yang 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 40), fib_dp2(40) can calculate it in 2s > but fib_dp(40) 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
What make function with huge list so slow
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 40), fib_dp2(40) can calculate it in 2s but fib_dp(40) 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(40) 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(40) 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
