[Haskell-cafe] Optimization problem

Ketil Malde ketil+haskell at ii.uib.no
Thu Sep 14 04:52:37 EDT 2006


Magnus Jonsson <magnus at smartelectronix.com> writes:

> splitStreams::Ord a=>[(a,b)]->[(a,[b])]

>> splitStreams [(3,x),(1,y),(3,z),(2,w)]
> [(3,[x,z]),(1,[y]),(2,[w])]

  [...]

> 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?

I guess it should be possible to use a quicksort-like algorithm,
splitting the stream into three streams with keys less than, equal,
and greater than the first element, and recurse on the less/equal
streams? 

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants



More information about the Haskell-Cafe mailing list