Prev: Newbie question regarding SSL and certificate verification
Next: Function parameter scope
From: Navkirat Singh on 28 Jul 2010 21:47
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

From: Chris Rebert on 28 Jul 2010 22:01
On Wed, Jul 28, 2010 at 6:47 PM, Navkirat Singh <navkirats(a)gmail.com> wrote:
> 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??

Your question is rather vague. Define "book keeping". Why do you feel
an OrderedDict might be useful in solving your problem?

Cheers,
Chris
From: sturlamolden on 29 Jul 2010 00:06
On 29 Jul, 03:47, Navkirat Singh <navkir...(a)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.










From: Navkirat Singh on 29 Jul 2010 00:22

On 29-Jul-2010, at 9:36 AM, sturlamolden wrote:

> On 29 Jul, 03:47, Navkirat Singh <navkir...(a)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.
>
>
>
>
>
>
>
>
>
>
> --
> http://mail.python.org/mailman/listinfo/python-list


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

From: Chris Rebert on 29 Jul 2010 02:05
On Wed, Jul 28, 2010 at 9:06 PM, sturlamolden <sturlamolden(a)yahoo.no> wrote:
> On 29 Jul, 03:47, Navkirat Singh <navkir...(a)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).

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
--
http://blog.rebertia.com
 |  Next  |  Last
Pages: 1 2 3
Prev: Newbie question regarding SSL and certificate verification
Next: Function parameter scope