CODEWITHSUNDEEP
python
Xiaowei Liu
Xiaowei Liu

Reputation: 89

Which is more efficient in Python: list.index() or dict.get()

I'm trying to solve a problem on LeetCode. I'm using Python and I made an attempt as follows:

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 whether element(other = target - item) in the list, and I used the index() method for this.

The right answer offered 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

It's OK, but I don't understand what's wrong with my code? Is list.index() slower than dict.get()?

Upvotes: 3

Views: 914

Answers (2)

NPE
NPE

Reputation: 500247

Is list.index() slower than dict.get()?

In a word, yes: list.index() has to scan the list to look for the element, whereas dict.get() can do its job in constant time (i.e. in time that's independent of the size of the dictionary).

Thus the first algorithm's time complexity is quadratic in the size of the input (written as O(n^2)), whereas the second algorithm's is linear (O(n)).

The following graph illustrates the difference between the two rates of growth:

O(n) vs O(n^2)

Upvotes: 7

cdarke
cdarke

Reputation: 44354

A get on a dictionary does not do a sequential search, basically it applies a hashing algorithm to the key to find the value in memory. index does a sequential search, so if the item you are looking for is at the start of the list then it could actually be faster!

All things being equal, a dictionary search will be consistent. The actual time depends on things like the algorithm in use, which in theory can vary between versions of python. You might also like to consider your test using a set() and maybe collections.OrderedDict.

You have stumbled across an important reason for having dictionaries. If you are going to search by position then use a list (or tuple), searching by key then use a dictionary.

Upvotes: 1

Related Questions