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).

3 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
  2. Extra hold assets on UK air terminal pausing and air terminal lodgings with our markdown Saucony Discount Code. These vouchers are on top of our standard locale rate hypothesis saves.

    ReplyDelete