[Patches] [ python-Patches-823292 ] Optional list.sort() args for
DSU pattern and reverse
SourceForge.net
noreply at sourceforge.net
Wed Oct 15 13:55:24 EDT 2003
Patches item #823292, was opened at 2003-10-14 03:53
Message generated for change (Comment added) made by rhettinger
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=823292&group_id=5470
Category: Core (C code)
Group: Python 2.4
Status: Open
Resolution: None
Priority: 5
Submitted By: Raymond Hettinger (rhettinger)
Assigned to: Nobody/Anonymous (nobody)
Summary: Optional list.sort() args for DSU pattern and reverse
Initial Comment:
Here is a first draft patch as discussed on python-dev.
Docs and tests to follow.
The keywords are: cmpfunc, key, reverse
This patch passes regression tests and a minimal set of
basic functionality tests which need to be expanded
considerably. I'll need to go back over this one in
more detail to check:
* Was the code inserted in the right place with respect
to the existing anti-mutation code.
* Is the strategy of decorating in-place to aggressive?
Decoration consists of *replacing* each value x with
(x, key(x)).
* Verify reference counting and error handling.
----------------------------------------------------------------------
>Comment By: Raymond Hettinger (rhettinger)
Date: 2003-10-15 12:55
Message:
Logged In: YES
user_id=80475
Updated the patch to make reversed sorts stable.
The python version of the code is:
class sortwrapper:
def __init__(self, key, value):
self.key = key
self.value = value
def __cmp__(self, other):
return cmp(self.key, other.key)
def getvalue(self):
return self.value
class cmpwrapper:
def __init__(self, cmpfunc):
self.cmpfunc = cmpfunc
def __call__(self, x, y):
return self.cmpfunc(x.key, y.key)
def sort(self, cmp=None, key=None, reverse=None):
if cmp is not None and key is not None:
cmp = cmpwrapper(cmp)
if key is not None:
self[:] = [sortwrapper(key(x), x) for x in self]
if reverse is not None:
self.reverse()
self.sort(cmp)
if key is not None:
self[:] = [x.getvalue() for x in self]
if reverse is not None:
self.reverse()
----------------------------------------------------------------------
Comment By: Raymond Hettinger (rhettinger)
Date: 2003-10-14 23:51
Message:
Logged In: YES
user_id=80475
Added a cmp function wrapper so that the key will be
unwrapped for a user specified cmp function applied to
wrapped keys.
----------------------------------------------------------------------
Comment By: Raymond Hettinger (rhettinger)
Date: 2003-10-14 21:35
Message:
Logged In: YES
user_id=80475
Here is a second patch including unittests and docs.
* The optional keywords arguments are: cmp, key, reverse.
* The key function triggers a DSU step with a wrapper object
that holds the full record, but returns only the key for a
comparision. This is fast and doesn't change the underlying
stability characteristics of the sort. (I think this was
Neil's idea -- and it works well.)
* If the key function is not specified, no wrapping occurs
so that sort performance is not affected.
----------------------------------------------------------------------
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=823292&group_id=5470
More information about the Patches
mailing list