CODEWITHSUNDEEP
pythondata-structures
Scott
Scott

Reputation: 5263

Is a list or dictionary faster in Python?

How much of a difference are these two as far as performance?

tmp = []
tmp.append(True)
print tmp[0]

And

tmp = {}
tmp[0] = True
print tmp[0]

Upvotes: 5

Views: 5418

Answers (4)

Dirk Roorda
Dirk Roorda

Reputation: 111

The answer that concluded that the dict is the winner is wrong.

Lists are faster than dicts (but not much).

To add items to dicts takes 1.5 x as much time as to lists.

To look up values from dicts takes 1.3 x as much time as from lists.

One should separate the performance for growing the list/dict from the performance of looking up items from the list/dict.

More importantly, the number of elements present might influence the efficiency of adding new elements, especially for dicts.

So, it is better to let the list/dict grow to a big number of elements, and then measure the lookup of all those elements.

Like this

from timeit import timeit
tmpList = []
tmpDict = {}

timeListAdd = timeit("""
for i in range(1000000):
    tmpList.append(True)
""", globals=locals(), number=1)
print(timeListAdd)

0.08886219099999959

timeDictAdd = timeit("""
for i in range(1000000):
    tmpDict[i]= True
""", globals=locals(), number=1)
print(timeDictAdd)

0.1336365199999996

timeListAccess = timeit("""
for i in range(1000000):
    tmpList[i]
""", globals=locals(), number=1)
print(timeListAccess)

0.06501517400000001

timeDictAccess = timeit("""
for i in range(1000000):
    tmpDict[i]
""", globals=locals(), number=1)
print(timeDictAccess)

0.08099801200000023

By the way, there is a better way to create these structures if you know all the elements at creation time:

timeListCreate = timeit("""tmpList = [True for i in range(1000000)]""", globals=locals(), number=1)
print(timeListCreate)

0.03953780500000903

timeDictCreate = timeit("""tmpDict = {i: True for i in range(1000000)}""", globals=locals(), number=1)
print(timeDictCreate)

0.0972781530000475

Upvotes: 0

John Y
John Y

Reputation: 14559

Not only is micro-optimization usually pointless in general, I find it is especially difficult and arcane for Python in particular. It is very easy to actually make your code simultaneously slower and more complicated. See this Stack Overflow question for an example where the simplest, clearest, and shortest Python solutions also turned out to be the fastest.

As others have shown with actual tests, the speed difference between your two choices is quite small. What is less small is the semantic difference. Lists and dictionaries are not merely two implementations of the same concept, but are intended for different uses. Pick the one which better fits your use.

Upvotes: 7

Luke Schafer
Luke Schafer

Reputation: 9275

they are equitable in my testing

Upvotes: -3

Alex Martelli
Alex Martelli

Reputation: 882851

The timeit module in the standard library is designed just to answer such questions! Forget the print (which would have the nasty side effect of spewing stuff to your terminal;-) and compare:

$ python -mtimeit 'tmp=[]; tmp.append(True); x=tmp[0]'
1000000 loops, best of 3: 0.716 usec per loop
$ python -mtimeit 'tmp={}; tmp[0]=True; x=tmp[0]'
1000000 loops, best of 3: 0.515 usec per loop

So, the dict is the winner -- by 0.2 microseconds...!-)

Upvotes: 25

Related Questions