Python：从lis中删除很多项

Question

我正在做一个项目的最后阶段。一切都很顺利，但我有一个瓶颈，我有麻烦工作。

我有一个元组列表。这个列表的长度从40000到1000000条记录不等。现在我有了一个字典，其中每个（值，键）都是列表中的元组。

所以，我可能

myList = [(20000, 11), (16000, 4), (14000, 9)...]
myDict = {11:20000, 9:14000, ...}

我想从列表中删除每个（v，k）元组。

目前我正在做：

for k, v in myDict.iteritems():
    myList.remove((v, k))

从包含20000个元组的列表中删除838个元组需要3-4秒的时间。我很可能会从1000000的列表中删除10000个元组，所以我需要更快。

有更好的办法吗？

我可以提供用于测试的代码，如果需要，还可以提供来自实际应用程序的pickle数据。

Answer 1

若要从约1000000个元组的列表中移除约10000个元组，如果这些值是可哈希的，则最快的方法应为：

totoss = set((v,k) for (k,v) in myDict.iteritems())
myList[:] = [x for x in myList if x not in totoss]

该集合的准备是一个小的一次性成本，节省了做元组解包和重新打包，或元组索引，很多次。赋值给myList[:]而不是赋值给myList在语义上也很重要（如果有其他对myList的引用，仅仅重新绑定名称是不够的——您真的想重新绑定内容！-).

我没有你的测试数据来自己测量时间，唉！，但是，让我知道它是如何利用你的测试数据的！

如果值不可哈希（例如，它们是子列表），最快的可能是：

sentinel = object()
myList[:] = [x for x in myList if myDict.get(x[0], sentinel) != x[1]]

或者（无论哪种方式都不应该有太大的区别，但我怀疑前一种方法更好——索引比解包和重新打包更便宜）：

sentinel = object()
myList[:] = [(a,b) for (a,b) in myList if myDict.get(a, sentinel) != b]

在这两种变体中，sentinel习惯用法用于防止None的值（这对于首选的基于集合的方法来说不是问题——如果值是散列的！）因为它将比if a not in myDict or myDict[a] != b（需要两个索引到myDict）便宜得多。

Answer 2

每次调用myList.remove时，Python都必须扫描整个列表以搜索并删除该项。在最坏的情况下，每次查找的项目都将位于列表的末尾。

您是否尝试过执行以下“反向”操作：

newMyList = [(v,k) for (v,k) in myList if not k in myDict]

但我真的不确定这会有多大的扩展性，因为你要复制一份原始列表——可能会占用大量内存。

或许最好的选择是等亚历克斯·马泰利发表一些令人惊叹的直观、简单和有效的方法。

Answer 3

你得衡量一下，但我可以想象这会更有效果：

myList = filter(lambda x: myDict.get(x[1], None) != x[0], myList)

因为查找发生在dict中，这更适合这种情况。不过，请注意，这将在删除旧列表之前创建一个新列表；因此存在内存折衷。如果这是一个问题，那么按照jkp的建议重新考虑您的容器类型可能是正确的。

编辑：但是，如果列表中确实有None，则必须使用不同的“占位符”