在Python中，最有效的推入和弹出列表的方法是什么？

Question

在Python中，我如何编写代码来移除列表的最后一个元素并将新元素添加到开头 - 以尽可能快的速度运行？

有很好的解决方案涉及使用append、rotate等方法，但不一定都能转换为快速执行。

- D.Jordan

---

也许您可以给我们提供一个示例，说明您所解释的方法，并展示不同列表大小下所需的时间长短的图表。目前，您的问题似乎缺乏努力和有点宽泛。 - Mandera

使用列表已经是低效的了。你应该选择一种专门设计用于这种访问的数据结构，比如collections.deque。（另外，“push”和“pop”这些词通常用于栈，而不是像你想要的FIFO队列。） - user2357112

感谢(user2357112)澄清列表本质上是低效的。 - D.Jordan

是的 - 我明白在其他情况下，列表可能是正确的工具（并且使用起来更清晰）。在其他语言中（例如Java），列表的等效物（即数组）被用作堆栈，并具有特定于此目的的堆栈弹出和推入方法。 - D.Jordan

啊，是的 - 我记错了。 - D.Jordan

Answer 1

不要使用列表。

列表仅能在其末尾快速插入和删除项目。您将使用pop(-1)和append，从而得到一个栈。

相反，请使用collections.deque，它专为高效地添加和删除元素于两端而设计。处理双端队列的“前面”时，请使用popleft和appendleft方法。请注意，“deque”代表“双端队列”，发音为“deck”。

- Blckknght

---

谢谢 - 这是一个有帮助的答案的典范。 - D.Jordan

Answer 2

L = [1, 2, 3]
L.pop() # returns 3, L is now [1, 2]
L.append(4) # returns None, L is now [1, 2, 4]
L.insert(0, 5) # returns None, L is now [5, 1, 2, 4]
L.remove(2) # return None, L is now [5, 1, 4]
del(L[0]) # return None, L is now [1, 4]
L.pop(0) # return 1, L is now [4]

- Eeshaan

Answer 3

我为您运行了一些基准测试，以下是结果。

简而言之，您可能想使用deque。否则，insert/append或pop/del都可以。

在末尾添加

from collections import deque
import perfplot

# Add to end

def use_append(n):
    "adds to end"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    a.append(7)
    return 1

def use_insert_end(n):
    "adds to end"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    a.insert(len(a),7)
    return 1

def use_add_end(n):
    "adds to end"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    a = a + [7]
    return 1

perfplot.show(
    setup=lambda n: n,  # or simply setup=numpy.random.rand
    kernels=[
        lambda a: use_append(a),
        lambda a: use_insert_end(a),
        lambda a: use_add_end(a),
    ],
    labels=["use_append", "use_insert_end", "use_add_end"],
    n_range=[2 ** k for k in range(15)],
    xlabel="len(a)",
)

从末尾移除

# Removing from the end

def use_pop(n):
    "removes from end"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    a.pop()
    return 1

def use_del_last(n):
    "removes from end"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    del(a[-1])
    return 1

def use_index_to_end(n):
    "removes from end"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    a = a[:-1]
    return 1

perfplot.show(
    setup=lambda n: n,
    kernels=[
        lambda a: use_pop(a),
        lambda a: use_del_last(a),
        lambda a: use_index_to_end(a),
    ],
    labels=["use_pop", "use_del_last", "use_index_to_end"],
    n_range=[2 ** k for k in range(20)],
    xlabel="len(a)",
)

在开头添加

# Add to beginning

def use_insert(n):
    "adds to beginning"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    a.insert(0,7)
    return 1

def use_deque_appendleft(n):
    "adds to beginning"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    a = deque(a)
    a.appendleft(7)
    return 1

def use_add_start(n):
    "adds to beginning"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    a = [7] + a
    return 1

perfplot.show(
    setup=lambda n: n,  # or simply setup=numpy.random.rand
    kernels=[
        lambda a: use_insert(a),
        lambda a: use_deque_appendleft(a),
        lambda a: use_add_start(a),
    ],
    labels=["use_insert", "use_deque_appendleft","use_add_start"],
    n_range=[2 ** k for k in range(15)],
    xlabel="len(a)",
)

从开头删除

# Remove from beginning

def use_del_first(n):
    "removes from beginning"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    del(a[0])
    return 1


def use_deque_popleft(n):
    "removes from beginning"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    a = deque(a)
    a.popleft()
    return 1


def use_index_start(n):
    "removes from beginning"
    a = [1,2,3,4,5,6,7,8,9,10]*n
    a = a[1:]
    return 1


perfplot.show(
    setup=lambda n: n,  # or simply setup=numpy.random.rand
    kernels=[
        lambda a: use_del_first(a),
        lambda a: use_deque_popleft(a),
        lambda a: use_index_start(a),
    ],
    labels=["use_del_first", "use_deque_popleft", "use_index_start"],
    n_range=[2 ** k for k in range(15)],
    xlabel="len(a)",
)

---

编辑

这些结果需要谨慎对待。由于perfplot的工作方式，删除方法将被运行多次，而设置仅运行一次。因此，列表（或deque）需要在每个函数中本地生成，这会增加运行时间。

我已修改下面的添加方法，并针对deque运行了一个单独的比较，以比较在函数内部生成列表的影响。

Deque设置差异

def gen_deque(n):
    a = [1,2,3,4,5,6,7,8,9,10]*n if n > 0 else [1,2,3]
    return deque(a)


def use_deque_appendleft(a):
    "adds to beginning"
    a.appendleft(7)
    return 1


def use_deque_appendleft_original(a):
    "adds to beginning"
    a = [1,2,3,4,5,6,7,8,9,10]*(len(a)//10)
    a = deque(a)
    a.appendleft(7)
    return 1

perfplot.show(
    setup=lambda n: gen_deque(n),  # or simply setup=numpy.random.rand
    kernels=[
        lambda a: use_deque_appendleft(a),
        lambda a: use_deque_appendleft_original(a),
    ],
    labels=["use_deque_appendleft", "use_deque_appendleft_original"],
    n_range=[2 ** k for k in range(15)],
    xlabel="len(a)",
)

添加到末尾

# Add to end

def gen_data(n):
    return [1,2,3,4,5,6,7,8,9,10]*n if n > 0 else [1,2,3]

def use_append(a):
    "adds to end"
#     a = [1,2,3,4,5,6,7,8,9,10]*n
    a.append(7)
    return 1

def use_insert_end(a):
    "adds to end"
#     a = [1,2,3,4,5,6,7,8,9,10]*n
    a.insert(len(a),7)
    return 1

def use_add_end(a):
    "adds to end"
#     a = [1,2,3,4,5,6,7,8,9,10]*n
    a = a + [7]
    return 1

perfplot.show(
    setup=lambda n: gen_data(n),  # or simply setup=numpy.random.rand
    kernels=[
        lambda a: use_append(a),
        lambda a: use_insert_end(a),
        lambda a: use_add_end(a),
    ],
    labels=["use_append", "use_insert_end", "use_add_end"],
    n_range=[2 ** k for k in range(15)],
    xlabel="len(a)",
)

添加到开头

# Add to beginning

def gen_data(n):
    return [1,2,3,4,5,6,7,8,9,10]*n if n > 0 else [1,2,3]


def use_insert(a):
    "adds to beginning"
    a.insert(0,7)
    return 1

def use_deque_appendleft(a):
    "adds to beginning"
    a = deque(a)
    a.appendleft(7)
    return 1

def use_add_start(a):
    "adds to beginning"
    a = [7] + a
    return 1

perfplot.show(
    setup=lambda n: gen_data(n),  # or simply setup=numpy.random.rand
    kernels=[
        lambda a: use_insert(a),
        lambda a: use_deque_appendleft(a),
        lambda a: use_add_start(a),
    ],
    labels=["use_insert", "use_deque_appendleft","use_add_start"],
    n_range=[2 ** k for k in range(5)],
    xlabel="len(a)",
)

结论

插入和追加的性能相似，使用双向队列似乎比插入性能更好。至于 del / pop / 双向队列的 popleft，看起来 del 和 pop 的性能相似，但考虑到在每个函数中生成列表/双向队列的开销来使用 perfplot，很难确定 deque 的 popleft 是否更好。

- bug_spray

---

你在这里测量的主要不是花费在 [1,2,3,4,5,6,7,8,9,10]*n 上的时间吗？ - Blckknght

嗯，你几乎想要 setup=lambda n: [1,2,3,4,5,6,7,8,9,10]*n，但那对于 deque 情况没有帮助。对于这些情况，您需要在设置中设置 deque，并在函数中执行弹出操作，我不确定这是否可以与 perfplot 一起使用。无论如何，您没有看到 popleft 和 del a[0] 之间的任何区别的原因是 O(1) 的 deque 弹出被埋藏在 O(N) 的代码构建列表并将其转换为 deque 下面。 - Blckknght

a = deque(a) 有什么重要性吗？ - bug_spray

是的，这也是O(N)。 - Blckknght

听起来设置只运行一次，函数不应该直接修改输入。我不确定 perfplot 是否能轻松帮助我们解决这个问题，因为我们想要测试的是直接修改输入的性能。 - Blckknght

Answer 4

你可以使用 Python 列表对象的 insert 方法。

l = [1, 2, 3]
#lets insert 10 at biggining, which means at index 0
l.insert(0, 10)
print(l) # this will print [10, 1, 2, 3]

- Alok

---

你可以这样做，但效率不高。 - glglgl

谢谢glglgl - 这是非常有帮助的答案。 - D.Jordan