Talk:Stern-Brocot sequence: Difference between revisions

: If you worry about speed, simply don't <code>pop()</code> the cache. You have to keep at least half of the array anyway:

<lang python>def stern_brocot0():

sb = [1, 1]

for i in count():

sb += [sb[i] + sb[i+1], sb[i+1]]

yield(sb[i])</lang>

: Or use a <code>tee</code> to do caching for you, counting on Python implementation being good:

<lang python>def stern_brocot4():

def gen():

a = next(tail)

for x in tail:

yield x + a

yield x

a = x

tail, out = tee(chain([1, 1], gen()))

for x in out: yield x</lang>

: Finding elements is better done by <code>len()</code> than by <code>sum()</code>, probably a small gain:

<lang python>print [1 + len(list(takewhile(lambda x: x != occur, stern_brocot2()))) for occur in range(1, 1000)]</lang>

: But it's better to skip the unnecessary lists altogether:

<lang python>def find(x, seq):

for i,v in enumerate(seq):

if v == x: return i + 1

# use it so:

# print [find(x, stern_brocot1()) for x in range(1, 1000)]</lang>

: In my tests, for larger numbers, using <code>find</code> along with <code>stern_brocot4()</code> is noticeably faster than other combinations. --[[User:Ledrug|Ledrug]] ([[User talk:Ledrug|talk]]) 19:39, 9 December 2014 (UTC)