Performance ordered dictionary vs normal dictionary

[Shashwat Anand]

>
>
> 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.)
>
>
Thanks, this was really insightful :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100729/fb8b429a/attachment-0001.html>