0

How do I remove the same items from a list? Say

A= [1, 2, 3, 8, 7, 8, 8, 7, 6]

And I want to remove all 8 how should I do this? if the number is not in order?

4

3 回答 3

4

最简单的方法是构建一个新列表，其中包含所有不是8. 例如：

B=[item for item in A if item != 8]

如果您真的想就地执行此操作（例如，因为某个其他对象引用了与 相同的列表A，并且您希望该其他对象看到更改），您可以。但这更棘手。例如，如果您按索引删除，您将不得不在某个时候向后退（因为当您删除第一个时8，所有后面 8的 s 都有新的索引，所以您总是必须先删除最后一个）：

indices = [index for index, item in enumerate(A) if item==8]
for index in reversed(indices):
    del A[index]

或者您可以继续尝试remove直到失败，但这既丑陋又缓慢：

while True:
    try:
        A.remove(8)
    except ValueError:
        break

事实上，您通常最好还是创建一个新列表，然后只是变异A为该新列表的副本：

A[:]=[item for item in A if item != 8]

对于性能测试，我针对所有建议的答案运行了此代码。测试的算法有：

  • revind：我在这个答案中的第一个就地算法。
  • whiledel：Chris Barker 的第一个算法。
  • 幻灯片：Chris Barker 的第二种算法（固定版本）。
  • geneexpr：我的最后一个算法，但使用的是genexpr 而不是listcomp。
  • listcomp：我的最后一个算法。
  • filterer：我的最后一个算法，但是使用了过滤器（请注意，这意味着它在 2.x 中构建了一个列表，但在 3.x 中构建了一个类似genexpr 的迭代器）。

请注意，如果您实际上不需要变异（A通常不需要，您可以重新绑定名称），则复制然后变异算法变得更加简单和快捷。但我没有在这里测试。

我也没有完全测试“while True: remove until error”算法，或者 Chris Barker 在评论中建议的变化，因为它们显然会慢得多，不值得测试。然而，一个非常快速的测试表明，变化比预期的慢大约 2 倍，并且在几乎任何测试用例中，两者都比其他任何东西慢几个数量级。

无论如何，测试是从长度为 100K 或 1M（重复次数的 1/10）的随机列表中删除 0，值范围从 0 到 16、256 或 65536（不同的值越少，百分比越高）点击删除）。

如果您使用的是 CPython，则 listcomp 版本总是最快的，尤其是当 N 很大时。在您使用 PyPy 时，当 N 很大而 M 很小时，就地算法可以击败它，但在这种情况下，它们都非常快。花哨的幻灯片算法消除了其他就地算法的二次行为，但对于简单的情况，它也会减慢速度，因此确实没有明显的赢家。（它也是迄今为止最复杂的——这可能是为什么它是唯一一个在第一次尝试时不正确的原因。）如果您绝对确定您只会删除少量副本，并且您正在使用 PyPy，请考虑使用 whiledel 解决方案；在任何其他用例中，或者当您不确定用例时，我会使用 listcomp。

          64-bit python CPython 3.3.0
          16 values    256 values   65536 values
          100K  1000K  100K  1000K  100K  1000K
revind    0.188 17.3   0.085 1.23   0.074 0.080
whiledel  0.324 19.3   0.206 1.36   0.199 0.203
slide     0.091  0.54  0.097 0.54   0.095 0.538
genepxr   0.094  0.11  0.100 0.11   0.099 0.108
listcomp  0.070  0.08  0.073 0.08   0.071 0.079
filterer  0.081  0.09  0.080 0.09   0.835 0.088

          64-bit python CPython 2.7.2
          16 values    256 values   65536 values
          100K  1000K  100K  1000K  100K  1000K
revind    0.198 17.1   0.089 1.23   0.088 0.955
whiledel  0.345 19.8   0.233 1.36   0.234 0.243
slide     0.095  0.54  0.099 0.55   0.095 0.551
genepxr   0.092  0.11  0.097 0.11   0.107 0.116
listcomp  0.091  0.09  0.099 0.08   0.105 0.114
filterer  0.122  0.23  0.132 0.09   0.135 0.150

          64-bit python PyPy 1.9.0 (Python 2.7.2)
          16 values    256 values   65536 values
          100K  1000K  100K  1000K  100K  1000K
revind    0.266 28.5   0.027 1.97   0.018 0.013
whiledel  0.281 30.2   0.023 1.94   0.034 0.009
slide     0.022  0.39  0.015 0.022  0.006 0.018
genepxr   0.089  0.13  0.087 0.154  0.089 0.147
listcomp  0.052  0.08  0.057 0.073  0.052 0.073
filterer  0.054  0.07  0.053 0.078  0.048 0.074

预测幻灯片的性能有点困难。在大 N/小 M 的情况下，您会期望它会吹走 whiledel，但实际上它更慢。但如果你想一想：该算法有效地用 N 个简单副本替换了 M 个线性移动。虽然前者是 O(NM) 而后者是 O(N)，但在 C 中（或者甚至更好的memmove是 inside ）循环的乘数比 Python 中的循环小得多，除非 N/M 否则你不能忽略它是巨大的（此时所有的解决方案都如此之快以至于它几乎无关紧要）。因此，执行 M 个 Python 循环和 NM 个 C 循环可以轻松击败执行 N 个 Python 循环。

于 2013-08-01T22:48:39.607 回答
2

这些答案中的大多数都建议复制数据。如果您的列表足够大，这可能是不受欢迎的。您可以轻松使用

while 8 in A: A.remove(8)

在不复制任何数据的情况下执行此操作。但是，这在二次时间中运行，如果您的列表很大，这也是不可取的。要在线性时间内完成并且不复制任何数据，请使用：

def remove_all_from_list(L, n):
    i = 0
    while i < len(L):
        if L[i] == n:
            del L[i] # Do not increment i here, because L[i] will change
        else:
            i += 1

>>> A = [1, 2, 3, 8, 7, 8, 8, 7, 6]
>>> remove_all_from_list(A, 8)
>>> A
[1, 2, 3, 7, 7, 6]

编辑：@abarnert 提醒我 del L[i] 是 O(N) 所以这实际上是二次的。这是 O(N) 就地解决方案的另一种尝试......

def remove_all_from_list(L, n):
    # indices takes *worse-case* O(N) space, but typical-case much less
    indices = [i for i, x in enumerate(L) if x==n]
    indices_seen = 0
    num_indices = len(indices)
    for i in xrange(len(L)):
        while (indices_seen < num_indices and 
            i + indices_seen == indices[indices_seen]):
            indices_seen += 1
        if i+indices_seen >= len(L):
            break
        L[i] = L[i+indices_seen]            
    L[-indices_seen:] = []

这将在最后完成所有改组，因此每个元素最多移动一次。我意识到这将花费与 abarnert 的复制方法一样多的时间。我只是想办法在你有一个非常大的列表的情况下减少内存使用。

最终编辑：速度测试（不如@abarnert 全面）

import random
L = range(30)*10000
random.shuffle(L)
from copy import copy

for fn in [remove_1, remove_2, remove_3, remove_4, remove_5, remove_6]:
    print fn.__name__
    %timeit fn(copy(L), 8)

remove_1 # listcomp
10 loops, best of 3: 39.1 ms per loop
remove_2 # revind
1 loops, best of 3: 1.7 s per loop
remove_3 # try: remove; except: break
1 loops, best of 3: 65.7 s per loop
remove_4 # while n in L: L.remove(n)
1 loops, best of 3: 129 s per loop
remove_5 # whiledel
1 loops, best of 3: 1.87 s per loop
remove_6 # slide
1 loops, best of 3: 227 ms per loop
于 2013-08-02T18:02:12.530 回答
0 
In [13]: A= [1, 2, 3, 8, 7, 8, 8, 7, 6]

In [14]: [i for i in A if i!=8]
Out[14]: [1, 2, 3, 7, 7, 6]

In [15]: filter(lambda i: i!=8, A)
Out[15]: [1, 2, 3, 7, 7, 6]
于 2013-08-01T22:48:33.250 回答