digitalmars.D.bugs - [Issue 5078] New: Some possible improvements for std.algorithm.schwartzSort()
- d-bugmail puremagic.com (74/74) Oct 18 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5078
- d-bugmail puremagic.com (9/9) Oct 19 2010 http://d.puremagic.com/issues/show_bug.cgi?id=5078
- d-bugmail puremagic.com (6/6) Feb 26 2013 http://d.puremagic.com/issues/show_bug.cgi?id=5078
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
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
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