Why are dictionaries faster than lists in Python?

Question

>>> timeit.timeit('test.append("test")', setup='test = []')
0.09363977164165221
>>> timeit.timeit('test[0] = ("test")', setup='test = {}')
0.04957961010914147

I even tried again with a loop, and the same thing:

>>> timeit.timeit('for i in range(10): test.append(i)', setup='test = []')
1.3737744340367612
>>> timeit.timeit('for i in range(10): test[i] = i', setup='test = {}')
0.8633718070233272

Why is the list slower?

Answer 1

First of all, list.appendand dict.__setitem__O (1) is the middle case. Of course, they will have different coefficients, but in fact there is no reason to say that one or the other will be faster. Odds may also vary depending on implementation details.

Secondly, a fairer comparison would be to remove overhead with attribute resolution:

>>> timeit.timeit('test[0] = ("test")', setup='test = {}')
0.0813908576965332
>>> timeit.timeit('test_append("test")', setup='test = []; test_append = test.append')
0.06907820701599121

Finding a method name in an instance is relatively expensive when you look at an extremely cheap operation, for example append.

, , . - python 3.5.2:

>>> dict_setup = 'import random; test = {random.random(): None for _ in range(1000)}'
>>> list_setup = 'import random; test = [random.random() for _ in range(1000)]; test_append=test.append'
>>> timeit.timeit('test[0] = "test"', setup=dict_setup)
0.06155529400166415
>>> timeit.timeit('test_append("test")', setup=list_setup)
0.057089386998995906