dictionnaries and lookup tables
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
--
http://mail.python.org/mailman/listinfo/python-list
Re: dictionnaries and lookup tables
On Tue, Oct 11, 2005 at 11:06:32AM -0700, [EMAIL PROTECTED] 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
pgpoNBi46YeD2.pgp
Description: PGP signature
--
http://mail.python.org/mailman/listinfo/python-list
Re: dictionnaries and lookup tables
[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
Re: dictionnaries and lookup tables
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=((BC)==(bc))
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
--
http://mail.python.org/mailman/listinfo/python-list
Re: dictionnaries and lookup tables
[EMAIL PROTECTED] 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=((BC)==(bc))
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 +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/
--
http://mail.python.org/mailman/listinfo/python-list
Re: dictionnaries and lookup tables
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=((BC)==(bc))
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.
--
http://mail.python.org/mailman/listinfo/python-list
Re: dictionnaries and lookup tables
Ok, Thanks for your answers, that's pretty unambiguous. M. -- http://mail.python.org/mailman/listinfo/python-list
