getKSmallest k list = take k (sort list)
getKSmallest k = take k . sort
(Algorithms aside, the full sort of 10M numbers, apparently using an underlying C implementation, looks stunishingly slow: Given at most 240M comparisons for merge-sorting the array, taking 10s would mean at throughput only 24M items per sec, bad memory access pattern at play maybe?)
Some benchmarks might convince me :)
GHCi, version 6.12.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Loading package ffi-1.0 ... linking ... done. Prelude> :m Data.List -- for sort function Prelude Data.List> :se +s -- to display timings.
Prelude Data.List> last $ sort [1..2^20] 1048576 (1.34 secs, 544634924 bytes) Prelude Data.List> last $ sort [1..2^21] 2097152 (2.84 secs, 1125744400 bytes) Prelude Data.List> last $ sort [1..2^22] 4194304 (5.51 secs, 2325062504 bytes) Prelude Data.List> 1.34/(2^20)/20 6.389617919921875e-8 (0.02 secs, 1576728 bytes) Prelude Data.List> 2.84/(2^21)/21 6.44865490141369e-8 (0.00 secs, 1578108 bytes) Prelude Data.List> 5.51/(2^22)/22 5.971301685680042e-8 (0.00 secs, 1572220 bytes)
Looks like it really sorts, even strictly ascending sequence (2^22 time problems could be attributed to GC or something).
Let us take first N from sorted list:
Prelude Data.List> sum $ take (2^1) $ sort [1..2^22] 3 (2.25 secs, 760208692 bytes) Prelude Data.List> sum $ take (2^2) $ sort [1..2^22] 10 (2.50 secs, 760292356 bytes) Prelude Data.List> sum $ take (2^3) $ sort [1..2^22] 36 (2.25 secs, 759678188 bytes) Prelude Data.List> sum $ take (2^4) $ sort [1..2^22] 136 (2.51 secs, 760209208 bytes) Prelude Data.List> sum $ take (2^5) $ sort [1..2^22] 528 (2.36 secs, 759678236 bytes) Prelude Data.List> sum $ take (2^6) $ sort [1..2^22] 2080 (2.31 secs, 759682904 bytes)
I don't know why this looks almost constant. But it is!
I expected to be able to show O(nlogk), but it performed even better. ;)