Am Montag 04 Januar 2010 02:35:04 schrieb Peter Green:
I am using the external-sort package to sort my output in the program below. I made this choice because my output dataset [[Int]] can be large (e.g. >3M items, each [Int]).
What my program does:
(1) Reads in a file containing 'compressed lists' which look like so:
8+12,11,7+13,10 1+2+3,1+9,3+6,4 . .
One compressed list per line. These compressed lists are parsed to become [[[Int]]]
[[[8,12],[11],[7,13],[10]], [[1,2,3],[1,9],[3,6],[4]], . . ]
Generally files of compressed lists have lengths of ~10,000 lines.
(2) Compressed lists are exploded to [[int]] via concatMap Cartesian Product over [[[Int]]], so we end up with [[Int]]
[[8, 11, 7, 10], [8, 11, 13, 10], [12, 11, 7, 10], [12, 11, 13, 10], [1, 1, 3, 4], . . [3, 9, 6, 4]]
I have a different idea. You want to consume the data in order, don't you? You can interleave sorting and exploding then: 1. read in data (~10,000 lists of lists. In your examples, each line contains a list of four short lists, the nested lists containing 1-3 elements. I hope that's not too far from reality.) 2. map (\l -> ([],l)) to get [([],[[8,12],[11],[7,13],[10]]), ([],[[1,2,3],[1,9],[3,6], [4]]), ... ] 3. split first sublists of second component and append to the first component (empty list) concatMap (\(acc,(toSplit:rest)) -> [(acc ++ [x],rest) | x <- toSplit]) [([],[[8,12],[11],[7,13],[10]]), ([],[[1,2,3],[1,9],[3,6],[4]]), . . ] ~> [([8],[[11],[7,13],[10]]), ([12],[[11],[7,13],[10]]), ([1],[[1,9],[3,6],[4]]), ([2],[[1,9],[3,6],[4]]), ([3],[[1,9],[3,6],[4]]), . . ] A list of ~30,000(?) ([Int],[[Int]]) pairs 4. sortBy (comparing fst) {-# import Data.Ord (comparing) #} 5. groupBy ((==) `on` fst) {-# import Data.Function (on) #-} You now have something like [ [([1],[[1,9],[3,6],[4]]), ([1],[[?],[?],[?]]), . . ], [([2],[[1,9],[3,6],[4]]), ([2],[[?],[?],[?]]), . . ], . . [([131],[[?],[?],[?]])], ([131],[?]), . . ] ] 6. If necessary, repeat 3. to 5. on each of the groups to get [ [ [([1,1],[[3,6],[4]]), ([1,1],[[?],[?]]), . . ], [([1,2],[[?],[?]]), ([1,2],[[?],[?]]), . . ], . . ] ] concat to get [ [([1,1],...), . . ], [([1,2],...), . . ], . . ] , iterate until exploding in step 8. produces something manageable. 7. map (\g@((h,_):_) -> (h, map snd g)) You now have something of type [([Int],[[[Int]]])], [([1],[ [[1,9],[3,6],[4]], [[?],[?],[?]],...]), ([2],[[[1,9],[3,6],[4]],[[?],[?],[?]],...]), . . ([131],[[[?],[?],[?]],...]) ] or [([1,1],[ [[3,6],[4]], [[?],[?]],...]), ([1,2],[ [[?],[?]], [[?],[?]],...]), . . ] 8. explode second components in each of the pairs, sort, append to first component, consume. Thanks to laziness, the [[[Int]]] of the second group will only be exploded after the first group has been consumed. One caveat: if the lines do not always contain lists of equal length, you must not repeat steps 3.-6. more often than the shortest length or modify the function in 3. to handle that, e.g. partialExplode (acc,toSplit:rest) = [(acc + [x],rest) | x <- toSplit] partialExplode (acc,[]) = [(acc,[])]
-- Cartesian Product over a List of Lists -- Http://www.cs.nott.ac.uk/~gmh/sudoku.lhs -- cp [[1,2],[3],[4,5,6]] --> [[1,3,4],[1,3,5],[1,3,6],[2,3,4],[2,3,5], [2,3,6]] cp :: [[a]] -> [[a]] cp [] = [[]] cp (xs:xss) = [y:ys | y <- xs, ys <- cp xss]
change that to cp (xs:xss) = [y:ys | ys <- cp xss, y <- xs] to get something more memory friendly.