I found some months ago that I could generate Hamming multiples of 3 and 5 multiples (3^x & 5^x) in one list comprehension. There are many fewer 3 and 5 Hamming multiples in a Hamming sequence. I did not have to be concerned with duplicate multiples as it is 2 disparate lists.
All I needed to do was add the Hamming 2 multiples.
When I did, it was chaos. Multiples of the 3 and 5 multiples with the 2^x produced clean Hamming numbers but left even more at the end of the list that had missing Hamming numbers between them.
The problem was the Cartesian product of the 2 multiples and the 3&5 multiples.
I had used the 3^x times 5^x’s in another algorithm successfully. I had limited the list with some involved calculation.
Then, I encountered the same problem working with primes. I wanted a list to subtract from a wheel but the list contained much excess. It was another huge Cartesian product of values.
I didn’t know which elements to eliminate from either list and I thought them intermixed.
Then it dawned on me. I tried it with the primes and it worked. Then with the Hamming 2s and it worked.
First I rewrote the 3 & 5 multiples list comprehension with the much simpler logic and way less calculation.
What was the solution? All it is, is using the end value of the generated first list to limit values of subsequent lists. List comprehensions take the first value of the first list and apply it to all values in the second list thus making a list. It is the first list end value that is the limit of each subsequent list. These limited lists do not generate any excess at the end of any list
The prime’s composite list to subtract is top and bottom diagonal to form a rouge triangle. In it x and y are identical. The Hammings lists are bottom, irregular diagonal only. The x and y are different.
My problem, now, is how to specify how many Hammings I want instead of the
2^x as the parameter. Is it just practical to use
take with some derived value of
2^x) to get the number of Hammings wanted? How can
x be derived from specified
n number of Hamming wanted? The second thing is how fast is this compared to the fastest Hamming list generators?
Thanks for any help you can offer.
The Hamming functions follow
gnf n f = scanl (*) 1 $ replicate f n mk35 n = (\c-> [m| t<- gnf 3 n, f<- gnf 5 n, m<- [t*f], m<= c]) (2^(n+1)) mkHams n = (\c-> sort [m| t<- mk35 n, f<- gnf 2 (n+1), m<- [t*f], m<= c]) (2^(n+1))
last $ mkHams 50
(0.03 secs, 12,869,000 bytes)
Well, I tried limiting differently but always come back to what is simplest.
I am opting for the least memory usage as also the fastest.
I also opted to use
map with an implicit parameter.
I also found that
Data.List.Ordered is faster that
concat. I also like when sublists are created so I can analyze the data much easier.
Then, because of @Wil Ness on SO switched to
iterate instead of
scanl making much cleaner code. Also because of @Wil Ness I stopped using last of of 2s list and switched to one value determining all lengths.
Just separating the function into two doesn't make a difference so the 3 and 5 multiples would be
m35 lim = mergeAll $ map (takeWhile (<=lim).iterate (*3)) $ takeWhile (<=lim).iterate (*5) $ 1
And the 2s each multiplied by the product of 3s and 5s
ham n = mergeAll $ map (takeWhile (<=lim).iterate (*2)) $ m35 lim where lim= 2^n
After editing the function I ran it
last $ ham 50
(0.00 secs, 7,029,728 bytes)
last $ ham 100
(0.03 secs, 64,395,928 bytes)
It is probably better to use
10^n but for comparison I again used `2^n.
Because I so prefer infinite and recursive lists I became a bit obsessed with making these infinite.
I was so impressed and inspired with @Daniel Wagner and his
Data.Universe.Helpers I started using
+++ but then added my own infinite list. I had to
mergeAll my list to work but then realized the infinite 3 and 5 multiples were exactly what they should be. So, I added the 2s and
mergeAlld everything and they came out. Before, I stupidly thought
mergeAll would not handle infinite list but it does most marvelously.
When a list is infinite in Haskell, Haskell calculates just what is needed, that is, is lazy. The adjunct is that it does calculate from, the start.
Now, since Haskell multiples until the limit of what is wanted, no limit is needed in the function, that is, no more
takeWhile. The speed up is incredible and the memory lowered too,
The following is on my slow home PC with 3GB of RAM.
tia = mergeAll.map (iterate (*2)) $ mergeAll.map (iterate (*3)) $ iterate (*5) 1
last $ take 10000 tia
(0.02 secs, 5,861,656 bytes)
I learned how to
gch -O2. The following is for 50,000 Hammings to 2.38E+30.
The only change from rerunning this is MUT is .016 and GC is .031 and total is .047 or like this one GC is .047 and total is the same.
INIT time 0.000s ( 0.000s elapsed) MUT time 0.000s ( 0.916s elapsed) GC time 0.047s ( 0.041s elapsed) EXIT time 0.000s ( 0.005s elapsed) Total time 0.047s ( 0.962s elapsed) Alloc rate 0 bytes per MUT second Productivity 0.0% of total user, 95.8% of total elapsed
@Will Ness rawks. He provided a clean and elegant revision of
tia above and it proved to be five times as fast in
GHCi. When I
ghc -O2 +RTS -s his against mine, mine was several times faster. There had to be a compromise.
So, I started reading about fusion that I had encountered in R. bird's Thinking Functionally with Haskell and almost immediately tried this.
mai n = mergeAll.map (iterate (*n)) mai 2 $ mai 3 $ iterate (*5) 1
It matched Will's at
0.08 for 100K Hammings in
GHCi but what really surprised me is (also for 100K Hammings.) The elapsed is really what gets me.
TASKS: 3 (1 bound, 2 peak workers (2 total), using -N1) SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled) INIT time 0.000s ( 0.000s elapsed) MUT time 0.000s ( 0.002s elapsed) GC time 0.000s ( 0.000s elapsed) EXIT time 0.000s ( 0.000s elapsed) Total time 0.000s ( 0.002s elapsed) Alloc rate 0 bytes per MUT second Productivity 100.0% of total user, 90.2% of total elapsed