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
如果你能走功能性的道路,下面就很清楚了
当然,您并没有将
x
插入到your_list
中,而是创建了一个预先添加了x
的新列表。在Python中,您通常不希望重复地在列表前面加上前缀。
如果它是短的,而你做的不多。。。那好吧。
list.insert
可以这样使用
list.insert
。但这是低效的,因为在Python中,
list
是一个指针数组,Python现在必须获取列表中的每个指针,并将其向下移动一个,以便在第一个槽中插入指向对象的指针,所以这实际上只对较短的列表有效,正如您所要求的那样。这里有一个代码片段from the CPython source在这里实现了这一点-如您所见,我们从数组的末尾开始,每次插入时将所有内容向下移动一个:
如果希望容器/列表在元素前加有效的前缀,则需要链接列表。Python有一个双链接列表,它可以快速地插入开头和结尾,称为
deque
。deque.appendleft
collections.deque
有许多列表方法。list.sort
是一个例外,使得deque
最终不能完全替代list
的Liskov。deque
还有一个appendleft
方法(以及popleft
)。deque
是一个双端队列和一个双链接列表-无论长度如何,预处理某事总是需要相同的时间。在大O表示法中,O(1)与列表的O(n)时间之比。用法如下:deque.extendleft
与此相关的还有deque的
extendleft
方法,该方法迭代地预先:请注意,每个元素将一次添加一个前缀,从而有效地颠倒它们的顺序。
的性能list
对deque
首先,我们设置一些迭代的前置:
以及性能:
德克要快得多。随着名单越来越长,我预计德克会表现得更好。如果您可以使用deque的
extendleft
,那么您可能会获得最好的性能。最常见的是
s.insert(0, x)
形式。不过,无论何时看到它,都可能是考虑使用collections.deque而不是使用列表的时候了。
相关问题 更多 >
编程相关推荐