Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #106731

Re: how to convert code that uses cmp to python3

Show key headers only | View raw

Op 09-04-16 om 13:49 schreef Ben Finney:
> Antoon Pardon <antoon.pardon@rece.vub.ac.be> writes:
> 
>> You don't seem to understand. I only do two comparisons and no the
>> equality is not necesarrily cheaper.
>>
>> I am talking about the difference between the following two:
>>
>>     if arg.key < node.key:   # possible expensive computation
>>         go_left()
>>     elif arg.key == node.key # possible expensive computation
>>         found_node()
>>     else:
>>         go_right()
>>
>> and
>>
>>     delta = cmp(arg.key, node.key) # possible expensive computation
>>     if delta < 0:                  # cheap computation
>>         go_left()
>>     elif delta == 0:               # cheap computation
>> 	found_node()
>>     else:
>>         go_right()
> 
> I find that a dubious claim.
> 
> The ‘cmp’ implementation must decide *at least* between three
> conditions: less-than, equal-to, greater-than. That is *at least* two
> inflection points.
> 
> The implementation of ‘__lt__’ and the implementation of ‘__eq__’ each
> only need to decide two conditions (true, false). So that is *at most*
> two inflection points.
> 
> If you're saying the latter implementation is somehow *more* expensive
> than the former, I think the implementations are suspect and likely can
> be improved: at least parity should be possible, to the point of
> statistical insignificance.

Let me give you an artifical example to show what can happen. The keys are all
iterables of equal lengths with integers as elements.

Then this could be the cmp function:

def cmp(ob1, ob2):
    itr1 = iter(ob1)
    itr2 = iter(ob2)
    for el1, el2 in zip(itr1, itr2)
        delta = el1 - el2
        if delta != 0:
            return delta
    return 0

Now maybe I'm missing something but I don't see how implementing __lt__ and
__eq__ in this case will be much different from largely reimplenting cmp.
So if you can work with a cmp function, you only need to travese the two
iterables only once. If you do it with the __lt__ and __eq__ methods you
will have to traverse them twice.

Now this probably is not a problem most of the times, but when you work with
tree's this kind of comparison to make a three way decision happens often and
the lower you descend in the tree, the close your argument will be with the
keys of the nodes you visit, making it more and more probable, you have a
large common prefix.

So in these circumstances it is more likely to be problematic.

-- 
Antoon Pardon

Back to comp.lang.python | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Re: how to convert code that uses cmp to python3 Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-04-09 16:25 +0200
  Re: how to convert code that uses cmp to python3 Marko Rauhamaa <marko@pacujo.net> - 2016-04-09 17:54 +0300

csiph-web