[Issue 5078] New: Some possible improvements for std.algorithm.schwartzSort()
d-bugmail at puremagic.com
d-bugmail at puremagic.com
Mon Oct 18 19:11:44 PDT 2010
http://d.puremagic.com/issues/show_bug.cgi?id=5078
Summary: Some possible improvements for
std.algorithm.schwartzSort()
Product: D
Version: D2
Platform: All
OS/Version: All
Status: NEW
Keywords: patch
Severity: enhancement
Priority: P2
Component: Phobos
AssignedTo: nobody at puremagic.com
ReportedBy: bearophile_hugs at eml.cc
--- Comment #0 from bearophile_hugs at eml.cc 2010-10-18 19:11:06 PDT ---
Here I have a (hopefully) improved version of schwartzSort (code not tested
much). It contains three changes:
1) I have removed the fields here:
return binaryFun!(less)(a[0], b[0]);
2) I have added a transformFunc, so schwartzSort() may accept a short string
too as transform, as sort/map/filter do, like: schwartzSort!q{ a.y }(data)
3) When the input data is very small it's a waste of time to allocate a
temporary array on the GC heap, so I have used alloca().
So this code assumes that the space allocated by alloca() gets freed only at
the end of the function, this is a constraint that I think D docs don't state,
see bug 3822
See also bug 5077
import std.algorithm: SwapStrategy, zip, sort, binaryFun, unaryFun;
import std.range: isRandomAccessRange, hasLength, front;
import std.c.stdlib: alloca;
import std.array: array;
void schwartzSort(alias transform, alias less = "a < b",
SwapStrategy ss = SwapStrategy.unstable, Range)(Range r)
if (isRandomAccessRange!(Range) && hasLength!(Range))
{
enum size_t MAX_SIZE = 512;
alias unaryFun!transform transformFunc;
alias typeof(transformFunc(r.front)) XformType;
XformType[] xform;
if (r.length * XformType.sizeof > MAX_SIZE)
{
xform = new XformType[r.length];
}
else
{
xform = (cast(XformType*)alloca(r.length * XformType.sizeof))[0 ..
r.length];
}
foreach (i, e; r)
{
xform[i] = transformFunc(e);
}
auto z = zip(xform, r);
alias typeof(z.front()) ProxyType;
bool myLess(ProxyType a, ProxyType b)
{
return binaryFun!(less)(a[0], b[0]);
}
sort!(myLess, ss)(z);
}
// demo code --------------------------
import std.typecons: Tuple;
import std.stdio: writeln;
alias Tuple!(int, "x", int, "y") P;
void main() {
P[] data = [P(1,4), P(2,3), P(3,1), P(4,0)];
writeln(data);
// schwartzSort!((p) { return p.y; })(data);
schwartzSort!q{ a.y }(data);
writeln(data);
}
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
More information about the Digitalmars-d-bugs
mailing list