how to convert code that uses cmp to python3

[Ian Kelly]

On Thu, Apr 7, 2016 at 2:56 PM, Antoon Pardon
<antoon.pardon at rece.vub.ac.be> wrote:
> Op 07-04-16 om 14:22 schreef Chris Angelico:
>
> ...
>
>> There's no __cmp__ method, but you could easily craft your own
>> compare() function:
>>
>> def compare(x, y):
>>     """Return a number < 0 if x < y, or > 0 if x > y"""
>>     if x == y: return 0
>>     return -1 if keyify(x) < keyify(y) else 1
>>
>> I'm not sure how your tree is crafted and how your "cheap" and
>> "expensive" comparisons previously worked, but give something like
>> this a try. I think you'll find it adequate.
>
> That solution will mean I will have to do about 100% more comparisons
> than previously.
>
> Lets simplify for the moment and suppose all keys are tuples of
> integers. Now because how trees are organised, the lower you
> descend in the tree, the closer the keys are together. In the
> case of tuples that means higher probability you have to traverse
> the two tuples further in order to find out which is greater.
>
> With the __cmp__ method, you only had to traverse the two tuples
> once in order to find out whether they were equal or if not which
> is the smaller and which is the greater.
>
> With this method I have to traverse the two tuples almost always
> twice. Once to find out if they are equal and if not a second
> time to find out which is greater.

You can reduce that to ~50% more if you swap the order. Check if one
tuple is less first. If it is, you have your answer, no further
comparison required. Otherwise, check the less likely case that
they're equal.