--- Comment #3 from 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:

>From the docs:

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:
------- You are receiving this mail because: -------

Reply via email to