擅长:python、mysql、java
<p>请注意,如果您经常尝试执行该操作,特别是在循环中,则列表是错误的数据结构。</p>
<p>列表没有针对前面的修改进行优化,<code>somelist.insert(0, something)</code>是一个<a href="https://wiki.python.org/moin/TimeComplexity">O(n) operation</a>。</p>
<p><code>somelist.pop(0)</code>和<code>del somelist[0]</code>也是O(n)操作。</p>
<p>要使用的正确数据结构是来自<code>collections</code>模块的<a href="https://docs.python.org/2/library/collections.html#collections.deque">^{<cd4>}</a>。deques公开了一个类似于列表的接口,但是针对两个端点的修改进行了优化。他们有一个在前面插入的<code>appendleft</code>方法。</p>
<p>演示:</p>
<pre><code>In [1]: lst = [0]*1000
In [2]: timeit -n1000 lst.insert(0, 1)
1000 loops, best of 3: 794 ns per loop
In [3]: from collections import deque
In [4]: deq = deque([0]*1000)
In [5]: timeit -n1000 deq.appendleft(1)
1000 loops, best of 3: 73 ns per loop
</code></pre>