[Haskell-cafe] k-minima in Haskell
Yitzchak Gale
gale at sefer.org
Thu Apr 12 14:23:23 EDT 2007
\begin{code}
kmin :: Ord a => Int -> [a] -> [Int]
kmin k x = map snd $ Set.toList $ foldl' insertIfSmall (Set.fromList h) t
where
(h, t) = splitAt k $ zip x [0..]
insertIfSmall :: Ord a => Set.Set a -> a -> Set.Set a
insertIfSmall s e
| e < mx = Set.insert e s'
| otherwise = s
where
(mx, s') = Set.deleteFindMax s
\end{code}
This gives O(log k * (n + k)) execution in constant memory.
If you need the result indices to be in order, you can put in
a sort at the end without changing the complexity.
This could be improved by a significant constant factor
by using a priority queue instead of Set. Any Edison people
out there?
Regards,
Yitz
More information about the Haskell-Cafe
mailing list