On Nov 14, 2007 1:06 PM, Brent Yorgey wrote:

On Nov 14, 2007 12:32 PM, Kurt Hutchinson wrote: The merging can be done much more simply and efficiently (this is code I wrote when computing squarefree numbers in a blog post a few months ago):

Wow, thanks for the tip. That really is a huge speed-up. I attempted something like this, but just tried doing a fold of the simple merge over the list of lists. That didn't work (not lazy enough?), which is what sent me down the complicated path above. Kurt

Brent Yorgey wrote:

Kurt Hutchinson wrote:

...

As part of a solution I'm working on for Project Euler problem 119, I wanted to create an ordered list of all powers of all positive integers (starting with squares).

The merging can be done much more simply and efficiently (this is code I wrote when computing squarefree numbers in a blog posthttp://byorgey.wordpress.com/2007/09/01/squarefree-numbers-in-haskell/a few months ago):

-- merge two nondecreasing lists. ( # ) :: (Ord a) => [a] -> [a] -> [a] [] # ys = ys xs # [] = xs xs@(x:xt) # ys@(y:yt) | x < y = x : (xt # ys) | x > y = y : (xs # yt) | otherwise = x : (xt # yt)

-- merge an infinite list of lists, assuming that each list -- is nondecreasing and the lists occur in order of their first -- element. mergeAll :: (Ord a) => [[a]] -> [a] mergeAll ([] : zs) = mergeAll zs mergeAll (xxs@(x:xs) : yys@(y:ys) : zs) | x < y = x : mergeAll (xs : yys : zs) | otherwise = mergeAll ((xxs # yys) : zs)

Then you can simply define

powers = 1 : mergeAll powertable

I wrote some code to sum the first n powers and print the result, and compiled (using -O2) first with your method, then with mergeAll. Summing the first 7000 powers took ~8s and ~0.1s respectively, so that's a pretty big speedup. Based on seeing how the times scale, I suspect that your code is O(n^2) or something of that sort, whereas mergeAll is essentially linear, although without scrutinizing your code more closely I'm not exactly sure why that would be the case.

In principle, both Kurt's and even your mergeAll are O(n^2), but that depends on the actual distribution of the numbers in the powertable. In both cases, the optimization over a naive implementation is to increase the number of rows to be considered only if the next output came from the last row. This is ok since of the last row, only the head element was considered so far and the non-considered elements all have to be bigger than this. Kurt's code is slower because it takes the minimum over _all_ the considered rows at every step. This is unnecessary since only one element changed, many comparisons can be "cached". In other words, this calls for a heap. Brent's code does not produce a heap, but I it's still able to cache lots of comparisons. Kurt may want to transpose the powertable to 2^2 3^2 4^2 5^2 .. 2^3 3^3 4^3 5^3 .. 2^4 3^4 4^4 .. .. instead of the current 2^2 2^3 2^4 2^5 .. 3^2 3^3 3^4 3^5 .. 4^2 4^3 4^4 .. .. since the first elements of the rows of the former grows far steeper than the ones of the latter. This means that only few rows are to be considered each turn. However, Brent may not want to transpose the powertable since the steep increase in every single row (as opposed to across rows) is exactly what makes his code fast. During evaluation, his tower of calls to # will compare something like the following numbers: 2^5 3^4 4^3 5^2 Thanks the form of the tower, the comparisons of the first elements are "cached". It looks like mergeAll $ (2^5:(__ # 3^4:__) # 4^3:__) : (5^2:xs) : __ The winner is 5^2 and mergeAll will proceeds by expecting the head of xs . But this one will first be compared to 2^5 = minimum [2^5,3^4,4^3] that's what I mean with "cached". Similarly, the winner 3^4 = minimum [2^5,3^4] is cached, too. In other words, the minimum of every initial segment of the numbers considered is "cached". The crucial point now is that those initial numbers quickly become very large (2^7 jumps exponentially to 2^8 and so on) and the winners are mostly to be found at the end of the list. With the caching, this is cheap to check. If Brent were to transpose the powertable , winners are more to the front of the list and the caching is useless, most likely rendering his implementation inferior to Kurt's one. Now, back to the heap and O(n*log n). There is no need to use an explicit heap data structure, it's possible to arrange the merges to form an implicit heap, i.e. using the best form of "caching". Here's an explanation of the technique with mergesort http://www.mail-archive.com/haskell@haskell.org/msg19980.html (Hm, does gmane gradually forget old messages?). The only problem is to make this work on an infinite list. Dave Bayer discovered a great way to do this, here's an explanation http://thread.gmane.org/gmane.comp.lang.haskell.cafe/26426/focus=26493 Regards, apfelmus

byorgey:

apfelmus, does someone pay you to write so many thorough, insightful and well-explained analyses on haskell-cafe? I'm guessing the answer is 'no', but clearly someone should! =)

Having met apfelmus last month in Freiburg I can inform the cafe that he is thorough and insightful not just in writing, but in person too :) -- Don

Calvin Smith wrote:

I really look forward to apfelmus' consistently outstanding explanations on haskell-cafe.

If some of the especially good ones were bundled up as book -- *Intermediate/Advanced Functional Programming with Haskell* -- I would buy it sight unseen (hint, hint).

:") I intend the Haskell wikibook http://en.wikibooks.org/wiki/Haskell to be(come) "the one" Beginner/Intermediate/Advanced Functional Programming book and the mailing list can also be seen as a marvelous source of materials, like "real world" questions, problems, techniques etc for that. The wikibook hasn't gained much momentum yet, but I guess that's also partly to the fact that writing a good tutorial is time consuming and harder than I imagined, mailing list rants are far easier :) Regards, apfelmus