Python 中 list 和 deque 性能對比

list 與 deque 的性能對比如下，deque 比 list 快了將近一倍。

In [1]: from collections import deque
In [2]: s = list(range(1000))
In [3]: d = deque(s)
In [4]: s_append, s_pop = s.append, s.pop
In [5]: d_append, d_pop = d.append, d.pop
In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop
In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop

• deque 的 appendleft() 和 popleft() 的時間復雜度為 O(1)
• list 的 insert(0, value) 和 pop() 的時間復雜度為 O(n)

列表追加性能好壞不定，因為它使用了realloc()。

因此，往往在簡單代碼中列表的性能不算太差(因為 realloc 內存分配機制不需要移動數據)，而在實際應用代碼中計時非常慢(因為 realloc 機制會移動所有數據)。

相比之下，deque的附加性能是一致的，因為它從不重新分配內存和移動數據。