October 02, 2011 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 |
October 02, 2011 Re: Lazy sort? | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | 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).
|
Copyright © 1999-2021 by the D Language Foundation