CODEWITHSUNDEEP
pythonlistdictionary
Anurag Sharma
Anurag Sharma

Reputation: 5039

Fetching element by index in list is faster than fetching element by key in dictionary

I have the following script to test which is faster

1.Fetching element by index in list, or

2.Fetching element by key in dictionary

import timeit
import random

lis1 = [random.randint(1,10000) for x in xrange(0,10001)]
dict1 = {x:random.randint(1,10000) for x in xrange(0,10001)}

def list_lookup():
    index = random.randint(0,10000)
    x = lis1[index]

def dict_lookup():
    index = random.randint(0,10000)
    x = dict1[index]


def main():
  print timeit.repeat("list_lookup()", "from __main__ import list_lookup",number=1000000)
  print timeit.repeat("dict_lookup()", "from __main__ import dict_lookup",number=1000000)

if __name__ == '__main__':
  main()

It is giving the following output

[1.208083152770996, 1.1942389011383057, 1.1882140636444092]
[1.2461788654327393, 1.2427518367767334, 1.2414629459381104]

Although the difference seems to be negligible but it seems like dictionary look-up takes slightly longer time

Is it because fetching element in dictionary involves 2 steps -- first hashing the key and then fetching the value (second), while in list we are just fetching the value from the memory address of that particular location of the list

Upvotes: 3

Views: 96

Answers (2)

MONTYHS
MONTYHS

Reputation: 924

Lookups in lists are O(n), lookups in dictionaries are amortized O(1), with regard to the number of items in the data structure.

For more info refer this answer Here

Upvotes: 0

shx2
shx2

Reputation: 64298

Three steps actually, it also needs to compare (==) the key it finds with the given key, to make sure it retuns the correct value, and not another value which happen to be mapped to the same bucket.

On top of that, inefficient hashing / collisions can cause further slowness (for this reason, dict lookup is O(N) worst case).

Upvotes: 2

Related Questions