Re: Lazy sort
On Friday, 11 September 2015 at 12:23:52 UTC, ixid wrote: Yes, I was reading about heapsort. I was only thinking about the usability POV (I mean isn't reduced pretty much an eager operation that accepts a lazy input? Why can't sort do that?) but it could also offer some performance improvement if you only use a part of the sorted array. I think there is something called "partial sort" in Phobos, but "lazy" sorting is the same as a priority queue. You need to look at all elements before finding the largest one, that's why you cannot turn sort into a plain generator (or lazy range as some may call it).
Re: Lazy sort
On Friday, 11 September 2015 at 11:08:29 UTC, Ola Fosheim Grøstad wrote: On Friday, 11 September 2015 at 10:41:16 UTC, ixid wrote: Does sort have to be eager or would it be possible to have a lazy version? It's messy to always have to use array and leap in and out of lazy operations within a UFCS chain. Surely as many functions as possible should be optionally lazy. https://en.wikipedia.org/wiki/Priority_queue Yes, I was reading about heapsort. I was only thinking about the usability POV (I mean isn't reduced pretty much an eager operation that accepts a lazy input? Why can't sort do that?) but it could also offer some performance improvement if you only use a part of the sorted array.
Re: Lazy sort
On Friday, 11 September 2015 at 10:41:16 UTC, ixid wrote: Does sort have to be eager or would it be possible to have a lazy version? It's messy to always have to use array and leap in and out of lazy operations within a UFCS chain. Surely as many functions as possible should be optionally lazy. https://en.wikipedia.org/wiki/Priority_queue
Re: Lazy sort
On Friday, 11 September 2015 at 10:41:16 UTC, ixid wrote: Does sort have to be eager or would it be possible to have a lazy version? It's messy to always have to use array and leap in and out of lazy operations within a UFCS chain. Surely as many functions as possible should be optionally lazy. Are you the lazy sort? ;) Sorry, I couldn't resist the pun.
Re: Lazy sort
On Friday, 11 September 2015 at 10:41:16 UTC, ixid wrote: Does sort have to be eager or would it be possible to have a lazy version? It's messy to always have to use array and leap in and out of lazy operations within a UFCS chain. Surely as many functions as possible should be optionally lazy. Wouldn't that mean removing min or max lazily?
Lazy sort
Does sort have to be eager or would it be possible to have a lazy version? It's messy to always have to use array and leap in and out of lazy operations within a UFCS chain. Surely as many functions as possible should be optionally lazy.
Re: Lazy sort?
On 10/02/2011 09:47 PM, bearophile wrote: Sometimes in my code I have to find the first few smaller (or bigger) items of an array, I don't know how many I will need, but I know in general I will need only few of them, much less than the whole array. Turnign the array into an heap is slow if I need only few items, and I can't use std.algorithm.partialSort because I don't know how many items I will need. So I have written this very simple LazySort range, based on partialSort (note: it is lazy in its output, but its input can't be lazy): http://ideone.com/iEPO6 I have not done benchmarks on it yet. Do you like it? Is something like it generally useful? Bye, bearophile I like the feature, but there are more efficient ways to do that (your implementation is asymptotically optimal though).
Lazy sort?
Sometimes in my code I have to find the first few smaller (or bigger) items of an array, I don't know how many I will need, but I know in general I will need only few of them, much less than the whole array. Turnign the array into an heap is slow if I need only few items, and I can't use std.algorithm.partialSort because I don't know how many items I will need. So I have written this very simple LazySort range, based on partialSort (note: it is lazy in its output, but its input can't be lazy): http://ideone.com/iEPO6 I have not done benchmarks on it yet. Do you like it? Is something like it generally useful? Bye, bearophile
