在Python中删除多个列表中的多个项目的最有效方法是什么？

Question

在Python中删除多个列表中的多个项目的最有效方法是什么？

3

我有几个项目列表，没有重复项，每个项目在每个列表中最多只出现一次（通常在所有列表中仅出现一次）。我还有一个要从此数据集中删除项目的列表。如何以最清晰和最有效的方式完成？

我读过在Python中，创建新对象通常比过滤现有对象更简单、更快。但是在我的基本测试中，我没有观察到这一点：

data = [[i*j for j in range(1, 1000)] for i in range(1, 1000)]
kill = [1456, 1368, 2200, 36, 850, 9585, 59588, 60325, 9520, 9592, 210, 3]

# Method 1 : 0.1990 seconds
for j in kill:
    for i in data:
        if j in i:
            i.remove(j)

# Method 2 : 0.1920 seconds
for i in data:
    for j in kill:
        if j in i:
            i.remove(j)

# Method 3 : 0.2790 seconds
data = [[j for j in i if j not in kill] for i in data]

在Python中，哪种方法是最好的使用方式？

- André Nasturas

6

使“kill”成为一个集合，至少。 - Ilja Everilä

2

前两种方法实际上并不正确，除非（如您的示例中）data中不存在重复值。如果数据中不可能存在重复值，则应该使用集合进行交集运算，这将更快，更短，更易于理解，并且比任何其他版本都更加自我解释。 - abarnert

2

使用 timeit 来计时你的代码片段。 - Chris_Rands

2

实际上，由于您没有迭代data的副本，即使没有重复项，前两个也是错误的：您在data中跳过了len(kill)个值，并且根本没有测试它们。因此，只有在从未连续出现可杀死项时才能得到正确答案。 - abarnert

2个回答

1

没有“Python中最好的从列表中删除”的方法。如果有，Python就只有一种方法可以做到这一点。对于不同的问题，有不同的最佳方法，这就是为什么Python有不同的方法来解决它。

正确性比速度更重要。快速得到错误答案是没有用的。（否则，最快的解决方案就是根本不做任何事情。）而您的前两个实现存在两个问题。

首先，您使用remove按值查找并删除元素。除了浪费时间（您刚刚搜索整个列表以查找元素，现在又要再次搜索以查找并删除它），如果有任何重复项，这样做将无法正常工作——只有第一个重复项将被删除。而如果没有重复项，则可能应该使用集合（如果没有重复项但顺序很重要，则应使用OrderedSet），这将使您编写简单且极其快速。

其次，您正在迭代时从列表中删除元素。这会导致您错过一些元素。如果您删除元素2，则所有后续元素都会上移——因此原始元素3现在变成了元素2，但您下一次通过循环检查的是元素3。因此，如果您有两个可杀死的对象排成一行，那么第二个对象将被忽略。您可以通过反向迭代来解决这个问题，但这会让事情变得更加复杂。或者您可以在修改原始列表的同时迭代副本，但这会让事情变得更加复杂，并且需要时间和空间来创建副本。

这两个问题都可以解决，但这也引出了一个重要的问题：前两个版本更容易出现微妙的错误，正如你犯错却没有注意到的事实所证明的那样。

当然，修复这些问题可能会使前两个版本变得稍微慢一点，而不是更快。

即使您解决了这些问题，改变一个对象并不等同于创建一个新对象。如果其他人引用了相同的列表，他们将在前两个版本中看到更改，但在最后一个版本中仍将保留他们预期的列表。如果那个其他人是在另一个线程上的代码，可能同时迭代该列表，这会让事情变得更加复杂。有时您想要第一种行为，有时则需要第二种行为。您可以在任何一个版本上添加更多复杂性以获得相反的效果（例如，将理解赋值给整个列表的切片，而不仅仅是重新绑定名称），但通常直接编写所需的版本更简单。

此外，理解版可以轻松地更改为按需仅执行任务的迭代版本（只需将方括号中的一个或两个集合更改为括号）。而且它适用于任何可迭代对象，不仅限于列表。通过将算法重写为一系列迭代器转换链，您通常可以在更高层次上获得巨大的性能优势和/或简化，从而无需在内存中保留整个数据集。但有时，多次传输或随机访问模式可以带来巨大的性能或简化效益，因此列表要好得多。这将决定您想要哪种实现方式来编写此代码片段。

还有一个空间差异。理解需要线性的临时空间，而不是常数空间，但另一方面，由于Python增长和缩小列表的方式，它可以使你在内存中留下更小的最终结果。(如果这很重要，你需要测试一下——语言甚至不能保证列表缩小它们的存储；它们如何缩小取决于每个实现。)

最后，我们谈论的是一个相当小的差异。如果这在您的代码中很重要，那么忽略其他可能会带来更大改进的选项可能更加重要。如果您可以使用一组集合而不是一组列表，则差异将是巨大的。如果不能，请至少将kill设置为集合，可以加快速度，您肯定可以这样做。使用numpy可能会带来数量级的改进。仅仅在PyPy中运行现有代码可能会使其加速，而且工作量要小得多，几乎与numpy一样。或者您可能需要为内部循环编写C扩展程序（这只是将相同的代码放入.pyx文件并进行Cython化的问题）。如果这些事情中没有一个值得花费数量级或更好的努力，那么为什么要为了50％的改进而投入已经投入的时间呢？

给这些方法加上一些实际数字：

方法1：140毫秒
改进后的方法1：193毫秒
方法3：190毫秒
在PyPy中的方法3：21.6毫秒
[i - kill for i in data]，其中data是一个集合列表，kill是一个集合：20.6毫秒
data[~np.isin(data, kill)]，其中data是一个np.array：26.6毫秒

（我还在Python 2.7中尝试了相同的测试；方法3大约慢30％，方法4慢15％，而其他方法几乎相同。）

作为一个附注，您没有向我们展示如何测试此代码，测试也很容易出现微妙的错误。即使您使用了timeit，仍然需要确保每次都针对原始列表运行，而不是针对已经过滤的相同列表重复运行代码（这意味着第一个rep测试正确的情况，其他99999个reps测试没有可杀死项的不同情况）。

- abarnert

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- FHTMitchell · Accepted Answer

https://wiki.python.org/moin/TimeComplexity

remove的时间复杂度为O(n)，因为它首先通过线性搜索列表，然后如果找到它，那么被删除对象后面的每个元素在内存中都会向左移动一个位置。由于这个原因，remove是一项相当昂贵的操作。

因此，从长度为N的列表中删除M个项目变成了O(N*M)

对于列表来说，in也是O(n)，因为我们需要按顺序搜索整个列表。因此，使用过滤器构建新列表也是O(N*M)。但是，对于集合来说，in是O(1)的，因为哈希使得我们的过滤器的时间复杂度为O(N)

因此，最好的解决方案是（为了简单起见，我只使用了一个平坦的列表，而没有嵌套）

def remove_kill_from_data(data, kill):
    s = set(kill)
    return [i for i in data if i not in kill]

如果您不关心保持顺序，这将更快（由于在C级别完成，仍然是O(N)）。

def remove_kill_from_data_unordered(data, kill):
    s = set(kill)
    d = set(data)
    return d - s

将其应用于您的列表之中

kill_set = set(kill)
[remove_kill_from_data(d, kill_set) for d in data]

一些定时（每个从静态数据首先复制）

%timeit method1(data, kill)
210 ms ± 769 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit method2(data, kill)
208 ms ± 2.89 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit method3(data, kill)
272 ms ± 1.28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit method4(data, kill)  # using remove_kill_from_data
69.6 ms ± 1.33 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit method5(data, kill) # using remove_kill_from_data_unordered
59.5 ms ± 3.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)