dictionnaries and lookup tables

Discussion in 'Python' started by m.barenco@gmail.com, Oct 11, 2005.

  1. Guest

    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
    , Oct 11, 2005
    #1
    1. Advertising

  2. Guest

    On Tue, Oct 11, 2005 at 11:06:32AM -0700, 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)

    iD8DBQFDTAG7Jd01MZaTXX0RApT8AKCE3d40OIZXFNQXTWqm9a8xhJheVgCbBy/e
    vm5m5gkTi+YViTmdNqkAdRM=
    =z2yT
    -----END PGP SIGNATURE-----
    , Oct 11, 2005
    #2
    1. Advertising

  3. Guest

    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
    , Oct 11, 2005
    #3
  4. Guest

    >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=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
    , Oct 11, 2005
    #4
  5. Steve Holden Guest

    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=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/
    Steve Holden, Oct 11, 2005
    #5
  6. 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=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.
    Steven D'Aprano, Oct 12, 2005
    #6
  7. Guest

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

    M.
    , Oct 12, 2005
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Demetri
    Replies:
    0
    Views:
    332
    Demetri
    Oct 15, 2003
  2. Jack
    Replies:
    0
    Views:
    356
  3. Adrian Charteris

    XSLT Lookup Tables Help.

    Adrian Charteris, Oct 15, 2004, in forum: XML
    Replies:
    4
    Views:
    935
    Adrian Charteris
    Oct 18, 2004
  4. John Collyer

    Function lookup tables?

    John Collyer, Oct 4, 2003, in forum: C++
    Replies:
    12
    Views:
    1,279
    Karl Heinz Buchegger
    Oct 6, 2003
  5. Salvatore

    "Adding" dictionnaries

    Salvatore, Jun 13, 2006, in forum: Python
    Replies:
    4
    Views:
    262
Loading...

Share This Page