N

#### Navkirat Singh

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

N

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

Ad

S

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.

N

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

C

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

R

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

H

sturlamolden said: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.

Ad

N

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 : )

**Want to reply to this thread or ask your own question?**

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.