std.partition is fucked
Andrei Alexandrescu
SeeWebsiteForEmail at erdani.org
Wed May 13 08:52:12 PDT 2009
superdan wrote:
> dis must be related to bug 2966 sayin' std.sort is fucked. problem
> must be with std.partition. i tested and unstable partition is 10
> times slower than stable. should be faster akshully. so looked into
> tat and found in da loop for std.partition unstable and found da
> range r1 is fucked.
That is correct. Where were you yesterday when I was looking for this?
:o) The fixed loop is:
// Inspired from www.stepanovpapers.com/PAM3-partition_notes.pdf,
// section "Bidirectional Partition Algorithm (Hoare)"
auto result = r;
for (;;)
{
for (;;)
{
if (r.empty) return result;
if (!pred(r.front)) break;
r.popFront;
result.popFront;
}
// found the left bound
assert(!r.empty);
for (;;)
{
if (pred(r.back)) break;
r.popBack;
if (r.empty) return result;
}
// found the right bound, swap & make progress
swap(r.front, r.back);
r.popFront;
result.popFront;
r.popBack;
}
Note how the left edge of result follows the left edge of r, but the
right edge stays put because partition() returns the right-hand-side
range. r shrinks from both ends to exhaustion.
The performance of std.sort is back to normal - still slower than the
built-in sort (but not by orders of magnitude), probably because bumping
ranges is at a disadvantage.
Thanks David and superdan.
Andrei
More information about the Digitalmars-d
mailing list