[Issue 6787] Lazy sort in Phobos?

[d-bugmail at puremagic.com]

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



--- Comment #3 from Andrei Alexandrescu <andrei at 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: -------