'''http://c...content-available-to-author-only...e.com/recipes/117119/'''
from itertools import count,islice,groupby
from timeit import Timer
import collections
from heapq import merge
import __main__
def consume(iterator, n):
"Advance the iterator n-steps ahead. If n is none, consume entirely."
# Use functions that consume iterators at C speed.
if n is None:
# feed the entire iterator into a zero-length deque
collections.deque(iterator, maxlen=0)
else:
# advance to the empty slice starting at position n
next(islice(iterator, n, n), None)
def add(D,x,s):
while x in D:
x += s
D[x] = s
return x
'''
Unserstanding code from here: http://stackoverflow.com/a/10733621/862380
postponed sieve, by Will Ness
See also: http://i...content-available-to-author-only...e.com/WFv4f
'''
def primes4(debug=False,level=0):
'''The space complexity is needlessly O(n). O(sqrt(n)) is enough indeed,
achieved by postponing the addition of stepping information for a prime
into the dict until that prime's square is seen amongst the candidates,
and not a moment sooner.
Having much smaller dict, performance and empirical time complexity improve too.
http://i...content-available-to-author-only...e.com/WFv4f'''
name = '{0}'.format(level)
print = __builtins__.print if debug else lambda *p: None
print('{name}: yield 2'.format(name=name)); yield 2
print('{name}: yield 3'.format(name=name)); yield 3
print('{name}: yield 5'.format(name=name)); yield 5
print('{name}: yield 7'.format(name=name)); yield 7
D = {}
c = 9; print('{name}: c = {c}'.format(name=name,c=c))
ps = (p for p in primes4(debug=debug,level=level+1)); print('{name}: Creating subiterator'.format(name=name))
temp = next(ps)
print('{name}: skip {temp}'.format(name=name,temp=temp)) #skip 2
p = next(ps); print('{name}: p = {p}'.format(name=name,p=p)) # 3
q = p*p; print('{name}: q = {q}'.format(name=name,q=q)) # 9
while True:
print('{name}: D = {D}'.format(name=name,D=D))
if c not in D:
print('{name}: c not in D'.format(name=name))
if c < q:
print('{name}: c<q'.format(name=name))
print('{name}: yield c = {c}'.format(name=name,c=c))
yield c
else:
print('{name}: c=q'.format(name=name))
x = add(D,c+2*p,2*p); print('{name}: D[{x}]={s}'.format(name=name,x=x,s=2*p))
p = next(ps); print('{name}: p = {p}'.format(name=name,p=p))
q = p*p; print('{name}: q = {q}'.format(name=name,q=q))
else:
print('{name}: c in D'.format(name=name))
s = D.pop(c); print('{name}: popping from D: s = {s}'.format(name=name,s=s))
x = add(D, c+s, s); print('{name}: adding to D[{x}]={s}'.format(name=name,x=x,s=c+s))
c += 2; print('{name}: c+=2 -> c={c}'.format(name=name,c=c))
def primes5(debug=False,level=0):
primes = []
name = '{0}'.format(level)
print = __builtins__.print if debug else lambda *p: None
print('{name}: yield 2'.format(name=name)); primes.append(2); yield 2
print('{name}: yield 3'.format(name=name)); primes.append(3); yield 3
print('{name}: yield 5'.format(name=name)); primes.append(5); yield 5
print('{name}: yield 7'.format(name=name)); primes.append(7); yield 7
D = {}
c = 9; print('{name}: c = {c}'.format(name=name,c=c))
ps = (p for p in iter(primes)); print('{name}: Creating subiterator'.format(name=name))
temp = next(ps)
print('{name}: skip {temp}'.format(name=name,temp=temp)) #skip 2
p = next(ps); print('{name}: p = {p}'.format(name=name,p=p)) # 3
q = p*p; print('{name}: q = {q}'.format(name=name,q=q)) # 9
while True:
print('{name}: D = {D}'.format(name=name,D=D))
if c not in D:
print('{name}: c not in D'.format(name=name))
if c < q:
print('{name}: c<q'.format(name=name))
print('{name}: yield c = {c}'.format(name=name,c=c))
primes.append(c); yield c
else:
print('{name}: c=q'.format(name=name))
x = add(D,c+2*p,2*p); print('{name}: D[{x}]={s}'.format(name=name,x=x,s=2*p))
p = next(ps); print('{name}: p = {p}'.format(name=name,p=p))
q = p*p; print('{name}: q = {q}'.format(name=name,q=q))
else:
print('{name}: c in D'.format(name=name))
s = D.pop(c); print('{name}: popping from D: s = {s}'.format(name=name,s=s))
x = add(D, c+s, s); print('{name}: adding to D[{x}]={s}'.format(name=name,x=x,s=c+s))
c += 2; print('{name}: c+=2 -> c={c}'.format(name=name,c=c))
funcs = ['primes4','primes5']
number = 1 #number of runs
upper = 10000 #the upper limit for primes
def main():
'''Complexity comparison between different functions'''
for func_name in funcs:
f = getattr(__main__,func_name)
print('---')
print(f.__name__)
print(list(islice(f(),20)))
timer = Timer('consume(f(),{upper})'.format(upper=upper),
'from __main__ import {name} as f, consume'.format(name=func_name))
result = timer.timeit(number=number)
print('t: {}'.format(result/number))
if __name__=='__main__':
main()