<blockquote>
<h2>What's the idiomatic syntax for prepending to a short python list?</h2>
</blockquote>
<p>在Python中,您通常不希望重复地在列表前面加上前缀。</p>
<p>如果它是短的,而你做的不多。。。那好吧。</p>
<h3><code>list.insert</code></h3>
<p>可以这样使用<code>list.insert</code>。</p>
<pre><code>list.insert(0, x)
</code></pre>
<p>但这是低效的,因为在Python中,<code>list</code>是一个指针数组,Python现在必须获取列表中的每个指针,并将其向下移动一个,以便在第一个槽中插入指向对象的指针,所以这实际上只对较短的列表有效,正如您所要求的那样。</p>
<p>这里有一个代码片段<a href="https://github.com/python/cpython/blob/master/Objects/listobject.c#L311" rel="noreferrer">from the CPython source</a>在这里实现了这一点-如您所见,我们从数组的末尾开始,每次插入时将所有内容向下移动一个:</p>
<pre><code>for (i = n; --i >= where; )
items[i+1] = items[i];
</code></pre>
<p>如果希望容器/列表在元素前加有效的前缀,则需要链接列表。Python有一个双链接列表,它可以快速地插入开头和结尾,称为<code>deque</code>。</p>
<h3><code>deque.appendleft</code></h3>
<p><code>collections.deque</code>有许多列表方法。<code>list.sort</code>是一个例外,使得<code>deque</code>最终不能完全替代<code>list</code>的Liskov。</p>
<pre><code>>>> set(dir(list)) - set(dir(deque))
{'sort'}
</code></pre>
<p><code>deque</code>还有一个<code>appendleft</code>方法(以及<code>popleft</code>)。<code>deque</code>是一个双端队列和一个双链接列表-无论长度如何,预处理某事总是需要相同的时间。在大O表示法中,O(1)与列表的O(n)时间之比。用法如下:</p>
<pre><code>>>> import collections
>>> d = collections.deque('1234')
>>> d
deque(['1', '2', '3', '4'])
>>> d.appendleft('0')
>>> d
deque(['0', '1', '2', '3', '4'])
</code></pre>
<h3><code>deque.extendleft</code></h3>
<p>与此相关的还有deque的<code>extendleft</code>方法,该方法迭代地预先:</p>
<pre><code>>>> from collections import deque
>>> d2 = deque('def')
>>> d2.extendleft('cba')
>>> d2
deque(['a', 'b', 'c', 'd', 'e', 'f'])
</code></pre>
<p>请注意,每个元素将一次添加一个前缀,从而有效地颠倒它们的顺序。</p>
<h3><code>list</code>对<code>deque</code></h3>的性能
<p>首先,我们设置一些迭代的前置:</p>
<pre><code>import timeit
from collections import deque
def list_insert_0():
l = []
for i in range(20):
l.insert(0, i)
def list_slice_insert():
l = []
for i in range(20):
l[:0] = [i] # semantically same as list.insert(0, i)
def list_add():
l = []
for i in range(20):
l = [i] + l # caveat: new list each time
def deque_appendleft():
d = deque()
for i in range(20):
d.appendleft(i) # semantically same as list.insert(0, i)
def deque_extendleft():
d = deque()
d.extendleft(range(20)) # semantically same as deque_appendleft above
</code></pre>
<p>以及性能:</p>
<pre><code>>>> min(timeit.repeat(list_insert_0))
2.8267281929729506
>>> min(timeit.repeat(list_slice_insert))
2.5210217320127413
>>> min(timeit.repeat(list_add))
2.0641671380144544
>>> min(timeit.repeat(deque_appendleft))
1.5863927800091915
>>> min(timeit.repeat(deque_extendleft))
0.5352169770048931
</code></pre>
<p>德克要快得多。随着名单越来越长,我预计德克会表现得更好。如果您可以使用deque的<code>extendleft</code>,那么您可能会获得最好的性能。</p>