www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Lazy sort?

reply bearophile <bearophileHUGS lycos.com> writes:
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
Oct 02 2011
parent Timon Gehr <timon.gehr gmx.ch> writes:
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).
Oct 02 2011