On Nov 14, 2007 12:32 PM, Kurt Hutchinson <[EMAIL PROTECTED]> 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). This is what I came up with: > > powers = ( uniq . map fst . iterate next ) ( 1, ( 0, powertable ) ) > > powertable = map (\ n -> map (\ p -> n ^ p ) [ 2 .. ] ) [ 2 .. ] > > next ( _, ( lim, ps ) ) = > ( p, ( lim', ps' ) ) > where > ( c, p ) = minimumBy ( compare `on` snd ) . zip [ 0 .. lim ] . > head . transpose $ ps > lim' = lim + ( if c == lim then 1 else 0 ) > ( front, b : back ) = splitAt c ps > ps' = front ++ ( tail b : back ) > > -- like the unix utility > uniq [] = [] > uniq [x] = [x] > uniq (x:y:ys) > | x == y = uniq (y:ys) > | otherwise = x : uniq (y:ys) > > Basically, think of a grid of numbers, each row is the list of powers > for one integer. To find the next power in the sequence, look at the > the first number in each row (since that will be the smallest number > in the row), up to limit number of rows. The limit is calculated as > the number of rows that we've already taken one number from, plus one. > This exploits the fact that the row heads are initially ordered. If we > use a number from a row, shift that row down to remove the number > used. > > It does pretty well, but I'd welcome any comments, or even suggestions > of a completely different algorithm (for this little exercise, or > problem 119). Thanks. >
The merging can be done much more simply and efficiently (this is code I wrote when computing squarefree numbers in a blog post<http://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. -Brent
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
