fork download
copy 
  1. from itertools import tee, chain, groupby, islice, imap
  2. from heapq import merge
  3.  
  4. def fibonacci():               # created: 2013-03-12  by: Will Ness   
  5.     def deferred_output():     # for: rosettacode.org/wiki/Hamming_numbers
  6.         for i in output:       #            #Non-sharing_recursive_generator
  7.             yield i
  8.     result, c1, c2 = tee(deferred_output(), 3) # LINEAR !!!!!! ergo, w/SHARING!
  9.     paired = imap(add, c1, islice(c2, 1, None))  # 800 - 0.0 secs !!!!!
  10.     output = chain([0, 1], paired) 
  11.     return result
  12.  
  13. def add(x, y):
  14.     return x + y
  15.  
  16. def fibonacci_rec():
  17.     yield 0; yield 1;
  18.     c1, c2 = tee(fibonacci_rec(), 2)  # QUADRATIC !!@#$%@#$!!!!!!
  19.     c2.next()
  20.     for i in imap(add, c1, c2):
  21.         yield i
  22.  
  23. #for i in islice(fibonacci(), 800, 801):  # rec: 800-0.22 secs !! (400-0.06s)
  24. #    print(i),
  25. #print    
  26.  
  27. # -------------------------------
  28. def hamming_rec():
  29.     last = 1
  30.     yield last
  31.  
  32.     a,b,c = tee(hamming_rec(), 3)
  33.  
  34.     for n in merge((2*i for i in a), (3*i for i in b), (5*i for i in c)):
  35.         if n != last:
  36.             yield n
  37.             last = n
  38.  
  39.  
  40. def hamming():  # by Raymond Hettinger
  41.     # Generate "5-smooth" numbers, also called "Hamming numbers"
  42.     # or "Regular numbers".  See: en.wikipedia.org/wiki/Regular_number
  43.     # Finds solutions to 2**i * 3**j * 5**k  for some integers i, j, and k.
  44.  
  45.     def deferred_output():
  46.         for i in output:
  47.             yield i
  48.  
  49.     result, p2, p3, p5 = tee(deferred_output(), 4)
  50.     m2 = (2*x for x in p2)                          # multiples of 2
  51.     m3 = (3*x for x in p3)                          # multiples of 3
  52.     m5 = (5*x for x in p5)                          # multiples of 5
  53.     merged = merge(m2, m3, m5)
  54.     combined = chain([1], merged)                   # prepend a starting point
  55.     output = (k for k,g in groupby(combined))       # eliminate duplicates
  56.  
  57.     return result
  58.  
  59.  
  60. for i in islice(hamming(), 16000, 16001):  # rec: 2000-0.06s  4000-0.15s
  61.   print(i),                                # rec: 8000-0.39s (linearithmic?)  
  62.                         # rec: 16k: 1.01s ... n^1.37 ... sharing: 0.06s !!!
Success #stdin #stdout 0.07s 7864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
351387532108200960000
https://ideone.com/PIkWEN
https://e...content-available-to-author-only...a.org/wiki/Corecursion
created: 2013-03-12 11:11:35
language:
Python (cpython 2.7.16)
created:
6 years ago
visibility:
public

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!