3 ms·
> Yeah but at least it's lazy! ;) ;) Yeah, except that the overhead of lazy is often (usually?) more than the "overhead" of doing the whole computation eagerl
by mpweiher 10y ago
> Yeah but at least it's lazy! ;)
;) Yeah, except that the overhead of lazy is often (usually?) more than the "overhead" of doing the whole computation eagerly.
> just sort-enough to give you these 4 sorted
And how is that going to work in a sort? The 4 first elements can be located anywhere and have to brought into position.
There are "first k of n" algorithms, but these are (last I checked) quite different from generic sorting algorithms, and I doubt that a lazy sort in Haskell actually magically turns into one of those algorithms.
Happy to be proved wrong!
- fmap 10y agoWell, you do get an (expected time) asymptotically efficient algorithm for sorting the first k elements of an array by running quicksort without recursing on the last n-k elements. This is what you get in Haskell with "take k (sort xs)". But, as you mentioned the constant factors involved are ridiculously high and this is not going to give you a practical solution.