[Haskell-cafe] Optimization problem
Magnus Jonsson
magnus at smartelectronix.com
Wed Sep 13 19:10:59 EDT 2006
Dear Haskell Cafe,
When programming the other day I ran into this problem. What I want to do
is a function that would work like this:
splitStreams::Ord a=>[(a,b)]->[(a,[b])]
> splitStreams [(3,x),(1,y),(3,z),(2,w)]
[(3,[x,z]),(1,[y]),(2,[w])]
I don't care about the order that the pairs are output, so the answer
could just as well be [(2,[w],(3,[x,z]),(1,[y])]. However I do care about
the order of the xyzw:s, so (3,[z,x]) could not be part of the solution in
this example.
Furthermore it should work on infinite lists. It can't eat the whole
list before producing any output.
Now, it's not too hard to come up with an inefficient solution that
traverses the input list multiple times. For example a sieving solution:
import Data.List
splitStreams [] = []
splitStreams ((channel,msg):rest) =
let (myMsgs,otherMsgs) =
partition (\(c,_)->c==channel) rest
in (channel, msg : map snd myMsgs) : splitStreams otherMsgs
I'm afraid this algorithm is O(n*m) time in the worst case, where n is the
length of the input list, and m is the number of unique channels.
But is there any way to write it such that each element is touched only
once? Or at least an O(n*log(m)) algorithm?
Any takers?
/ Magnus Jonsson
More information about the Haskell-Cafe
mailing list