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: nob...@puremagic.com ReportedBy: bearophile_h...@eml.cc --- Comment #0 from bearophile_h...@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: -------