Talk:Stern-Brocot sequence: Difference between revisions
(→Algorithm used in the C example is different: Perceptions.) |
|||
Line 17: | Line 17: | ||
In CPython lists are implemented as arrays dynamic on the right. I don't remember how exactly they (and the append/pop(0) methods) are implemented, but it's not easy to give to such data structure those operations efficient in both space and time. A collections.deque could be better. --[[User:Bearophile|bearophile]] ([[User talk:Bearophile|talk]]) |
In CPython lists are implemented as arrays dynamic on the right. I don't remember how exactly they (and the append/pop(0) methods) are implemented, but it's not easy to give to such data structure those operations efficient in both space and time. A collections.deque could be better. --[[User:Bearophile|bearophile]] ([[User talk:Bearophile|talk]]) |
||
::Sounds right. I will update it when I truly wake. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 03:28, 9 December 2014 (UTC) |
::Sounds right. I will update it when I truly wake. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 03:28, 9 December 2014 (UTC) |
||
===deque over list?=== |
|||
Well deque's are better for pushing and popping whilst Python lists are better for general indexing (deques loose the ability to be sliced, for example). After Bearophiles comment I decided on doing some timings: |
|||
<lang python>from itertools import takewhile, tee, islice |
|||
from collections import deque |
|||
from fractions import gcd |
|||
def stern_brocot1(): |
|||
...: sb = [1, 1] |
|||
...: while True: |
|||
...: sb += [sum(sb[:2]), sb[1]] |
|||
...: yield sb.pop(0) |
|||
...: |
|||
def stern_brocot2(): |
|||
...: sb = deque([1, 1]) |
|||
...: while True: |
|||
...: sb += [sum(sb[0] + sb[1]), sb[1]] |
|||
...: yield sb.popleft() |
|||
...: |
|||
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot1())) for occur in (list(range(1, 11)) + [2500])] |
|||
Wall time: 11.7 s |
|||
Out[30]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931] |
|||
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot1())) for occur in (list(range(1, 11)) + [2500])] |
|||
Wall time: 11.7 s |
|||
Out[31]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931] |
|||
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot1())) for occur in (list(range(1, 11)) + [2500])] |
|||
Wall time: 11.8 s |
|||
Out[32]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931] |
|||
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot2())) for occur in (list(range(1, 11)) + [2500])] |
|||
Wall time: 2.46 s |
|||
Out[33]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931] |
|||
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot2())) for occur in (list(range(1, 11)) + [2500])] |
|||
Wall time: 2.49 s |
|||
Out[34]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931] |
|||
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot2())) for occur in (list(range(1, 11)) + [2500])] |
|||
Wall time: 2.48 s |
|||
Out[35]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931]</lang> |
|||
The deque is faster, (and the margin increases for later members of the series). |
Revision as of 08:04, 9 December 2014
Finding first occurrences in Python: procedural version
Thanks Ledrug for pointing out a much better way to find first occurrence in the procedural Python example. Once you pointed it out, it became clear why your method worked.
I agree with you keeping it as a comment as well, as it does (at least for me), take another step to see that it works and now we have both methods. (either one of which could be commented). --Paddy3118 (talk) 21:34, 8 December 2014 (UTC)
Algorithm used in the C example is different
The task states a method of calculation that is not used in the current C example. I suggest another example closer to the given algorithm from the task description be used then this C example can be given as an alternative if the algorithm is explained. (I am thinking of starting another task that uses the tree construction and a comparison between the two, but time has not allowed ...). --Paddy3118 (talk) 21:47, 8 December 2014 (UTC)
- There's no real difference here: if you look at the n-th element, you obtain the 2n-1 and 2n-th elements, so you can always find each value backwards. The C program doesn't have a problem printing the first members in sequence, so what's wrong with that? --Ledrug (talk) 22:22, 8 December 2014 (UTC)
More functional Python entry
In such entry the "occurs" variable is not defined.
> (its sb variable stores less compared to the procedural version aboveby popping the last element every time around the while loop.
In CPython lists are implemented as arrays dynamic on the right. I don't remember how exactly they (and the append/pop(0) methods) are implemented, but it's not easy to give to such data structure those operations efficient in both space and time. A collections.deque could be better. --bearophile (talk)
deque over list?
Well deque's are better for pushing and popping whilst Python lists are better for general indexing (deques loose the ability to be sliced, for example). After Bearophiles comment I decided on doing some timings:
<lang python>from itertools import takewhile, tee, islice
from collections import deque
from fractions import gcd
def stern_brocot1():
...: sb = [1, 1] ...: while True: ...: sb += [sum(sb[:2]), sb[1]] ...: yield sb.pop(0) ...:
def stern_brocot2():
...: sb = deque([1, 1]) ...: while True: ...: sb += [sum(sb[0] + sb[1]), sb[1]] ...: yield sb.popleft() ...:
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot1())) for occur in (list(range(1, 11)) + [2500])] Wall time: 11.7 s Out[30]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931]
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot1())) for occur in (list(range(1, 11)) + [2500])] Wall time: 11.7 s Out[31]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931]
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot1())) for occur in (list(range(1, 11)) + [2500])] Wall time: 11.8 s Out[32]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931]
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot2())) for occur in (list(range(1, 11)) + [2500])] Wall time: 2.46 s Out[33]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931]
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot2())) for occur in (list(range(1, 11)) + [2500])] Wall time: 2.49 s Out[34]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931]
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot2())) for occur in (list(range(1, 11)) + [2500])] Wall time: 2.48 s Out[35]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931]</lang>
The deque is faster, (and the margin increases for later members of the series).