Home Original page

[Python-Dev] decorate-sort-undecorate

Tim Peters tim.one at comcast.net
Tue Oct 14 14:01:49 EDT 2003 
[Fred]
>> We could allocate a second array of PyObject* to mirror the list
>> contents; that would have only the keys.  When two values are
>> switched in the sort, the values in both the key list and the value
>> list can be switched.  When done, we only need to decref the
>> computed keys and free the array of keys.

[Guido]
> I can't tell if that'll work, but if it does, it would be a great
> solution.

I mentioned that before -- doubling the amount of data movement would hurt,
at best by blowing cache all to hell.

There's a related approach, though:  build a distinct vector of custom
objects, each containing:

1. A pointer to the key.
2. The original index, as a C integer.

This is similar to, but smaller than, something mentioned before.

The comparison function for this kind of object redirects to comparing only
the keys -- the integers are ignored during the sort.  Sort this list with
the sorting code exactly as it exists now.

At the end of sorting, the integer members can be used to permute the
original list into order.  This can be done in-place efficiently (not
entirely obvious; Knuth gives at least one algorithm for it).
More information about the Python-Dev mailing list