Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From: Antoon Pardon <antoon.pardon@rece.vub.ac.be>
Newsgroups: comp.lang.python
Subject: Re: how to convert code that uses cmp to python3
Date: Sat, 9 Apr 2016 16:25:38 +0200
Lines: 70
Message-ID: <mailman.118.1460212008.2253.python-list@python.org>
References: <57064D0D.1030701@rece.vub.ac.be> <CAPTjJmrGiQS9uhFU-+TQ4nUWQ2p4gmJoQitMotS0Ob--qm1iWg@mail.gmail.com> <5706C961.2000009@rece.vub.ac.be> <CAPTjJmrbL870mV1kU8nHar=bPyKZRmhKP-8iUs_tpYVo5vhhOA@mail.gmail.com> <57075F43.7060004@rece.vub.ac.be> <85fuuw5ypl.fsf@benfinney.id.au> <5707B2CE.1010407@rece.vub.ac.be> <CAPTjJmrMv5O5vwrbfHJJCdiHi87naPOanhPmk4Ba_SLRgu1m4Q@mail.gmail.com> <5707BE18.1050805@rece.vub.ac.be> <CAPTjJmoMuqwg0Q_fp=qitC3wWkXYHtdqBNVGzO+3ToAmsgit8Q@mail.gmail.com> <5708C8B0.6050904@rece.vub.ac.be> <85twjb3su5.fsf@benfinney.id.au> <570910E2.3030400@rece.vub.ac.be>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Icedove/38.7.0
In-Reply-To: <85twjb3su5.fsf@benfinney.id.au>
Precedence: list
Xref: csiph.com comp.lang.python:106731

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