Tuesday, July 7, 2015

collections.deque random access is O(n)

>>> r = range(int(1e6))
>>> li = list(r)
>>> de = collections.deque(r)
>>> pos = len(de) / 2
>>> timeit.timeit(lambda: de[100])
0.1355267132935296
>>> timeit.timeit(lambda: li[100])
0.14215966414053582

Great, list and deque performance are identical.

>>> timeit.timeit(lambda: li[pos])
0.1369839611421071
>>> timeit.timeit(lambda: de[pos])
56.227819584345696

Oops.  O(1) vs O(n).

2 comments:

  1. It's strange, right? If you call directly de[pos] without timeit or lambda, then it doesn't take 56 s.

    ReplyDelete
    Replies
    1. timeit.timeit() by default runs the code 100,000 times in a loop :-)

      Although the difference between 0.14 and 56 is very large, in absolute terms the duration of both operations is way below what we would perceive as instantaneous.

      Delete