using datetime containers

Arnaud Delobelle arnodel at
Sun Nov 9 07:49:02 CET 2008

indika <indikabandara19 at> writes:

> while trying out the sorting method i realized that u can *never*
> insert the sorted data to dict !!!
>>>> m1
> {, 1, 1): 'b',, 1, 3): 'c',
>, 1, 2): 'a'}
>>>> l = sorted(m1.items(), cmp=cmpr) // cmpr is date comp function
>>>> for i, j in l:
> ...     m3[i] = j;
> ...
>>>> m3
> {, 1, 1): 'b',, 1, 3): 'c',
>, 1, 2): 'a'}
> so then there's no point in sorting.
> it will only be possible to do a linear search i.e. sort and add to
> list then search from top.

That's because dicts are the wrong data structure for this.  Dicts are
implemented as hashtables.  You can use lists instead: look at the
module bisect.  There aren't any linear structures with fast insertion
in standard Python (e.g. d-linked lists or balanced trees). 

> I would really like to suggest some wrapper or an enhanced dict
> structure which has a configurable comparison function that will be
> used to insert and find keys.
> this will help, for example, if we want to go to a specific key and
> iterate from there onwards

I'm sure that googling for 'python sorted dict' with yield useful
information and probably some implementations.


More information about the Python-list mailing list