如何在Python短列表中添加前缀？

Question

list.append()将一个元素添加到列表的末尾。 这篇文章解释了由于性能问题，在大型列表中不存在list.prepend()。 对于短列表，如何在列表开头添加一个值？

- hurrymaplelad

---

从计算时间上来看，new_list = [x] + your_list 比 your_list.insert(x) 效率低吗？ - Charlie Parker

Answer 1

s.insert(0, x)形式是最常见的。

无论何时看到它，都应考虑使用collections.deque而不是列表。在deque中前置元素以常量时间运行，而在列表中前置元素以线性时间运行。

- Raymond Hettinger

---

为什么这样说呢？每当你遇到这种情况时，可能是考虑使用 collections.deque 而不是 list。 - Mattwmaster58

如果你在一个列表前插入元素，Python 必须将所有其他的元素向前移动一个位置，列表无法“在前面腾出空间”。collections.deque（双端队列）支持在前面“腾出空间”，在这种情况下速度更快。 - fejfo

@fejfo，我认为该评论应该是答案的一部分。 - zrajm

从计算时间的角度来看，new_list = [x] + your_list 比 your_list.insert(x) 效率低吗？ - Charlie Parker

@CharlieParker 是的，创建一个新列表会更不高效，因为所有对象的引用计数都必须更新。否则，复制工作量是相似的。 - Raymond Hettinger

Answer 2

这将创建一个新的列表，其中x被放在列表的开头，而不是修改现有的列表：

new_list = [x] + old_list

- Nil Geisweiller

---

你所观察到的并不是将元素添加至列表的动作，而是创建了一个新的列表。因此这一动作根本不能满足问题要求。 - Chris Morgan

虽然它不能完全回答问题，但它可以使问题更加完整，这也是本网站存在的目的。感谢您的评论，您说得对，但当人们搜索这个问题时，看到这个信息会很有帮助。 - dave4jr

如果您想将一个列表添加到另一个列表的开头，使用 insert 方法可能无法按预期工作。但是这个方法可以！ - gota

你的代码 your_list = [x] + your_list 有什么问题吗？这不会创建一个新的列表吗？ - lightbox142

@lightbox142 它将创建一个新的列表并将其分配给your_list。 - Ataxias

从计算时间的角度来看，new_list = [x] + your_list 是否比 your_list.insert(x) 的效率低？ - Charlie Parker

Answer 3

如何在Python中向一个短列表添加元素？

通常情况下，您不需要重复在Python中向列表前面添加元素。

如果列表较短并且您不需要频繁进行添加，那么可以使用以下方法：

list.insert

可以使用list.insert方法来实现。

list.insert(0, x)

但这种方法效率低下，因为在Python中，一个list是一个指针数组，Python现在必须将列表中的每个指针向下移动一个位置，以便将指向您的对象的指针插入到第一个插槽中，所以这对于相当短的列表才真正有效，正如您所说。

以下是从CPython源代码中获取的代码片段，您可以看到，我们从数组的末尾开始，每插入一个元素就将其后面的所有元素向下移动一位：

for (i = n; --i >= where; )
    items[i+1] = items[i];

如果你想要一个在前面添加元素高效的容器/列表，那么你需要一个链表。Python 有一个双向链表，可以快速插入开头和结尾 - 它被称为 deque。

deque.appendleft

collections.deque 拥有许多与列表相似的方法。但是 list.sort 是一个例外，使得 deque 明显不能完全替代list。

>>> set(dir(list)) - set(dir(deque))
{'sort'}

deque还有一个appendleft方法（以及popleft）。deque是双端队列和双向链表-无论长度如何，在前面添加东西始终需要相同的时间。在大O符号表示法中，相对于列表的O(n)时间，它只需要O(1)时间。以下是用法：

>>> import collections
>>> d = collections.deque('1234')
>>> d
deque(['1', '2', '3', '4'])
>>> d.appendleft('0')
>>> d
deque(['0', '1', '2', '3', '4'])

deque.extendleft

deque 的 extendleft 方法也很重要，它可以迭代地在左侧添加元素：

>>> from collections import deque
>>> d2 = deque('def')
>>> d2.extendleft('cba')
>>> d2
deque(['a', 'b', 'c', 'd', 'e', 'f'])

请注意，每个元素将逐个插入到列表的最前面，因此实际上会颠倒它们的顺序。

list与deque的性能比较

首先，我们进行一些迭代插入操作：

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')

并且性能（通过调整每次试验的运行次数来抵消更多prepends的较长运行时间 - repeat默认进行三次试验）：

compare_prepends(20, 1_000_000)
compare_prepends(100, 100_000)
compare_prepends(500, 100_000)
compare_prepends(2500, 10_000)

>>> 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

deque比list更快。随着列表变得越来越长，deque的表现会越来越好。如果您可以使用deque的extendleft功能，那么这可能是最佳性能的方法。

如果您必须使用列表，请记住对于小型列表，list.insert速度更快，但对于较大的列表，使用切片符号插入将更快。

不要在列表前添加元素

列表应该附加到而不是在前面添加元素。如果您遇到这种需要在前面添加元素的情况，可能会影响代码性能，要么切换到deque，要么如果可以颠倒语义并实现相同的目标，则反转列表并附加。

通常应避免在内置的Python list对象前添加元素。

- Russia Must Remove Putin

---

从计算时间的角度来看，new_list = [x] + your_list 比 your_list.insert(x) 效率低吗？ - Charlie Parker

是的。它们在语义上是不同的 - 第一个创建了两个新列表并丢弃了只有 x 的短列表，而第二个则直接在原始列表中进行了变异。在计算方面，我预计语义相似的部分会有类似的性能 - 并且对于第一个来说，为新列表分配空间会产生更大的性能损失。通常我能够通过仅将元素附加到列表来避免可变性问题。如果我需要一个通用算法（例如来自 Haskell）来改变列表开头的值，我可能会反转它以从末尾开始工作。 - Russia Must Remove Putin

your_list.insert(0, x)必须将your_list中的每个元素向上移动一个位置，从而实现与[x] + your_list相同的复制。 - chepner

Answer 4

如果有人像我一样遇到这个问题，这里是我对所提出方法的性能测试：

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

正如您所看到的，insert 和切片赋值比显式添加快近两倍，结果非常接近。正如Raymond Hettinger所指出的那样，insert 是更常见的选项，而我个人更喜欢使用这种方法来在列表前面添加元素。

- Alexey Milogradov

---

@Dakkaron，我认为你对此有误。许多来源引用list.insert的线性复杂度，例如这张不错的表格，并且由提问者提供的合理解释也暗示着线性复杂度。我怀疑CPython在前两种情况下正在重新分配列表中每个元素的内存，因此这三种情况可能都具有线性复杂度。不过，我并没有查看代码或自己进行测试，如果这些来源是错误的，那么很抱歉。Collections.deque.appendleft确实具有你所说的线性复杂度。 - T.C. Proctor

@Dakkaron 不是真的，所有这些操作的复杂度都是相等的。虽然 .insert 和 [0:0] = [0] 可以 原地 进行，但它们仍然需要重新分配整个缓冲区。 - juanpa.arrivillaga

这些基准测试结果不好。初始列表应在单独的设置步骤中创建，而不是作为计时本身的一部分。最后一个测试创建了一个长度为1000001的新列表，因此与另外两个原地变异版本进行比较是没有可比性的。 - wim

你修复了测试吗？这些测试不可靠，正如Wim所说。 - Charlie Parker

Answer 5

在我看来，在Python中将一个元素或列表添加到另一个列表的最优雅和惯用的方法是使用扩展运算符 *（也称为解压运算符）。

在我看来，在Python中将一个元素或列表添加到另一个列表的最优雅和惯用的方法是使用扩展运算符 *（也称为解压运算符），

# Initial list
l = [4, 5, 6]

# Modification
l = [1, 2, 3, *l]

修改后的列表为[1, 2, 3, 4, 5, 6]

我还喜欢使用运算符+简单地将两个列表组合在一起，如下所示：

# Prepends [1, 2, 3] to l
l = [1, 2, 3] + l

# Prepends element 42 to l
l = [42] + l

我不喜欢另一种常见的方法l.insert(0, value)，因为它需要一个魔法数字。此外，insert()只允许添加一个元素，然而上述方法对于添加单个或多个元素具有相同的语法。

- jose.angel.jimenez

---

从计算时间的角度来看，new_list = [x] + your_list 比 your_list.insert(x) 效率低吗？ - Charlie Parker

怎么样？：微笑：在没有我的辩护律师在场的情况下，我唯一会说的就是“过早优化是万恶之源”。正如我回答的第一段所述，我指的是连接两个列表的惯用方式。 - jose.angel.jimenez

Answer 6

让我们来介绍4种方法

1. 使用insert()函数

>>> 
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> l.insert(0, 5)
>>> l
[5, 0, 1, 2, 3, 4]
>>> 

2. 使用 [] 和 +

>>> 
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> l = [5] + l
>>> l
[5, 0, 1, 2, 3, 4]
>>> 

3. Using Slicing

>>> 
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> l[:0] = [5]
>>> l
[5, 0, 1, 2, 3, 4]
>>> 

4. 使用 collections.deque.appendleft() 方法

>>> 
>>> from collections import deque
>>> 
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> l = deque(l)
>>> l.appendleft(5)
>>> l = list(l)
>>> l
[5, 0, 1, 2, 3, 4]
>>> 

- Prabhav Rajeev

---

您的回答精辟地总结了所有选项，但没有回答所问的问题。请提供一个连贯的答案。 - Epsi95

作为对旧问题的新回答，您应该提供新的见解或信息。这个答案并没有回答原来的问题，只是重复了其他答案中已经存在的信息。 - snakecharmerb

从计算时间的角度来看，new_list = [x] + your_list 比 your_list.insert(x) 更低效吗？ - Charlie Parker

Answer 7

我会使用Python>=3.0快速实现某些操作。

list=[0,*list]

在我看来，这可能不是最高效的方式，但它是最符合Python风格的。

- Jérémy

Answer 8

对于一个小列表，您可以使用insert（）方法将值添加到列表的开头：

my_list = [2, 3, 4]
my_list.insert(0, 1)

然而，对于大型列表，使用双端队列(deque)可能比使用列表(list)更有效：

from collections import deque

my_list = deque([2, 3, 4])
my_list.appendleft(1)

双端队列是一种数据结构，支持高效的前置和后置操作，并且通常比列表在大型数据结构中更快。

- SyntaxNavigator