Python 3.0, rich comparisons and sorting order

Andrew Dalke adalke at mindspring.com
Tue Sep 21 22:02:03 CEST 2004


Phil Frost wrote:

> On Tue, Sep 21, 2004 at 05:42:35PM +0000, Steven Bethard wrote:
> 
>>Phil Frost <indigo <at> bitglue.com> writes:
>>
>>>On Tue, Sep 21, 2004 at 05:24:48PM +0000, I wrote:
>>>
>>>>Could you give an example of a list that you'd like to do this to?  I'm 
>>>>still having trouble imagining a list of disparate types that I call sort 
>>>>on...
>>>
>>>What about binary trees? Currently it's possible to implement a binary
>>>tree that is as general as a dict, but restricting comparisons to like
>>>types would make that impossible.
>>
>>Is there a good use case for binary trees with incompatible types at the nodes?
>>
>>I'm not sure I follow your comparison here anyway, since you can't sort a 
>>dict...  Could you clarify?
>>
>>Thanks,
>>
>>STeve
> 
> 
> That's the point. Dicts can't be sorted, but binary trees *must* be.
> There are at least two good reasons to use a binary tree:
> 
> - you need a mapping that is sorted by key
> - the worst case O(n) complexity of a hash table is not acceptable
> 
> The right question here is, "is there a reason for mappings with
> heterogeneous key types?" It's not something that I do often, but it's
> something that's important to have. Dynamic typing is a good thing.



More information about the Python-list mailing list