[Issue 5077] std.algorithm.schwartzSort is slow

[d-bugmail at puremagic.com]

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



--- Comment #3 from bearophile_hugs at eml.cc 2010-10-22 04:52:28 PDT ---
(In reply to comment #2)

Thank you for your answers.

> 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.

In that D benchmark there are 3 kinds of sort, two use the normal sort() the
other uses schwartzSort.

The "alternative" version is still a normal sort. The only difference is that
it uses a delegate, as you see from the code:
(P a, P b) { return a.y < b.y; }

instead of a "template lambda":
q{ a.y < b.y }


Regarding Python, years ago Python2 used to have just a sort like this, with
the "cmp" argument:
s.sort(cmp)

>From the docs:
http://docs.python.org/library/stdtypes.html#mutable-sequence-types

cmp specifies a custom comparison function of two arguments (list items) which
should return a negative, zero or positive number depending on whether the
first argument is considered smaller than, equal to, or larger than the second
argument: cmp=lambda x,y: cmp(x.lower(), y.lower()). The default value is None.


Recent Python2 versions use have a more complex sort signature:

s.sort([cmp[, key[, reverse]]])

Where beside the "cmp" that's still present, there is the "key" function:

key specifies a function of one argument that is used to extract a comparison
key from each list element: key=str.lower. The default value is None.


Python3 has removed the cmp argument.

In the bug report I was referring to "key" that's a function that takes a
single argument and return a single transformed item. So in Python if you use
the "key" you are performing a Schwartz sort.

C source code of CPython is available online, if you use "key" CPython builds a
temporary array of the transformed data, that is used to sort the true data.


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

The performance of schwartzSort is too much low, so in my opinion the bug
report needs to be open still.

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