Iterating Over Dictionary From Arbitrary Location
Diez B. Roggisch
deets at nospam.web.de
Sat Jun 6 11:53:54 EDT 2009
akindo schrieb:
> Hi all. I am new to Python and have a problem regarding data structures.
>
> In my application I will be having several messages and my own type of
> IDs (Lamport clocks) to go with these messages. I will need to
> frequently ask for specific messages based on the ID. Hence a dictionary
> seems a better choice than a list, as I will be using my own IDs to
> index into the data structure. However, the problem is that I will also
> at times ask for a specific message based on the ID key, but then want
> _all_ messages with a higher ID returned as well. :shock: From my
> research, there are two problems with a dictionary then: 1. it can't be
> sorted (only returns a sorted list), 2. even if it was possible to sort
> a dictionary, it is not possible to iterate over it from a given location.
>
> So, it seems I want the best of both worlds: specific indexing using my
> own IDs/keys (not just by list element location), sorting and the
> ability to start iterating from a specific location. I am trying to
> prevent having to scan through a list from the beginning to find the
> desired ID, and then return all elements after that. Is there another
> data structure or design pattern which will do what I want? Thanks a lot
> for any help! :)
you could use a list which is sorted and then use the bisect-module to
look up your keys in O(log n). You could also map keys to list-indices.
Diez
More information about the Python-list
mailing list