Talk:Hamming numbers: Difference between revisions
Content added Content deleted
(→Original DrDobbs blog discussion: upd link) |
(→"Cyclic generator variant #1" not efficient: new section) |
||
Line 79: | Line 79: | ||
::Thank ''you'' for getting inspired and making this page happen! :) The book in question is "A Discipline of Programming", Prentice-Hall, [http://web.cecs.pdx.edu/~cs410aph/Lectures/Smalltalk%20II/Dijkstra%20on%20Hamming's%20Problem.pdf chap. 17 "An Exercise Attributed to R.W.Hamming"], [http://i.imgur.com/tPygG.gif pg. 132]. -- [[User:WillNess|WillNess]] 17:40, 29 August 2012 (UTC) |
::Thank ''you'' for getting inspired and making this page happen! :) The book in question is "A Discipline of Programming", Prentice-Hall, [http://web.cecs.pdx.edu/~cs410aph/Lectures/Smalltalk%20II/Dijkstra%20on%20Hamming's%20Problem.pdf chap. 17 "An Exercise Attributed to R.W.Hamming"], [http://i.imgur.com/tPygG.gif pg. 132]. -- [[User:WillNess|WillNess]] 17:40, 29 August 2012 (UTC) |
||
== "Cyclic generator variant #1" not efficient == |
|||
The Python [[Hamming numbers#Cyclic generator variant #1.|Cyclic generator variant #1.]] that is said to be much simpler, is not really equivalent to the other solutions. I compared it to another version, measuring how many times the <code>merge</code> iterator is advanced: |
|||
<lang python>from itertools import tee, chain, groupby, islice |
|||
import heapq |
|||
count = 0 |
|||
def merge(*args): |
|||
global count |
|||
for x in heapq.merge(*args): |
|||
count += 1 |
|||
yield x |
|||
def raymonds_hamming(): |
|||
# Generate "5-smooth" numbers, also called "Hamming numbers" |
|||
# or "Regular numbers". See: http://en.wikipedia.org/wiki/Regular_number |
|||
# Finds solutions to 2**i * 3**j * 5**k for some integers i, j, and k. |
|||
def deferred_output(): |
|||
for i in output: |
|||
yield i |
|||
result, p2, p3, p5 = tee(deferred_output(), 4) |
|||
m2 = (2*x for x in p2) # multiples of 2 |
|||
m3 = (3*x for x in p3) # multiples of 3 |
|||
m5 = (5*x for x in p5) # multiples of 5 |
|||
merged = merge(m2, m3, m5) |
|||
combined = chain([1], merged) # prepend a starting point |
|||
output = (k for k,g in groupby(combined)) # eliminate duplicates |
|||
return result |
|||
print list(islice(raymonds_hamming(), 100)) |
|||
print count</lang> |
|||
<lang python>from itertools import tee, chain, groupby, islice |
|||
import heapq |
|||
count = 0 |
|||
def merge(*args): |
|||
global count |
|||
for x in heapq.merge(*args): |
|||
count += 1 |
|||
yield x |
|||
def hamming_numbers(): |
|||
last = 1 |
|||
yield last |
|||
a,b,c = tee(hamming_numbers(), 3) |
|||
for n in merge((2*i for i in a), (3*i for i in b), (5*i for i in c)): |
|||
if n != last: |
|||
yield n |
|||
last = n |
|||
print list(islice(hamming_numbers(), 100)) |
|||
print count</lang> |
|||
The results I get: |
|||
{| class="wikitable" |
|||
|- |
|||
! number of items printed !! raymonds_hamming !! hamming_numbers |
|||
|- |
|||
| 20 || 28 || 59 |
|||
|- |
|||
| 100 || 201 || 670 |
|||
|- |
|||
| 1,000 || 2,506 || 17,822 |
|||
|- |
|||
| 10,000 || 27,634 || 420,168 |
|||
|- |
|||
| 100,000 || 288,851 || 9,429,734 |
|||
|} |
|||
The new "Cyclic generator variant #1" version seems to be much, much worse. --[[User:Spoon!|Spoon!]] 20:52, 12 October 2012 (UTC) |