Q: sort's key and cmp parameters
Mon Oct 5 12:10:01 CEST 2009
Raymond Hettinger <python at rcn.com> writes:
> So, it looks like the relevant comparison values can be stored in
> nested lists:
> list_of_lists = \
> [[1, [3, , ],
> [7, [5, , ], ]],
> [19, [23, , ],
Now you've copied all the data out of the original tree, which is even
worse than putting a class wrapper around it. The comparison remains
(asymptotically) as expensive as before, too.
> Are there any of these trees that cannot be transformed
> (by a key function) into an equivalent nested list of lists
> and values so that the trees can be directly compared to one another
> using Python's normal built-in recursive comparison order for lists?
I think so. Say you want to change the numeric comparisons so that
even numbers always sort before odd numbers, ie.
-4 < -2 < 0 < 2 < 4 < ... < -999 < ... -1 < 1 < 3 ...
I don't think there is a way to re-encode the numbers so they
can be compared with direct integer comparison. Even if there is,
I think there are reasonable orderings on the trees themselves that
can't possibly be embedded in the standard python comparison order.
I might be able to construct an example using ordinal diagrams from
More information about the Python-list