dictionnaries and lookup tables

[m.barenco]

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?

Note that when I type:dir(D)

['__class__', '__cmp__', '__contains__', '__delattr__', '__delitem__',
'__doc__', '__eq__', '__ge__', '__getattribute__', '__getitem__',
'__gt__', '__hash__', '__init__', '__iter__', '__le__', '__len__',
'__lt__', '__ne__', '__new__', '__reduce__', '__reduce_ex__',
'__repr__', '__setattr__', '__setitem__', '__str__', 'clear', 'copy',
'fromkeys', 'get', 'has_key', 'items', 'iteritems', 'iterkeys',
'itervalues', 'keys', 'pop', 'popitem', 'setdefault', 'update',
'values']
the functions __ge__, __gt__, __lt__, __le__ seem to be non-implemented
but there is some __doc__ in them. Is there the intention to do
something similar as is described above or are they here for some
(future) dictionnary comparison purposes?

Thanks a lot!

Martino

[jepler]

On Tue, Oct 11, 2005 at 11:06:32AM -0700, m.*******@gmail.com wrote:

Note that when I type:

dir(D) [...]

the functions __ge__, __gt__, __lt__, __le__ seem to be non-implemented
but there is some __doc__ in them. Is there the intention to do
something similar as is described above or are they here for some
(future) dictionnary comparison purposes?

Sure they're implemented. That's why I can compare dictionaries for equality
or order.
d = {1: None}
e = {1: None}
f = {2: None}
d == e True d == f False d < f or f < e

True

If the operation you need to optimize is "find the largest element that is
smaller than X", then perhaps you want to use the bisect module. This involves
keeping your information in a sorted list of tuples, instead of in a
dictionary. However, removing or inserting items has O(n) complexity instead
of O(1).

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDTAG7Jd01MZaTXX0RApT8AKCE3d40OIZXFNQXTWqm9a 8xhJheVgCbBy/e
vm5m5gkTi+YViTmdNqkAdRM=
=z2yT
-----END PGP SIGNATURE-----

[gry]

m.*******@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/pytho...avl-2.0.tar.gz

[m.barenco]

>Sure they're implemented.

Oops, my apologies.

Just to build up on that, when I run:

#start of listing
import random

A={1:None,2:None,"hello":None,(1,2,3):None}

def dictcomp(n):
for i in range(n):
B=A.copy()
C=A.copy()
b=random.uniform(0,1)
c=random.uniform(0,1)
B[b]=None
C[c]=None
res=((B>C)==(b>c))
print res,

dictcomp(1000)
#end of listing

I get 1000 True's on the output, which suggests that key-wise ordering
is implemented in some guise. The question is: how do I access that?

Thanks

Martino

[Steve Holden]

m.*******@gmail.com wrote:

Sure they're implemented.

Oops, my apologies.

Just to build up on that, when I run:

#start of listing
import random

A={1:None,2:None,"hello":None,(1,2,3):None}

def dictcomp(n):
for i in range(n):
B=A.copy()
C=A.copy()
b=random.uniform(0,1)
c=random.uniform(0,1)
B[b]=None
C[c]=None
res=((B>C)==(b>c))
print res,

dictcomp(1000)
#end of listing

I get 1000 True's on the output, which suggests that key-wise ordering
is implemented in some guise. The question is: how do I access that?

You don't. There is no ordering of the keys, so there is no way that you
can implement the function you want.

regards
Steve
--
Steve Holden [phone] [phone]
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

[Steven D'Aprano]

On Tue, 11 Oct 2005 11:50:24 -0700, m.barenco wrote:

Just to build up on that, when I run:

#start of listing
import random

A={1:None,2:None,"hello":None,(1,2,3):None}

def dictcomp(n):
for i in range(n):
B=A.copy()
C=A.copy()
b=random.uniform(0,1)
c=random.uniform(0,1)
B[b]=None
C[c]=None
res=((B>C)==(b>c))
print res,

dictcomp(1000)
#end of listing

I get 1000 True's on the output, which suggests that key-wise ordering
is implemented in some guise. The question is: how do I access that?

I don't think your code is showing what you think it is showing. I think
you have discovered an accidental invariant that depends on the *specific*
details of your code. In fact, I predict that if you run that code again,
you will randomly get 1000 Trues, or 1000 Falses, but never mixed Trues
and Falses.

Does this quote from the Python reference manual help you?

"Keys and values are listed in an arbitrary order which is non-random,
varies across Python implementations, and depends on the dictionary's
history of insertions and deletions."

http://docs.python.org/lib/typesmapping.html

What about this?

"Mappings (dictionaries) compare equal if and only if their sorted (key,
value) lists compare equal. Outcomes other than equality are resolved
consistently, but are not otherwise defined."

http://docs.python.org/ref/comparisons.html
In other words, even if you have discovered a consistent invariant
of dict behaviour, you can't rely on it -- it may disappear with the next
release of Python, or if you use an older version, or a version on a
different platform, or even because you've deleted an item from a dict and
then put it back in. (And if you know anything about typical
implementations of hash tables, you will understand why that last one is
quite reasonable.)


--
Steven.

[m.barenco]

Ok, Thanks for your answers, that's pretty unambiguous.

M.