Which is more efficient in Python: list.index () or dict.get ()
I am trying to solve the problem on LeetCode. I am using Python and I did the following:
def twoSum(self, num, target):
index0 = 0
index1 = -1
for item in num:
index0 += 1
other = target - item
try:
index1 = num[index0:].index(other)
index1 += index0 + 1
except ValueError:
continue
else:
break
return index0, index1
But I always get the result: Time Limit Exceeded
The idea of my code is to check if it is element(other = target - item)
in the list and I used a method index()
to do this.
The correct answer as suggested on the internet is as follows:
def twoSum(self, num, target):
length = len(num)
dic = {}
for i in xrange(length):
dic[num[i]] = i
index0 = -1
index1 = -1
for key in xrange(length): #not "for key in dic.values():"
other = target - num[key]
index1 = dic.get(other)
#[1, 2, 3, 4], 4: 2,2 is not the EXPECTED answer.
if index1 and index1 != key:
index0 = key + 1
index1 += 1
break
return index0, index1
This is ok but I don't understand what happened to my code? list.index()
slower than dict.get()
?
source to share
Is it
list.index()
slower thandict.get()
?
In short, yes: list.index()
you need to scan the list to look for an element, while it dict.get()
can do its job at a constant time (that is, in a time that does not depend on the size of the dictionary).
Thus, the first algorithm time complexity is quadratic in the size of the input (written as O (n ^ 2)), while the second algorithm is linear (O (n)).
The following graph illustrates the difference between the two growth rates:
source to share
A get
no sequential lookup is done in the dictionary, basically it applies a hashing algorithm to the key to find the value in memory. index
performs a sequential search, so if the item you are looking for is at the beginning of the list, then it might be faster!
All other things being equal, dictionary searches will be consistent. The actual time depends on things like the algorithm used, which could theoretically vary between python versions. You can also review your test with set()
and possibly collections.OrderedDict
.
You are faced with an important reason for having dictionaries. If you are going to search by position, use a list (or tuple), search by key, then use a dictionary.
source to share