fork download
copy 
  1. '''http://c...content-available-to-author-only...e.com/recipes/117119/'''
  2.  
  3. from itertools import count,islice,groupby
  4. from timeit import Timer
  5. import collections
  6. from heapq import merge
  7. import __main__
  8.  
  9.  
  10. def consume(iterator, n):
  11.     "Advance the iterator n-steps ahead. If n is none, consume entirely."
  12.     # Use functions that consume iterators at C speed.
  13.     if n is None:
  14.         # feed the entire iterator into a zero-length deque
  15.         collections.deque(iterator, maxlen=0)
  16.     else:
  17.         # advance to the empty slice starting at position n
  18.         next(islice(iterator, n, n), None)
  19.  
  20.  
  21. def add(D,x,s):
  22.     while x in D:
  23.         x += s
  24.     D[x] = s
  25.     return x
  26.  
  27.  
  28. '''
  29. Unserstanding code from here: http://stackoverflow.com/a/10733621/862380
  30. postponed sieve, by Will Ness
  31. See also: http://i...content-available-to-author-only...e.com/WFv4f
  32. '''        
  33. def primes4(debug=False,level=0):
  34.     '''The space complexity is needlessly O(n). O(sqrt(n)) is enough indeed,
  35.     achieved by postponing the addition of stepping information for a prime
  36.     into the dict until that prime's square is seen amongst the candidates,
  37.     and not a moment sooner.
  38.     Having much smaller dict, performance and empirical time complexity improve too.
  39.     http://i...content-available-to-author-only...e.com/WFv4f'''
  40.  
  41.     name = '{0}'.format(level)
  42.  
  43.     print = __builtins__.print if debug else lambda *p: None
  44.  
  45.     print('{name}: yield 2'.format(name=name)); yield 2 
  46.     print('{name}: yield 3'.format(name=name)); yield 3
  47.     print('{name}: yield 5'.format(name=name)); yield 5
  48.     print('{name}: yield 7'.format(name=name)); yield 7 
  49.     D = {}              
  50.     c = 9; print('{name}: c = {c}'.format(name=name,c=c))
  51.     ps = (p for p in primes4(debug=debug,level=level+1)); print('{name}: Creating subiterator'.format(name=name))
  52.     temp = next(ps)
  53.     print('{name}: skip {temp}'.format(name=name,temp=temp))     #skip 2 
  54.     p = next(ps); print('{name}: p = {p}'.format(name=name,p=p)) # 3
  55.     q = p*p; print('{name}: q = {q}'.format(name=name,q=q))      # 9
  56.     while True:
  57.         print('{name}: D = {D}'.format(name=name,D=D))
  58.         if c not in D:
  59.             print('{name}: c not in D'.format(name=name))
  60.             if c < q:
  61.                 print('{name}: c<q'.format(name=name))
  62.                 print('{name}: yield c = {c}'.format(name=name,c=c))
  63.                 yield c 
  64.             else:
  65.                 print('{name}: c=q'.format(name=name))
  66.                 x = add(D,c+2*p,2*p); print('{name}: D[{x}]={s}'.format(name=name,x=x,s=2*p)) 
  67.                 p = next(ps); print('{name}: p = {p}'.format(name=name,p=p))
  68.                 q = p*p; print('{name}: q = {q}'.format(name=name,q=q))
  69.         else:
  70.             print('{name}: c in D'.format(name=name))
  71.             s = D.pop(c); print('{name}: popping from D: s = {s}'.format(name=name,s=s))
  72.             x = add(D, c+s, s); print('{name}: adding to D[{x}]={s}'.format(name=name,x=x,s=c+s))
  73.         c += 2; print('{name}: c+=2 -> c={c}'.format(name=name,c=c))
  74.  
  75.  
  76. def primes5(debug=False,level=0):
  77.  
  78.     primes = []
  79.  
  80.     name = '{0}'.format(level)
  81.  
  82.     print = __builtins__.print if debug else lambda *p: None
  83.  
  84.     print('{name}: yield 2'.format(name=name)); primes.append(2); yield 2 
  85.     print('{name}: yield 3'.format(name=name)); primes.append(3); yield 3
  86.     print('{name}: yield 5'.format(name=name)); primes.append(5); yield 5
  87.     print('{name}: yield 7'.format(name=name)); primes.append(7); yield 7 
  88.     D = {}              
  89.     c = 9; print('{name}: c = {c}'.format(name=name,c=c))
  90.     ps = (p for p in iter(primes)); print('{name}: Creating subiterator'.format(name=name))
  91.     temp = next(ps)
  92.     print('{name}: skip {temp}'.format(name=name,temp=temp))     #skip 2 
  93.     p = next(ps); print('{name}: p = {p}'.format(name=name,p=p)) # 3
  94.     q = p*p; print('{name}: q = {q}'.format(name=name,q=q))      # 9
  95.     while True:
  96.         print('{name}: D = {D}'.format(name=name,D=D))
  97.         if c not in D:
  98.             print('{name}: c not in D'.format(name=name))
  99.             if c < q:
  100.                 print('{name}: c<q'.format(name=name))
  101.                 print('{name}: yield c = {c}'.format(name=name,c=c))
  102.                 primes.append(c); yield c 
  103.             else:
  104.                 print('{name}: c=q'.format(name=name))
  105.                 x = add(D,c+2*p,2*p); print('{name}: D[{x}]={s}'.format(name=name,x=x,s=2*p)) 
  106.                 p = next(ps); print('{name}: p = {p}'.format(name=name,p=p))
  107.                 q = p*p; print('{name}: q = {q}'.format(name=name,q=q))
  108.         else:
  109.             print('{name}: c in D'.format(name=name))
  110.             s = D.pop(c); print('{name}: popping from D: s = {s}'.format(name=name,s=s))
  111.             x = add(D, c+s, s); print('{name}: adding to D[{x}]={s}'.format(name=name,x=x,s=c+s))
  112.         c += 2; print('{name}: c+=2 -> c={c}'.format(name=name,c=c))
  113.  
  114.  
  115.  
  116.  
  117.  
  118. funcs = ['primes4','primes5']
  119.  
  120.  
  121. number = 1 #number of runs
  122. upper = 10000 #the upper limit for primes
  123.  
  124. def main():
  125.     '''Complexity comparison between different functions'''
  126.     for func_name in funcs:
  127.         f = getattr(__main__,func_name)
  128.         print('---')
  129.         print(f.__name__)
  130.         print(list(islice(f(),20)))
  131.         timer = Timer('consume(f(),{upper})'.format(upper=upper),
  132.                       'from __main__ import {name} as f, consume'.format(name=func_name))
  133.         result = timer.timeit(number=number)
  134.         print('t: {}'.format(result/number))
  135.  
  136.  
  137.  
  138. if __name__=='__main__':
  139.     main()
Success #stdin #stdout 7.76s 6276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
---
primes4
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
t: 3.84812188148
---
primes5
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
t: 3.88595104218
https://ideone.com/QV4EQ
language:
Python 3 (python  3.9.5)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!