Talk:Stern-Brocot sequence: Difference between revisions
Content added Content deleted
(→deque over list?: remove unnecessary call to sum in deque example.) |
(→deque over list?: effect of sum over a slice.) |
||
| Line 68: | Line 68: | ||
The deque is faster, (and the margin increases for later members of the series). |
The deque is faster, (and the margin increases for later members of the series). |
||
That use of sum() over a slice of the list in the first version does turn out to be slow, but it does ''not'' tip the scales in favour of using a list: |
|||
<lang python>def stern_brocot3(): |
|||
...: sb = [1, 1] |
|||
...: while True: |
|||
...: sb += [sb[0] + sb[1], sb[1]] |
|||
...: yield sb.pop(0) |
|||
...: |
|||
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot3())) for occur in (list(range(1, 11)) + [2500])] |
|||
Wall time: 7.83 s |
|||
Out[43]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931] |
|||
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot3())) for occur in (list(range(1, 11)) + [2500])] |
|||
Wall time: 7.94 s |
|||
Out[44]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931] |
|||
%time [1 + sum(1 for i in takewhile(lambda x: x != occur, stern_brocot3())) for occur in (list(range(1, 11)) + [2500])] |
|||
Wall time: 8.12 s |
|||
Out[45]: [1, 3, 5, 9, 11, 33, 19, 21, 35, 39, 152931]</lang> |
|||