getting the key index in a Python OrderedDict?

python dictionary ordereddictionary
Jason S picture Jason S · Dec 31, 2014 · Viewed 16k times · Source

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.

Answer

BrenBarn picture BrenBarn · Dec 31, 2014

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.

Related questions

Rename a dictionary key

Is there a way to rename a dictionary key, without reassigning its value to a new name and removing the old name key; and without iterating through dict key/value? In case of OrderedDict, do the same, while keeping that …

Read More
Accessing items in an collections.OrderedDict by index

Lets say I have the following code: import collections d = collections.OrderedDict() d['foo'] = 'python' d['bar'] = 'spam' Is there a way I can access the items in a numbered manner, like: d(0) #foo's Output d(1) #bar's Output

Read More
Right way to initialize an OrderedDict using its constructor such that it retains order of initial data?

What's the correct way to initialize an ordered dictionary (OD) so that it retains the order of initial data? from collections import OrderedDict # Obviously wrong because regular dict loses order d = OrderedDict({'b':2, 'a':1}) # An OD is represented by a …

Read More