Q: sort's key and cmp parameters

Raymond Hettinger python at rcn.com
Sat Oct 3 08:25:59 CEST 2009


[Paul Rubin]
> The idea was that you have a list of trees that you want to sort, and
> an ordering relation between trees:
>
>    def gt(tree1, tree2): ...

Are the trees user defined classes?  Can the gt() function be added
incorporated as __lt__ method so that you can just run a plain sort:

    sort(list_of_trees)

Is the recursive search order something you can turn into a straight
sequence:

    sort(list_of_trees, key=flattener)

IOW, if there is an ordering relation between the trees, why can't
it be either part of the tree API or collapsable into a list of
successive nodes to be compared.

>From the sound of it, the trees are static during the sort and
would get a nice O(n log n) --> O(n) speed-up if a key function
were allowed to flatten them in a single pass.


Raymond



More information about the Python-list mailing list