按索引删除列表元素是否比按值删除更有效？

Question

在 python 中，假设我们有以下列表： my_list = ['a', 'b', 'c', 'd', ...]

my_list.pop(3) 会比 my_list.remove('d') 更有效率吗？

Answer 1

对于小列表来说并不重要：

[wander@box ~]$ python -m timeit '[1, 2, 3].pop(1)'
10000000 loops, best of 3: 0.167 usec per loop
[wander@box ~]$ python -m timeit '[1, 2, 3].remove(2)'
10000000 loops, best of 3: 0.129 usec per loop

如果您的列表非常大，或者比较列表中的元素需要很长时间，则差异可能更大。删除会比较慢，因为它必须遍历（并比较）所有元素：

[wander@box ~]$ python -m timeit -n 100000 'list(range(1, 100)).pop(98)'
100000 loops, best of 3: 0.916 usec per loop
[wander@box ~]$ python -m timeit -n 100000 'list(range(1, 100)).remove(98)'
100000 loops, best of 3: 2.05 usec per loop

那是整数，比较起来非常快。如果列表中的元素有更有趣的 __eq__ 方法，remove 可能需要很长时间：

class Foo:
    def __eq__(self, other):
        time.sleep(1)
        return False

[Foo(), Foo(), Foo(), Foo(), 20].remove(20)

因此，如果您知道索引，请使用 pop。

Answer 2

根据this answer，这两种方法的复杂度为：

pop     O(n - i)
remove  O(n)

列表长度n和元素索引i。

因此，根据列表的大小，pop 可能在较长的运行上更快。

Answer 3

查看 listpop and listremove 的实际 C 代码（您指的是 CPython，对吧？），您可以看到：

.remove 需要遍历列表（因此按 O(i) 缩放，其中 i 是项目的索引）；
.pop走捷径，如：
- 判断索引是否越界很简单（第 928 行），但 .remove 必须检查整个列表才能找到它的目标（或无法找到目标） );和
- 特殊情况下索引是列表中的最后一项（第 933 行）；
listremove调用了PyObject_RichCompareBool（第2200行），开销比较大，因为需要检查当前索引处的对象是否等于物品;和
两者（除了上面提到的 .pop 的特殊情况）最终委托给 list_ass_slice（第 941 和 2202 行 - 并且没有在后面咯咯笑）一旦合适找到切片位置；这必须将数组其余部分中的项目一起洗牌，所以将是 O(n - i).

在此基础上 .pop 会更快，尤其是对于列表中的最后一项；但是，如果您是从项目本身开始的，并且已经进行了 O(n) 操作并通过丰富的比较来找到它的 .index，那么您在回旋处已经失去了在秋千上的收获。

此外，重新排列数组中剩余的所有内容（即 list_ass_slice）以弥补您删除的内容的操作，.pop 和 .remove 都需要这样做，可能比首先找出要删除的项目要昂贵得多。

请注意，无需深入研究源代码，只需从逻辑上思考每个操作涉及的内容，就可以弄清楚上述几乎所有内容。

按索引删除列表元素是否比按值删除更有效？

Is removing a list element by index more efficient than removing it by value?

python

performance

runtime

python-internals