Performance ordered dictionary vs normal dictionary

[Navkirat Singh]

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

 

[sturlamolden]

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.

 

[Navkirat Singh]

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.

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

 

[Chris Rebert]

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

 

[Raymond Hettinger]

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

 

[Hrvoje Niksic]

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.

 

[Navkirat Singh]

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.

Thanks that was an excellent point : )