www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 5078] New: Some possible improvements for std.algorithm.schwartzSort()

reply d-bugmail puremagic.com writes:
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 puremagic.com
        ReportedBy: bearophile_hugs eml.cc



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: -------
Oct 18 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5078


Andrei Alexandrescu <andrei metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |andrei metalanguage.com


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 19 2010
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5078




PST ---
Bearophile, could you please paste this as a pull request. Thanks!

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 26 2013