getting the key index in a Python OrderedDict?
Solution 1
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.
Solution 2
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
Solution 3
The OrderedDict is a subclass of dict
which has the ability to traverse its keys in order (and reversed order) by maintaining a doubly linked list. So it does not know the index of a key. It can only traverse the linked list to find the items in O(n) time.
Perusing the source code may be the most satisfying way to confirm that the index is not maintained by OrderedDict. You'll see that no where is an index ever used or obtained.
Related videos on Youtube
Jason S
Updated on June 27, 2022Comments
-
Jason S almost 2 years
I have a
collections.OrderedDict
with a list of key, value pairs. I would like to compute the indexi
such that thei
th 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 keyrice
to the index 1. I can do this now withfood.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
.-
jtlz2 over 3 yearsDoes
food.keys().index('rice')
work for python3?
-
-
BrenBarn over 9 yearsYou can do that, but it won't be kept in sync if you add and/or remove items.