Op 09-04-16 om 17:31 schreef Chris Angelico: > On Sun, Apr 10, 2016 at 1:24 AM, Antoon Pardon > <antoon.par...@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 -- https://mail.python.org/mailman/listinfo/python-list
