DSU pattern (was Re: Trouble sorting lists (unicode/locale related?))

[Peter Otten]

Alex Martelli wrote:

>> Everytime that someone posts a naive list.sort(compare), the DSU pattern
>> is proposed to improve execution speed.
>> 
>> So maybe it's about time to change the sort() method to support a second
>> argument
>> 
>> list.sort(compare=None, mapping=None)
>> 
>> that, if provided, would perform the DSU magic. Or was that already
>> proposed and rejected?
> 
> I have not seen this proposed before, and I'm not very clear on what
> the "compare" and "mapping" arguments are supposed to be in order to
> let you specify any DSU.  Basically it seems you would need two
> callables, "decorate" to be called with each item in the list (to
> return for each item the decorated tuple) and "undecorate" to be
> called with each decorated tuple after the sort (to return the item
> for the result).  How do you turn that into "compare" and "mapping"?

My first idea was to add a .dsu(mapping) where the tuples in the decoration
phase would be generated as (mapping(item), item). 
But I would rather enhance the already-existing sort() to provide for both
the traditional and the dsu sorting. Then you have to detect if the
function passed to sort(fun) takes one or two arguments, which is not
reliable when default values come into play. So I resorted to named
arguments. Didn't make it any clearer?

So here is a pure python prototype to shed some light on the matter:

class dsu(list):
    def sort(self, compare=None, mapping=None):
        if mapping:
            decorated = [(mapping(i), i) for i in self]
            decorated.sort()
            self[:] = [i[1] for i in decorated]
        else:
            list.sort(self, compare)

sample = dsu("ab Aa AC d e f".split())

# "traditional" sort
sample.sort(lambda s, t: -cmp(s, t))
print sample

# decorate-sort-undecorate
sample.sort(mapping=lambda s: s.lower())
print sample


Peter