CODEWITHSUNDEEP
pythonperformancecpu-speed
MattTheSnake
MattTheSnake

Reputation: 117

Is it faster to add a key to a dictionary or append a value to a list in Python?

I have an application where I need to build a list or a dictionary and speed is important. Normally I would just declare a list of zeros of the appropriate length and assign values one at a time but I need to be able to check the length and have it still be meaningful.

Would it be faster to add a key value pair to a dictionary or to append a value to a list? The length of the lists and dictionary will usually be small (less than 100) but this isn't always true and in worst case could be much larger.

I could also just have a variable to keep track of where I am in the list if both of these operations are too slow.

Upvotes: 7

Views: 11050

Answers (2)

fantabolous
fantabolous

Reputation: 22696

Another option is a deque: purpose built for fast append and pop (especially popleft).

Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Caveat: read access is slower than list or dict if you're trying to access items in the middle.

However, I was surprised that for adding new items, dict was at least as fast:

python -m timeit -s "from collections import deque; d = deque()" "for i in range(10000000):" " d.append(i)"
1 loop, best of 5: 459 msec per loop

python -m timeit -s "l = list()" "for i in range(10000000):" " l.append(i)"
1 loop, best of 5: 517 msec per loop

python -m timeit -s "d = dict()" "for i in range(10000000):" " d[i] = i"
1 loop, best of 5: 450 msec per loop

Upvotes: 0

saurabh baid
saurabh baid

Reputation: 1877

Best way is to use time() to check your execution time.

In following example dict is slightly faster.

from time import time

st_time = time()
b = dict()
for i in range(1, 10000000):
    b[i] = i

print (time() - st_time)

st_time = time()
a = []
for i in range(1, 10000000):
    a.append(i)

print (time() - st_time)

1.45600008965
1.52499985695

Upvotes: 4

Related Questions