Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > dictionnaries and lookup tables

Reply
Thread Tools

dictionnaries and lookup tables

 
 
m.barenco@gmail.com
Guest
Posts: n/a
 
      10-11-2005
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

 
Reply With Quote
 
 
 
 
jepler@unpythonic.net
Guest
Posts: n/a
 
      10-11-2005
On Tue, Oct 11, 2005 at 11:06:32AM -0700, http://www.velocityreviews.com/forums/(E-Mail Removed) 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-----

 
Reply With Quote
 
 
 
 
gry@ll.mit.edu
Guest
Posts: n/a
 
      10-11-2005

(E-Mail Removed) 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

 
Reply With Quote
 
m.barenco@gmail.com
Guest
Posts: n/a
 
      10-11-2005
>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

 
Reply With Quote
 
Steve Holden
Guest
Posts: n/a
 
      10-11-2005
(E-Mail Removed) 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 +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

 
Reply With Quote
 
Steven D'Aprano
Guest
Posts: n/a
 
      10-11-2005
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.

 
Reply With Quote
 
m.barenco@gmail.com
Guest
Posts: n/a
 
      10-12-2005
Ok, Thanks for your answers, that's pretty unambiguous.

M.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
"Adding" dictionnaries Salvatore Python 4 06-13-2006 02:06 PM
XSLT Lookup Tables Help. Adrian Charteris XML 4 10-18-2004 08:58 AM
using XSLT to do "medium-heavy" data transformations with lookup tables Jack Java 0 04-20-2004 10:29 PM
Datagrid or Datalist with Lookup Tables Demetri ASP .Net 0 10-15-2003 01:26 AM
Function lookup tables? John Collyer C++ 12 10-06-2003 12:37 PM



Advertisments