fork download
  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 [email protected]#$%@#$!!!!!!
  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
stdin
Standard input is empty
stdout
351387532108200960000