[Issue 5077] std.algorithm.schwartzSort is slow

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=5077


Andrei Alexandrescu <andrei at metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andrei at metalanguage.com


--- Comment #2 from Andrei Alexandrescu <andrei at metalanguage.com> 2010-10-19 06:37:48 PDT ---
This is a misunderstanding of Schwartz sort is supposed to do. D's equivalent
of Python's key argument is not Schwartz sort, but instead:

        sort!q{p.x < p.y}(data);

i.e. the keys are not copied but instead a projection is used for the
comparison. That's your "alt" sort. Schwartz sort is meant for usage when the
key computation (in this case a simple member access) is too expensive to be
done more than once. To avoid that, schwartzSort creates an array of the
computed keys and then sorts the keys and the original arrays in lockstep. It
is expected that schwartzSort is considerably slower than sort for cheap keys.
It is also expected that "alt" sort is the best of the breed because it has the
fastest key computation.

I'm leaving this open in case you have new experiments that do reveal a
problem. Otherwise, feel free to close it.

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