Iterating Over Dictionary From Arbitrary Location

[akindo]

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!

 

[Diez B. Roggisch]

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

 

[bearophileHUGS]

akindo:

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.

A sorted associative map may be fit. A data structure based on a
search tree, like a red-black tree, etc.
The Python std lib doesn't contain such data structure.
Do you need to add items to your data structure? Diez has suggested a
possible solution. You can keep a copy of the items in a sorted list,
but this isn't handy if you have to add and remove items frequently.
Or you may be able to find somewhere a sorted associative array data
structure (tree-based).

Bye,
bearophile

 

[Aahz]

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!

One option is to maintain both a dict and a list; it doesn't cost much
memory because the individual elements don't get copied. See various
"ordered dictionary" implementations for ideas on coding this.

 

[bearophileHUGS]

Aahz:

See various "ordered dictionary" implementations
for ideas on coding this.

But be careful to not confuse ordered dictionaries with sorted
ones

Bye,
bearophile