sorting with expensive compares?

Kent Johnson kent at kentsjohnson.com
Fri Dec 23 14:12:39 CET 2005


bonono at gmail.com wrote:
> Dan Stromberg wrote:
>>Python appears to have a good sort method, but when sorting array elements
>>that are very large, and hence have very expensive compares, is there some
>>sort of already-available sort function that will merge like elements into
>>a chain, so that they won't have to be recompared as many times?
> 
> Sounds like DSU time.
> 
> [a] -> [ (hash(a), a) ]

This won't work - elements with different hashes will sort by hash and 
elements with the same hash will still be compared which is exactly what 
the OP is trying to avoid.

If there is some function of the arrays which sorts in the same order as 
the natural comparison then that function can be used as a sort key.
sort(arrayList, key=some_proxy_function)

Kent



More information about the Python-list mailing list