collections.deque: why q[9999] is faster than q[-1]?

user_12014965 0
Viewed 90

If I were a programmer writing this functionality, I would implement it as negative means start from right, positive means start from left, which will result in q[-1] much faster than q[9999].

However, as -1 transformed to 1 step from right seems no more time consuming than transform 9999 to 1 step from right, so why does q[-1] is slower than q[9999]?

Thanks

>>> q = collections.deque()
>>> q.extend(range(10000))
>>> %timeit q[-1]
50.7 ns ± 0.195 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
>>> %timeit q[9999]
40.5 ns ± 0.528 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
cpython deque python
1 Answers

If you implement __getitem__ in Python, you receive whatever index the caller used, without modification.

However, under the hood, collections.deque implements the C API sequence protocol, and the C API sequence protocol version of __getitem__ works differently. If you pass in a negative number, Python will add the len of the sequence to your index before passing it to the deque's item retrieval implementation.

With both q[-1] and q[9999], the index the deque receives is 9999, and it has to decide whether to iterate from the left or the right to find the element you asked for. However, q[-1] has an extra layer of overhead first.

user_23571120
Related