Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

getting the key index in a Python OrderedDict?

Tags:

I have a collections.OrderedDict with a list of key, value pairs. I would like to compute the index i such that the ith key matches a given value. For example:

food = OrderedDict([('beans',33),('rice',44),('pineapple',55),('chicken',66)])

I want to go from the key chicken to the index 3, or from the key rice to the index 1. I can do this now with

food.keys().index('rice')

but is there any way to leverage the OrderedDict's ability to look things up quickly by key name? Otherwise it seems like the index-finding would be O(N) rather than O(log N), and I have a lot of items.

I suppose I can do this manually by making my own index:

>>> foodIndex = {k:i for i,k in enumerate(food.keys())}
>>> foodIndex
{'chicken': 3, 'rice': 1, 'beans': 0, 'pineapple': 2}

but I was hoping there might be something built in to an OrderedDict.

like image 698
Jason S Avatar asked Dec 31 '14 20:12

Jason S


People also ask

Is OrderedDict obsolete?

No it won't become redundant in Python 3.7 because OrderedDict is not just a dict that retains insertion order, it also offers an order dependent method, OrderedDict. move_to_end() , and supports reversed() iteration*.

How do you check if an item is in a dictionary python?

You can check if a key exists or not in a dictionary using if-in statement/in operator, get(), keys(), handling 'KeyError' exception, and in versions older than Python 3, using has_key().

What is OrderedDict in Python?

Python's OrderedDict is a dict subclass that preserves the order in which key-value pairs, commonly known as items, are inserted into the dictionary. When you iterate over an OrderedDict object, items are traversed in the original order. If you update the value of an existing key, then the order remains unchanged.


2 Answers

Basically, no. OrderedDict gets its ability to look things up quickly by key name just by using a regular, unordered dict under the hood. The order information is stored separately in a doubly linked list. Because of this, there's no way to go directly from the key to its index. The order in an OrderedDict is mainly intended to be available for iteration; a key does not "know" its own order.

like image 59
BrenBarn Avatar answered Oct 06 '22 09:10

BrenBarn


As others have pointed out, an OrderedDict is just a dictionary that internally remembers what order entries were added to it. However, you can leverage its ability to look-up things quickly by storing the desired index along with the rest of the data for each entry. Here's what I mean:

from collections import OrderedDict

foods = [('beans', 33), ('rice', 44), ('pineapple', 55), ('chicken', 66)]
food = OrderedDict(((v[0], (v[1], i)) for i, v in enumerate(foods))) # saves i

print(food['rice'][1])  # --> 1
print(food['chicken'][1])  # --> 3
like image 43
martineau Avatar answered Oct 06 '22 09:10

martineau