import timeit
from collections import deque
def list_insert_0(prepends: int):
l = []
for i in range(prepends):
l.insert(0, i)
def list_slice_insert(prepends):
l = []
for i in range(prepends):
l[:0] = [i] # semantically same as list.insert(0, i)
def list_add(prepends):
l = []
for i in range(prepends):
l = [i] + l # caveat: new list each time
def deque_appendleft(prepends):
d = deque()
for i in range(prepends):
d.appendleft(i) # semantically same as list.insert(0, i)
def deque_extendleft(prepends):
d = deque()
d.extendleft(range(prepends)) # semantically same as deque_appendleft above
和一个用于分析的函数,这样我们就可以公平地比较一系列使用中的所有操作:
def compare_prepends(n, runs_per_trial):
results = {}
for function in (
list_insert_0, list_slice_insert,
list_add, deque_appendleft, deque_extendleft,
):
shortest_time = min(timeit.repeat(
lambda: function(n), number=runs_per_trial))
results[function.__name__] = shortest_time
ranked_methods = sorted(results.items(), key=lambda kv: kv[1])
for name, duration in ranked_methods:
print(f'{name} took {duration} seconds')
>>> compare_prepends(20, 1_000_000)
deque_extendleft took 0.6490256823599339 seconds
deque_appendleft took 1.4702797569334507 seconds
list_insert_0 took 1.9417422469705343 seconds
list_add took 2.7092894352972507 seconds
list_slice_insert took 3.1809083241969347 seconds
>>> compare_prepends(100, 100_000)
deque_extendleft took 0.1177942156791687 seconds
deque_appendleft took 0.5385235995054245 seconds
list_insert_0 took 0.9471780974417925 seconds
list_slice_insert took 1.4850486349314451 seconds
list_add took 2.1660344172269106 seconds
>>> compare_prepends(500, 100_000)
deque_extendleft took 0.7309095915406942 seconds
deque_appendleft took 2.895373275503516 seconds
list_slice_insert took 8.782583676278591 seconds
list_insert_0 took 8.931685039773583 seconds
list_add took 30.113558700308204 seconds
>>> compare_prepends(2500, 10_000)
deque_extendleft took 0.4839253816753626 seconds
deque_appendleft took 1.5615574326366186 seconds
list_slice_insert took 6.712615916505456 seconds
list_insert_0 took 13.894083382561803 seconds
list_add took 72.1727528590709 seconds
Python 2.7.8
In [1]: %timeit ([1]*1000000).insert(0, 0)
100 loops, best of 3: 4.62 ms per loop
In [2]: %timeit ([1]*1000000)[0:0] = [0]
100 loops, best of 3: 4.55 ms per loop
In [3]: %timeit [0] + [1]*1000000
100 loops, best of 3: 8.04 ms per loop
7条答案
按热度按时间nr7wwzry1#
s.insert(0, x)
形式是最常见的。无论何时你看到它,也许是时候考虑使用collections.deque而不是list了。前置到一个deque运行在常数时间内,前置到一个list运行在线性时间内。
smdncfj32#
这将创建一个新列表,并在其前面添加
x
,而不是修改现有列表:x9ybnkn63#
在python短列表前面添加前缀的惯用语法是什么?
在Python中,通常不希望重复地在列表前面添加前缀。
如果清单***短***,而且你做得不多......那么好吧。
∮ ∮ ∮ ∮ ∮一个月一个月
list.insert
可以这样使用。但这是低效的,因为在Python中,
list
是一个指针数组,Python现在必须获取列表中的每一个指针,并将其向下移动一个,以将指向对象的指针插入到第一个槽中,所以这实际上只对相当短的列表有效,正如你所问的。下面是CPython源代码的一个片段,在这里实现了这个功能--正如您所看到的,我们从数组的末尾开始,每插入一次,就将所有内容向下移动一个:
如果你想要一个在元素前面高效的容器/列表,你需要一个链表,Python有一个双向链表,它可以在开始和结束时快速插入--它被称为
deque
。一米四分一秒
collections.deque
有许多列表的方法。list.sort
是一个例外,使得deque
绝对不能完全Liskov替代list
。deque
也有一个appendleft
方法(以及popleft
)。deque
是一个双端队列和一个双链表-无论长度如何,它总是花费相同的时间来准备某个东西。在大O符号中,O(1)与列表的O(n)时间。下面是用法:一米十三分一秒
同样相关的是deque的
extendleft
方法,该方法迭代地预先考虑:请注意,每个元素将一次前置一个元素,从而有效地颠倒了它们的顺序。
list
与deque
的性能对比首先,我们设置一些迭代前置:
和一个用于分析的函数,这样我们就可以公平地比较一系列使用中的所有操作:
和性能(向下调整每次试验的运行次数,以补偿更多前置项的更长运行时间-
repeat
默认情况下执行三次试验):双端队列的速度要快得多。当列表变长时,双端队列的性能会更好。如果你能使用双端队列的
extendleft
,你可能会得到最好的性能。如果必须使用列表,请记住,对于小列表,
list.insert
工作得更快,但对于较大列表,使用切片表示法插入会更快。不添加到列表前面
列表应该被追加,而不是被前置。如果你遇到这种前置会损害代码性能的情况,要么切换到双端队列,要么,如果你可以反转你的语义并达到同样的目的,反转你的列表并追加。
一般来说,要避免在内置Python
list
对象前面添加前缀。nszi6y054#
如果有人像我一样发现了这个问题,下面是我对所提出的方法的性能测试:
正如你所看到的,
insert
和slice赋值几乎是显式加法的两倍,并且结果非常接近,正如Raymond Hettinger所指出的,insert
是更常见的选项,我个人更喜欢这种方式来前置到列表中。snz8szmq5#
在我看来,在Python中,将一个元素或列表前置到另一个列表的最优雅和最惯用的方法是使用扩展操作符 *(也称为解包操作符),
其中修改后的结果列表为
[1, 2, 3, 4, 5, 6]
我还喜欢用操作符+简单地组合两个列表,如图所示,
我不喜欢另一种常用的方法
l.insert(0, value)
,因为它需要一个幻数,而且insert()
只允许前置一个元素,而上面的方法对于前置一个元素或多个元素具有相同的语法。mwg9r5ms6#
让我们看一下4种方法
1.使用插入()
1.使用[]和+
1.使用切片
1.使用集合.deque.appendleft()
5jvtdoz27#
我会在python〉= 3.0中做一些非常快的事情
这也许不是最有效的方法,但在我看来,这是最Python的方法。