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

[The_Kernel]

Basically you just want to put the keys from the dictionary into a list and sort that list. Then if you iterate through the sorted list of keys. Like this:

my_dict = { 'z': 1,  'a': 2,  'g': 3 }
sorted_keys = sorted(my_dict.keys())

for key in sorted_keys:
    print '%s = %s' % (key, my_dict[key])

running this results in:

a = 2
g = 3
z = 1

[akindo]

Hi Kernel. Thanks for that info. I have read about this technique, but I am pretty sure it doesn't solve my problem. I want to avoid having to iterate through a list from the beginning of it, but instead be able to index directly into it like in a dictionary using my own IDs (not the location of the list element), but then be able to iterate from that point on.

[The_Kernel]

I don't know if you'll be able to do exactly what you're talking about. However once you have the sorted list of keys you could always do the following (to start iterating at the letter 'g' in the example):

my_dict = { 'z': 1,  'a': 2,  'g': 3 }
sorted_keys = sorted(my_dict.keys())

index = sorted_keys.index('g')

for key in sorted_keys[index:]:
    print '%s = %s' % (key, my_dict[key])

[woooee]

You can find an ordered dictionary here http://www.voidspace.org.uk/python/odict.html but that does not solve the "but then want _all_ messages with a higher ID" problem as you don't know what the next higher key is. A list of keys will return the index of the key found, and you can then increment through the end. Another way is to use an in memory SQLite database, lookup the key and then fetch until their are no more records
cur.execute(<SQL QUERY>)
cur.fetchone() # get one record
cur.fetchone() # get next record
If there is some reason why you can not do it either way then please post the reason, otherwise this thread should be considered solved.

[scru]

index = sorted_keys.index('g')

No.

[The_Kernel]

No.

Care to elaborate?

[scru]

The index method when used on a list still scans from start until it finds the item. So this isn't what the poster is looking for.

[akindo]

woee: Thanks. An ordered dictionary, going by the Python PEP 372 (http://www.python.org/dev/peps/pep-0372/) definition, is defined as one in which "the ordering of items is defined by the time of insertion of the key. New keys are appended at the end, but keys that are overwritten are not moved to the end." This is not what I am looking for. I am looking for a sorted dictionary, sorted by key values (i. e. 1 comes before 2 comes before 3).

The SQLite database idea is a real good one and the best answer I've gotten so far, may go for this.

scru: agreed, list.index() still starts scanning from the beginning, something I want to avoid.

But thanks to all of you for your help! :)