3 ms·

When you have lazy evaluation in your tools, finding K extremal elements in list will be one-liner: getKSmallest k list = take k (sort list) or even shorte

by thesz 15y ago

When you have lazy evaluation in your tools, finding K extremal elements in list will be one-liner: getKSmallest k list = take k (sort list) or even shorter in point-free notation: getKSmallest k = take k . sort http://en.wikipedia.org/wiki/Selection_algorithm#Language_support http://en.wikipedia.org/wiki/Selection_algorithm#Language_su...

CJefferson 15y ago
Does this really achieve O(n.k) for small k? I'm not sure I believe sort can be that lazy, without being deficient when used in a non-lazy context. Some benchmarks might convince me :)
- thesz 15y ago
  Let us convince ourselves that sort sorts: GHCi, version 6.12.1: http://www.haskell.org/ghc/ 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. ;)
kaiwetzel 15y ago
Interesting blog post about how this could be done in Haskell using a suitable mergesort (or quicksort): http://apfelmus.nfshost.com/articles/quicksearch.html http://apfelmus.nfshost.com/articles/quicksearch.html (pointed out in a similar discussion some time ago). Having used Haskell in university only, articles like this really make me want to revisit the language. (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?)

by thesz 15y ago

CJefferson 15y ago

Does this really achieve O(n.k) for small k? I'm not sure I believe sort can be that lazy, without being deficient when used in a non-lazy context. Some benchmarks might convince me :)

thesz 15y ago
Let us convince ourselves that sort sorts: GHCi, version 6.12.1: http://www.haskell.org/ghc/ 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. ;)

kaiwetzel 15y ago

Interesting blog post about how this could be done in Haskell using a suitable mergesort (or quicksort): http://apfelmus.nfshost.com/articles/quicksearch.html http://apfelmus.nfshost.com/articles/quicksearch.html (pointed out in a similar discussion some time ago). Having used Haskell in university only, articles like this really make me want to revisit the language. (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?)