CODEWITHSUNDEEP
pythondictionary
Felix Schütz
Felix Schütz

Reputation: 1377

Is it possible to efficiently find the index of a dictionary item in Python by key?

As of Python 3.7, dictionaries are guarantueed to keep insertion order. According to the original proposal for the change of memory layout (https://mail.python.org/pipermail/python-dev/2012-December/123028.html), an indices list stores the index of each value, indexed by the key hash. Therefore, it should be possible to efficiently retrieve an index of an item in the dictionary by its key. However, there seems to be no method for doing that. The only way I can think of is the following:

a = {}
a[1] = "b"
a[0] = "a"
a[2] = "c"
list(a).index(0) # returns 1

However, this is very inefficient. Do I have to use a library with a custom dictionary implementation or is there a way to access the internal CPython representation of a dictionary?

Upvotes: 3

Views: 166

Answers (1)

Alain T.
Alain T.

Reputation: 42143

If you're going to perform this operation on the same dictionary multiple times (without changing its content), you could create an indexing dictionary for the keys and use that to get the index:

a = {1:"b", 0:"a", 2:"c"}
ia = {k:i for i,k in enumerate(a)}

print(ia[0]) # 1

If you don't want a separate dictionary, you could store the indexes along with the values in tuples:

a = {1:"b", 0:"a", 2:"c"}
a = {k:(i,v) for i,(k,v) in enumerate(a.items())}

print(a)
{1: (0, 'b'), 0: (1, 'a'), 2: (2, 'c')}


index,value = a[0]
print(index) # 1

Otherwise some form of sequential search will probably be your only option:

i = next(i for i,k in enumerate(a) if k=0)

Upvotes: 2

Related Questions