[EMAIL PROTECTED] wrote: > Hello, > > I am considering using dictionnaries as lookup tables e.g. > > >>>D={0.5:3.9,1.5:4.2,6.5:3} > > and I would like to have a dictionnary method returning the key and > item of the dictionnary whose key is smaller than the input of the > method (or <=,>,>=) but maximal (resp. maximal,minimal,minimal) eg.: > > >>>D.smaller(3.0) > (1.5,4.2) > >>>D.smaller(11.0) > (6.5,3) > >>>D.smaller(-1.0) > None (or some error message) > > Now, I know that dictionnaries are stored in a non-ordered fashion in > python but they are so efficient in recovering values (at least wrt > lists) that it suggests me that internally there is some ordering. I > might be totally wrong because I don't know how the hashing is really > done. Of course I would use such methods in much larger tables. So is > this possible or should I stick to my own class with O(log2(N)) > recovery time? ...
I believe that to do this efficiently, you want some kind of tree, e.g. B-tree, RB-tree, AVL-tree. You could try the AVL tree from: ftp://squirl.nightmare.com/pub/python/python-ext/avl/avl-2.0.tar.gz -- http://mail.python.org/mailman/listinfo/python-list