Performance ordered dictionary vs normal dictionary

Discussion in 'Python' started by Navkirat Singh, Jul 29, 2010.

  1. Hi guys,

    I was wondering what would be better to do some medium to heavy book keeping in memory - Ordered Dictionary or a plain simple Dictionary object??

    Regards,
    N4v
     
    Navkirat Singh, Jul 29, 2010
    #1
    1. Advertising

  2. Navkirat Singh

    sturlamolden Guest

    On 29 Jul, 03:47, Navkirat Singh <> wrote:

    > I was wondering what would be better to do some medium to heavy book keeping in memory - Ordered Dictionary or a plain simple Dictionary object??


    It depends on the problem. A dictionary is a hash table. An ordered
    dictionary is a binary search tree (BST). Those are different data
    structures.

    The main things to note is that:

    - Access is best-case O(1) for the hash table and O(log n) for the
    BST.

    - Worst case behavior is for access is O(n) for both. The pathologic
    conditions are excessive collisions (hash) or an unbalanced tree
    (BST). In pathologic cases they both converge towards a linked list.

    - Searches are only meaningful for == and != for a hash table, but BST
    searches are also meaningful for >, <, <=, and >=. For this reason,
    databases are often implemented as BSTs.

    - A BST can be more friendly to cache than a hash table, particularly
    when they are large. (Remember that O(1) can be slower than O(log n).
    Big-O only says how run-time scales with n.)

    That said, I have not compared ordered dicts with normal dicts, as I
    still use 2.6.
     
    sturlamolden, Jul 29, 2010
    #2
    1. Advertising

  3. On 29-Jul-2010, at 9:36 AM, sturlamolden wrote:

    > On 29 Jul, 03:47, Navkirat Singh <> wrote:
    >
    >> I was wondering what would be better to do some medium to heavy book keeping in memory - Ordered Dictionary or a plain simple Dictionary object??

    >
    > It depends on the problem. A dictionary is a hash table. An ordered
    > dictionary is a binary search tree (BST). Those are different data
    > structures.
    >
    > The main things to note is that:
    >
    > - Access is best-case O(1) for the hash table and O(log n) for the
    > BST.
    >
    > - Worst case behavior is for access is O(n) for both. The pathologic
    > conditions are excessive collisions (hash) or an unbalanced tree
    > (BST). In pathologic cases they both converge towards a linked list.
    >
    > - Searches are only meaningful for == and != for a hash table, but BST
    > searches are also meaningful for >, <, <=, and >=. For this reason,
    > databases are often implemented as BSTs.
    >
    > - A BST can be more friendly to cache than a hash table, particularly
    > when they are large. (Remember that O(1) can be slower than O(log n).
    > Big-O only says how run-time scales with n.)
    >
    > That said, I have not compared ordered dicts with normal dicts, as I
    > still use 2.6.
    >
    >
    >
    >
    >
    >
    >
    >
    >
    >
    > --
    > http://mail.python.org/mailman/listinfo/python-list



    Thanks for the insight. I am still in the thinking stage, so will let you know as and when I get down to implementation of my idea.

    Thanks for your time. : )

    Regards,
    Nav
     
    Navkirat Singh, Jul 29, 2010
    #3
  4. Navkirat Singh

    Chris Rebert Guest

    On Wed, Jul 28, 2010 at 9:06 PM, sturlamolden <> wrote:
    > On 29 Jul, 03:47, Navkirat Singh <> wrote:
    >> I was wondering what would be better to do some medium to heavy book keeping in memory - Ordered Dictionary or a plain simple Dictionary object??

    >
    > It depends on the problem. A dictionary is a hash table. An ordered
    > dictionary is a binary search tree (BST).


    Er, if you're talking about collections.OrderedDict specifically,
    you're wrong. It's quite clearly implemented using a regular
    dictionary (i.e. hash table) and auxiliary list: See
    http://bugs.python.org/file13231/od7.diff from
    http://bugs.python.org/issue5397

    Cheers,
    Chris
    --
    http://blog.rebertia.com
     
    Chris Rebert, Jul 29, 2010
    #4
  5. On Jul 28, 6:47 pm, Navkirat Singh <> wrote:
    > I was wondering what would be better to do some medium
    > to heavy book keeping in memory - Ordered Dictionary
    > or a plain simple Dictionary object??


    The current implementation of OrderedDict is based on regular
    dictionaries, so it performance cannot be better than a regular
    dictionary for the usual mapping operations. Some accessor methods
    like __getitem__(), __len__(), __contains__(), and get() are pass
    throughs, so their performance is the same. Most of the rest of the
    methods are order aware and are slower by a constant factor.

    So, if you don't need the ordering feature, then you're better-off
    with a regular dictionary.

    A potential future implementation for OrderedDict written in C would
    have nearly identical performance as regular dicts for most operations
    and slightly improved performance for iteration.

    Raymond
     
    Raymond Hettinger, Jul 29, 2010
    #5
  6. sturlamolden <> writes:

    > On 29 Jul, 03:47, Navkirat Singh <> wrote:
    >
    >> I was wondering what would be better to do some medium to heavy book keeping in memory - Ordered Dictionary or a plain simple Dictionary object??

    >
    > It depends on the problem. A dictionary is a hash table. An ordered
    > dictionary is a binary search tree (BST).


    The ordered dictionary shipped with Python is also a hash table, with an
    internal list to keep track of item order.

    The one thing not mentioned in the thread is that ordered dict's
    deletion is O(n), which might impact "heavy bookkeeping". As Raymond
    said, where order doesn't matter, it's best to stick with dict.
     
    Hrvoje Niksic, Jul 29, 2010
    #6
  7. On 29-Jul-2010, at 2:50 PM, Hrvoje Niksic wrote:

    > sturlamolden <> writes:
    >
    >> On 29 Jul, 03:47, Navkirat Singh <> wrote:
    >>
    >>> I was wondering what would be better to do some medium to heavy book keeping in memory - Ordered Dictionary or a plain simple Dictionary object??

    >>
    >> It depends on the problem. A dictionary is a hash table. An ordered
    >> dictionary is a binary search tree (BST).

    >
    > The ordered dictionary shipped with Python is also a hash table, with an
    > internal list to keep track of item order.
    >
    > The one thing not mentioned in the thread is that ordered dict's
    > deletion is O(n), which might impact "heavy bookkeeping". As Raymond
    > said, where order doesn't matter, it's best to stick with dict.
    > --
    > http://mail.python.org/mailman/listinfo/python-list


    Thanks that was an excellent point : )
     
    Navkirat Singh, Jul 29, 2010
    #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. Leif K-Brooks

    Ordered dictionary?

    Leif K-Brooks, Jan 22, 2004, in forum: Python
    Replies:
    13
    Views:
    769
    David M. Wilson
    Jan 23, 2004
  2. Tom Anderson
    Replies:
    0
    Views:
    320
    Tom Anderson
    Nov 26, 2005
  3. pyGuy
    Replies:
    2
    Views:
    305
    pyGuy
    Apr 12, 2006
  4. Chris Rebert
    Replies:
    0
    Views:
    529
    Chris Rebert
    Jul 29, 2010
  5. DL

    Ordered list inside ordered list

    DL, Nov 9, 2009, in forum: Javascript
    Replies:
    6
    Views:
    327
    Dr J R Stockton
    Nov 21, 2009
Loading...

Share This Page