On Mar 28, 8:43 am, Steven D'Aprano <steve
+comp.lang.pyt...@pearwood.info> wrote:
> Thank you for spending the time to get some hard data, but I can't
> replicate your results since you haven't shown your code. Rather than
> attempt to guess what you did and duplicate it, I instead came up with my
> own timing measurements. Results are shown here, my code follows below:
>
> [steve@sylar ~]$ python2.7 sort_test.py
> Comparison function: 12.1256039143
> Key function: 3.51603388786
> Double sort: 2.33165812492
> cmp_to_key: 28.1129128933
>
> By far the best result comes from two calls to sort. Not far off is the
> key function solution. (Admittedly, coming up with a key function for non-
> numeric data would be challenging.) The comparison function, and the
> cmp_to_key solution, are clearly *much* slower.
On Mar 28, 8:43 am, Steven D'Aprano <steve
+comp.lang.pyt...@pearwood.info> wrote:
> Thank you for spending the time to get some hard data, but I can't
> replicate your results since you haven't shown your code. Rather than
> attempt to guess what you did and duplicate it, I instead came up with my
> own timing measurements. Results are shown here, my code follows below:
>
> [steve@sylar ~]$ python2.7 sort_test.py
> Comparison function: 12.1256039143
> Key function: 3.51603388786
> Double sort: 2.33165812492
> cmp_to_key: 28.1129128933
>
> By far the best result comes from two calls to sort. Not far off is the
> key function solution. (Admittedly, coming up with a key function for non-
> numeric data would be challenging.) The comparison function, and the
> cmp_to_key solution, are clearly *much* slower.
There is less here than meets the eye. The cmp-function dispatch in
cmp_to_key() is written in pure Python. Essentially, the timings are
showing the already well-known fact that call forwarding is faster in
C than in pure python.
Each of the O(n log n) comparisons is run through pure Python code
that like this:
def __lt__(self, other):
# mycmp is nested scope variable pointing to
# the user-defined cmp-function
return mycmp(self.obj, other.obj) < 0
I intend to add a C version of cmp_to_key() so that no trips around
the eval-loop are needed. It should be about as efficient as
bound_method dispatch (very fast), leaving the user-supplied cmp-
function as the dominant cost in the handful of cases where the
superfast O(n) key-function approach can't be used for some reason.
The memory overhead should either stay the same or drop slightly
(currently at 14 bytes per element on a 32-bit build and 28 bytes per
element on a 64-bit build).
Also note that running timings on Py2.7 instead of Py3.2 disadvantages
key-functions. In 2.7, key-functions use sortwrapper objects which
were removed in 3.2 (saving memory and reducing dispatch time
considerably). Also, in Py2.7 cmp logic is called even when a key-
function is defined (because key-function logic was wrapped around the
already existing sort with cmp-logic) so you pay the price of both
(i.e. creating a 2-tuple for cmp arguments on every call). In Py3.x
the cmp logic is gone, making the remaining key-function logic even
faster. IOW, key-function logic is way faster and more space
efficient in 3.2.
One of the implications of the last paragraph is that if 2.7 style cmp-
logic were reinstated in 3.3, not only would it clutter the API with
two-ways-to-do-it, it would also disadvantage make the common case
(using key-functions) run much more slowly. In other words, the
performance mavens will have shot themselves (and us) in the foot.
Raymond
--
http://mail.python.org/mailman/listinfo/python-list
