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