Summary: Lazy sort in Phobos?
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos

--- Comment #0 from 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));

    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:
------- You are receiving this mail because: -------

Reply via email to