sorting with expensive compares?
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.
More information about the Python-list