Q: sort's key and cmp parameters
Raymond Hettinger
python at rcn.com
Sun Oct 4 22:01:42 EDT 2009
[Paul Rubin]
> Example of list of trees (nested dicts). In practice you could get
> such a list from the simplejson module:
>
> list_of_trees = [{'value':1, 'left':{'value':3,'left':None,'right':None},
> 'right':{'value':7,'left':{'value':5, ...}}},
> {'value':19, 'left':{'value':23', ...}},
> ...
> ]
So, it looks like the relevant comparison values can be stored in
nested lists:
list_of_lists = \
[[1, [3, [], []],
[7, [5, [], []], []]],
[19, [23, [], []],
[]],
]
Here I've used a transformation where a tree is stored as:
[tree['value'], tree['left'], tree['right']]
and the None value indicating an empty tree transformed to:
[]
> > Example comparison function:
>
> def compare(tree1, tree2):
> c = cmp(tree1['value'], tree2['value'])
> if c != 0: return c
> c = compare(tree1['left'], tree2['left'])
> if c != 0: return c
> return compare(tree1['right'], tree2['right])
Hmm, that recursive comparison order looks like how Python
already recursively compares lists. So, perhaps the
lists can be compared directly:
if list_of_lists[0] < list_of_lists[1]:
...
>> Are the trees user defined classes?
>
> Not in general. They might be nested tuples, lists, or dictionaries.
> Or they could come from a non-extensible library-defined class, like
> from cElementTree
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?
Raymond
More information about the Python-list
mailing list