dictionnaries and lookup tables

[gry at ll.mit.edu]

m.barenco at gmail.com 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