http://d.puremagic.com/issues/show_bug.cgi?id=6787

           Summary: Lazy sort in Phobos?
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@eml.cc 2011-10-07 15:53:29 PDT ---
Sometimes in my code I have to find the first few smallest (or biggest) items of an array, I don't know how many I will need of them, but I know in general I will need only few of them, much less than the whole array.

Turning the array into an heap is a slow operation if I will only need few items, and I can't use std.algorithm.partialSort because I don't know the number of items I will need.

So I have created this very simple LazySort range, based on partialSort (works
with DMD 2.056head):


import std.stdio, std.algorithm, std.random, std.array, std.range, std.traits;

// Missing still: less and SwapStrategy template arguments.
struct LazySort(Range) if (isRandomAccessRange!Range) {
    Range data;
    private size_t idx, idxSorted;

    bool empty() { return idx >= data.length; }

    ForeachType!Range front() {
        if (idx >= idxSorted) {
            immutable oldIdxSorted = idxSorted;
            idxSorted = min(data.length, idxSorted ? (idxSorted * 2) : 1);
            partialSort(data[oldIdxSorted .. $], idxSorted - oldIdxSorted);
        }
        return data[idx];
    }

    void popFront() { idx++; }
}

void main() {
    auto A = array(iota(25));
    randomShuffle(A);
    writeln(A);

    foreach (x; LazySort!(int[])(A))
        write(x, " ");
}



I have not done benchmarks on it yet. This code seems to work, but it is not efficient, it's just to show the semantics of the idea. A better implementation is welcome.

I think a lazy sort will be useful in Phobos. Timon Gehr seems to appreciate the idea.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6787


Andrei Alexandrescu <andrei@metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andrei@metalanguage.com


--- Comment #1 from Andrei Alexandrescu <andrei@metalanguage.com> 2011-10-07 15:58:21 PDT ---
The canonical solution uses a heap. Creating a heap is cheap and quickly amortized over only a few pops. An input range that creates a heap and then yields one element at a time would be a better idea.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6787



--- Comment #2 from bearophile_hugs@eml.cc 2011-10-07 16:21:35 PDT ---
(In reply to comment #1)
> The canonical solution uses a heap. Creating a heap is cheap and quickly amortized over only a few pops. An input range that creates a heap and then yields one element at a time would be a better idea.

If benchmarks show that a range that heapifies the input array is about as efficient as a tailored lazy sorting solution for about 4 to 10 requested max/min items, then I am OK with this idea :-)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=6787



--- Comment #3 from Andrei Alexandrescu <andrei@metalanguage.com> 2011-10-07 17:17:20 PDT ---
(In reply to comment #2)
> (In reply to comment #1)
> > The canonical solution uses a heap. Creating a heap is cheap and quickly amortized over only a few pops. An input range that creates a heap and then yields one element at a time would be a better idea.
> 
> If benchmarks show that a range that heapifies the input array is about as efficient as a tailored lazy sorting solution for about 4 to 10 requested max/min items, then I am OK with this idea :-)

This is odd at a few levels. First, you opened this report. So it's not you who's supposed to be OK, it's the rest of us. You have the burden of proof. Second, there's no need for benchmarking anything - simple complexity analysis shows that partialSort does O(n) log(n-k) at each step, which pretty much makes it bankrupt compared to the heap approach.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------