3 ms·

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 benchm

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. ;)

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. ;)