Anonymous user
Talk:Stern-Brocot sequence: Difference between revisions
→More functional Python entry: deque over list?
(→Algorithm used in the C example is different: Perceptions.) |
|||
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]])
::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).
| |||