Performance ordered dictionary vs normal dictionary

[Navkirat Singh]

On 29-Jul-2010, at 2:50 PM, Hrvoje Niksic wrote:

> sturlamolden <sturlamolden at yahoo.no> writes:
> 
>> 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).
> 
> 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 : )