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

Groups > comp.lang.python > #106743 > 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 Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2016-04-09 18:03 +0200
    Re: how to convert code that uses cmp to python3 Marko Rauhamaa <marko@pacujo.net> - 2016-04-09 19:32 +0300

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

Op 09-04-16 om 17:31 schreef Chris Angelico:
> On Sun, Apr 10, 2016 at 1:24 AM, Antoon Pardon
> <antoon.pardon@rece.vub.ac.be> wrote:
>>
>> So? I need a structure that can easily give me an answer to the
>> following: Given key1 and key2 what are the the keys between them
>> with their corresponding values. As long as a dict can't provide
>> me with that answer, it doesn't matter that it will out perform
>> lookups in my trees.
> 
> Ah, okay. You can probably still take advantage of the other thing I
> mentioned, which was structuring your tree such that it's aware of the
> common prefixes, even if you can't go for O(1) hashing. That would
> drastically reduce the number of comparisons you have to do.

I think that would be a premature optization at this point. At this
moment I am just converting my python2 avltree module to python3.
This module doesn't care about how the keys are structured, it just
wants to know, given two keys, how are they ordered.

Now the original module can avoid doing some duplicate work by using
cmp instead of directly using the comparators. I am only prepared
to do something similar, because this is supposed to be a general
purpose tree and not one taylored to specific kinds of key objects.

The tests I have done show, the above is not an issue if my keys
are simple python objects like ints, strings, ... or tuples of
such.

And when I need some personal object as a key, I can avoid the
duplication by using some kind of cmp cache when I implement
__lt__ and family.

-- 
Antoon Pardon

[toc] | [next] | [standalone]

#106745

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

> And when I need some personal object as a key, I can avoid the
> duplication by using some kind of cmp cache when I implement __lt__
> and family.

Yes, that's what you can do in rare, extreme cases where key comparison
takes a long time. For caching, you will simply need to require that
keys stay immutable wrt comparing.


Marko

[toc] | [prev] | [standalone]

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

csiph-web