Python：从列表中移除多个项目

Question

我正在进行一个项目的最后阶段，整体运行得很顺利，但我遇到了一个瓶颈，解决起来有点麻烦。

我有一个元组的列表，这个列表的长度大约在40,000到1,000,000条记录之间。现在，我有一个字典，里面的每一个（值，键）都是列表中的一个元组。

比如，我可能有这样的内容：

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

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

目前我在做的是：

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

从一个包含20,000个元组的列表中删除838个元组，花费的时间大约是3到4秒。考虑到我可能需要从一个包含1,000,000个元组的列表中删除大约10,000个元组，所以我需要这个过程更快一些。

有没有更好的方法来实现这个？

如果需要，我可以提供用于测试的代码，以及实际应用中的数据。

Answer 1

每次你调用 myList.remove 的时候，Python 都需要遍历整个列表，去寻找并删除那个特定的项。在最糟糕的情况下，你每次寻找的项可能都在列表的最后面。

你有没有试过做这个操作的“反向”操作：

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

不过我真的不太确定这样做的效果如何，因为你会需要复制原来的列表——这可能会占用很多内存。

这里最好的选择可能是等 Alex Martelli 发一些既简单又高效的直观方法。

Answer 2

如果你想从大约一百万个元素的列表中删除大约一万个元组，如果这些值是可以哈希的，最快的方法应该是：

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]

在这两种变体中，使用了哨兵模式来防止出现 None 的值（如果值是可以哈希的，这对首选的基于集合的方法来说不是问题！），因为这样做比 if a not in myDict or myDict[a] != b 便宜得多（后者需要对 myDict 进行两次索引）。

Answer 3

你需要自己测量一下，但我觉得这样做可能会更快：

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

因为查找是在字典中进行的，字典更适合这种操作。不过要注意，这样做会在删除旧列表之前先创建一个新列表，所以会占用更多的内存。如果这对你来说是个问题，像jkp建议的那样考虑换一种容器类型可能是个好主意。

编辑：不过要小心，如果你的列表里真的有None，你就得用其他的“占位符”。