On 04/12/2016 06:49 AM, Nordlöw wrote:
On Thursday, 7 April 2016 at 13:09:22 UTC, Andrei Alexandrescu wrote:
This is a good start but we'd need a more principled attack on the
problem.
Ok, Andrei! Here's a start.
https://github.com/nordlow/phobos-next/blob/master/src/sortn.d
Currently uses Phobos' permutations for complete verification. Its
complexity will of course not work for larger values such as 16.
Supports sorting networks currently up to length 6.
More to come :)
This is great. A few notes:
* Spacing around operators is inconsistent, for Phobos please use the
prevalent style.
* There's a bit too much foreplay, e.g. why introduce names for
everything even when used once (e.g. "alias comp = binaryFun!less;").
* There should be a notion of at what point the networks become too
bulky to be fast - 6-16 may be the limit.
* The arguments in conditionalSwap are a bit awkward, how about:
template conditionalSwap(indexes...)
{
void conditionalSwap(less = "a < b", Range)(Range r) { ... }
}
That way the caller doesn't need to specify less and Range.
* There is a nice peephole optimization you could make. Consider:
r.conditionalSwap!("a < b", less, 0, 1, 1, 2)(r);
which needs to do
if (r[1] < r[0]) r.swapAt(0, 1);
if (r[2] < r[1]) r.swapAt(1, 2);
For types with no elaborate copy/assignment, it's more efficient to use
a "hole"-based approach - assign the first element to a temporary and
then consider it a hole that you fill, then leaving another hole:
if (r[1] < r[0])
if (r[2] < r[0]) r.swapAt(0, 1, 2);
else r.swapAt(0, 1);
else
if (r[2] < r[1]) r.swapAt(1, 2);
with swapAt with three argument having this definition: auto t = r[a];
r[a] = r[b]; r[b] = r[c]; r[c] = t;
i.e. create a temporary (which creates a "hole" in the array) then fill
it leaving another hole etc., until the last hole is filled with the
temporary.
* I found no use for hybridSort, only for sortExactly. Then hybridSort
is a two-liner the user may write.
Could you please take a look at how to handle stability of "equal"
elements?
I'm not sure. Does it suffice to always swap when the lhs index is less
than the rhs index?
Andrei
