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

Groups > comp.lang.python > #106665 > unrolled thread

Re: how to convert code that uses cmp to python3

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: how to convert code that uses cmp to python3 Marko Rauhamaa <marko@pacujo.net> - 2016-04-08 11:34 +0300
    Re: how to convert code that uses cmp to python3 Steven D'Aprano <steve@pearwood.info> - 2016-04-08 19:23 +1000
      Re: how to convert code that uses cmp to python3 Ian Kelly <ian.g.kelly@gmail.com> - 2016-04-08 08:17 -0600
        Re: how to convert code that uses cmp to python3 Marko Rauhamaa <marko@pacujo.net> - 2016-04-08 19:33 +0300
          Re: how to convert code that uses cmp to python3 Ian Kelly <ian.g.kelly@gmail.com> - 2016-04-08 11:05 -0600
            Re: how to convert code that uses cmp to python3 Marko Rauhamaa <marko@pacujo.net> - 2016-04-08 20:14 +0300

#106665 — Re: how to convert code that uses cmp to python3

Antoon Pardon <antoon.pardon@rece.vub.ac.be>:

> In python2 descending the tree would only involve at most one
> expensive comparison, because using cmp would codify that comparison
> into an integer which would then be cheap to compare with 0. Now in
> python3, I may need to do two expensive comparisons, because there is
> no __cmp__ method, to make such a codefication.

I think you should base your tree implementation on key.__lt__() only.
Only compare keys using <, nothing else, ever.

It may lead to faster or slower performance, depending on the ordering
function, but I think it is more minimalistic, and thus philosophically
more appealing than __cmp__.


Marko

[toc] | [next] | [standalone]

#106668

On Fri, 8 Apr 2016 06:34 pm, Marko Rauhamaa wrote:

> Antoon Pardon <antoon.pardon@rece.vub.ac.be>:
> 
>> In python2 descending the tree would only involve at most one
>> expensive comparison, because using cmp would codify that comparison
>> into an integer which would then be cheap to compare with 0. Now in
>> python3, I may need to do two expensive comparisons, because there is
>> no __cmp__ method, to make such a codefication.
> 
> I think you should base your tree implementation on key.__lt__() only.
> Only compare keys using <, nothing else, ever.

I believe that's how list.sort() and sorted() work:

py> class Spam(object):
...     def __init__(self, n):
...             self.n = n
...     def __lt__(self, other):
...             return self.n < other.n
...     def __repr__(self):
...             return repr(self.n)
...
py> L = [Spam(5), Spam(3), Spam(9), Spam(1), Spam(2)]
py> L
[5, 3, 9, 1, 2]
py> sorted(L)
[1, 2, 3, 5, 9]


as well as max() and min().



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#106682

On Fri, Apr 8, 2016 at 3:23 AM, Steven D'Aprano <steve@pearwood.info> wrote:
> On Fri, 8 Apr 2016 06:34 pm, Marko Rauhamaa wrote:
>
>> Antoon Pardon <antoon.pardon@rece.vub.ac.be>:
>>
>>> In python2 descending the tree would only involve at most one
>>> expensive comparison, because using cmp would codify that comparison
>>> into an integer which would then be cheap to compare with 0. Now in
>>> python3, I may need to do two expensive comparisons, because there is
>>> no __cmp__ method, to make such a codefication.
>>
>> I think you should base your tree implementation on key.__lt__() only.
>> Only compare keys using <, nothing else, ever.
>
> I believe that's how list.sort() and sorted() work:
>
> py> class Spam(object):
> ...     def __init__(self, n):
> ...             self.n = n
> ...     def __lt__(self, other):
> ...             return self.n < other.n
> ...     def __repr__(self):
> ...             return repr(self.n)
> ...
> py> L = [Spam(5), Spam(3), Spam(9), Spam(1), Spam(2)]
> py> L
> [5, 3, 9, 1, 2]
> py> sorted(L)
> [1, 2, 3, 5, 9]
>
>
> as well as max() and min().

That's fine for those operations and probably insert, but how do you
search an AVL tree for a specific key without also using __eq__?

[toc] | [prev] | [next] | [standalone]

#106691

Ian Kelly <ian.g.kelly@gmail.com>:

> That's fine for those operations and probably insert, but how do you
> search an AVL tree for a specific key without also using __eq__?

Not needed:

========================================================================
if key < node.key:
    look_right()
elif node.key < key:
    look_left()
else:
    found_it()
========================================================================


Marko

[toc] | [prev] | [next] | [standalone]

#106693

On Fri, Apr 8, 2016 at 10:33 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Ian Kelly <ian.g.kelly@gmail.com>:
>
>> That's fine for those operations and probably insert, but how do you
>> search an AVL tree for a specific key without also using __eq__?
>
> Not needed:
>
> ========================================================================
> if key < node.key:
>     look_right()
> elif node.key < key:
>     look_left()
> else:
>     found_it()
> ========================================================================

That makes me a little nervous since it assumes that the keys are
totally ordered and could return an incorrect node if they aren't.
Granted, the keys *should* be totally ordered if the data structure is
being used properly, but an explicit equality check ensures that the
worst that could happen is the node simply isn't found despite being
present.

More to the contextual point, this is still doing two comparisons,
even if both of them are less than, so it doesn't really solve the
OP's issue.

[toc] | [prev] | [next] | [standalone]

#106695

Ian Kelly <ian.g.kelly@gmail.com>:

> On Fri, Apr 8, 2016 at 10:33 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> Ian Kelly <ian.g.kelly@gmail.com>:
>>
>>> That's fine for those operations and probably insert, but how do you
>>> search an AVL tree for a specific key without also using __eq__?
>>
>> Not needed:
>>
>> ========================================================================
>> if key < node.key:
>>     look_right()
>> elif node.key < key:
>>     look_left()
>> else:
>>     found_it()
>> ========================================================================
>
> That makes me a little nervous since it assumes that the keys are
> totally ordered and could return an incorrect node if they aren't.

That's all the more reason to tie the order explicitly to < and nothing
else.

> Granted, the keys *should* be totally ordered if the data structure is
> being used properly, but an explicit equality check ensures that the
> worst that could happen is the node simply isn't found despite being
> present.

Well, how do you know how __eq__ and __lt__ are related?

Better simply *define* a *match* as

   not key < node.key and not node.key < key

> More to the contextual point, this is still doing two comparisons,
> even if both of them are less than, so it doesn't really solve the
> OP's issue.

I'm not sure the OP has a real issue. If *that* is a real issue, I
recommend a different programming language. Thing is, I bet method calls
are the single most expensive Python operation, yet would anyone suggest
avoiding method calls?


Marko

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web