http://d.puremagic.com/issues/show_bug.cgi?id=5077
Summary: std.algorithm.schwartzSort is slow Product: D Version: D2 Platform: x86 OS/Version: Windows Status: NEW Keywords: performance Severity: enhancement Priority: P2 Component: Phobos AssignedTo: nob...@puremagic.com ReportedBy: bearophile_h...@eml.cc --- Comment #0 from bearophile_h...@eml.cc 2010-10-18 19:08:43 PDT --- Here are few benchmarks that show that schwartzSort() is much slower than sort(). (While in Python the usage of the 'key' argumement, analogous to a Schwartz sort, usually leads to faster code. But Python and D have very different compilation structure, so comparisons are hazardous at best.) Timings 2.1 GHz CPU, , DATA_LEN=1_000_000, best of 4, seconds: none: 0.3 sort: 4.1 sort: 3.4 (alternative) schwartz: 17.9 I have no idea why the "alternative" sort is faster than the normal sort, I was expecting the opposite. ----------------------------------------- import std.stdio: writeln; import std.algorithm: schwartzSort, sort; import std.random: Random, uniform; import std.typecons: Tuple; enum SortType { none, sort, schwartz } enum DATA_LEN = 1_000_000; enum sort_type = SortType.sort; alias Tuple!(double, "x", double, "y") P; void main() { auto data = new P[DATA_LEN]; auto rnd = Random(1); foreach (ref el; data) { double x = uniform(0.0, 1.0, rnd); double y = uniform(0.0, 1.0, rnd); el = P(x, y); } if (data.length < 50) writeln(data); static if (sort_type == SortType.schwartz) { schwartzSort!((p) { return p.y; })(data); schwartzSort!((p) { return p.x; })(data); schwartzSort!((p) { return p.y; })(data); } static if (sort_type == SortType.sort) { sort!q{ a.y < b.y }(data); sort!q{ a.x < b.x }(data); sort!q{ a.y < b.y }(data); /* // alternative sort!((P a, P b) { return a.y < b.y; })(data); sort!((P a, P b) { return a.x < b.x; })(data); sort!((P a, P b) { return a.y < b.y; })(data); */ } if (data.length < 50) writeln(data); } -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------