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

Question

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

Basically the answer is **Yes** but that is too short to be an answer. — Steve Barnes, Mar 03 '15 at 06:05

score 2 · Accepted Answer · answered Mar 03 '15 at 06:06

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).

score 0 · Answer 2 · edited May 23 '17 at 11:56

0

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

edited May 23 '17 at 11:56

Community

1
1

answered Mar 03 '15 at 06:09

MONTYHS

926
1
7
30

Getting an item by index from a list is not the same as a "lookup". – jepio Mar 03 '15 at 07:48

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

2 Answers2