Performance ordered dictionary vs normal dictionary

[sturlamolden]

On 29 Jul, 03:47, Navkirat Singh <navkir... at gmail.com> 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.