[Haskell-cafe] Optimization problem
Matthias Fischmann
fis at wiwi.hu-berlin.de
Thu Sep 14 10:12:55 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?
something like this, then?
splitStreams :: Ord a => [(a, b)] -> [(a, [b])]
splitStreams [] = []
splitStreams ((a, b) : t) = (a, b : bs) : splitStreams t'
where
(bs, t') = foldr f ([], []) t
f z@(a', b') (bs, t') = if a' == a
then (b' : bs, t')
else (bs, z : t')
(i guess i should use a strictness '!' for (xs, ys), but i am still
running ghc-6.5, and i don't like the case constructions that much.
does this bite me here? i didn't check, really.)
who can tune this any further?
cheers,
m.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20060914/1999c8ab/attachment.bin
More information about the Haskell-Cafe
mailing list