我正处于一个我一直在工作的项目的最后阶段。一切都很顺利，但是我有一个瓶颈问题，我无法解决。
我有一个元组列表。该列表长度范围从 40,000 到 1,000,000 条记录不等。现在我有一个字典，其中每个 (value, key) 对都是列表中的一个元组。
所以，我可能会有以下情况：
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个元组的列表中删除更多，因此需要更快的方法。
有更好的方法吗？
如果需要，我可以提供用于测试的代码以及实际应用程序的pickled数据。
你需要进行测量，但我可以想象这种方式更加高效：
myList = filter(lambda x: myDict.get(x[1], None) != x[0], myList)
因为在字典中查找更适合这种情况。需要注意的是，在删除旧列表之前，这将创建一个新列表；因此会有内存上的权衡。如果这是一个问题，那么重新考虑容器类型，就像jkp建议的那样。
编辑: 但要小心，如果 None 实际上在您的列表中 - 您必须使用不同的“占位符”。
如果要从大约1,000,000个列表中删除约10,000个元组，如果值是可哈希的，则最快的方法应该是：
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 进行两次索引）。myList.remove时，Python都要扫描整个列表以搜索并删除该项。在最坏的情况下，每次查找的每个项都位于列表末尾。您是否尝试过执行“反向”操作：newMyList = [(v,k) for (v,k) in myList if not k in myDict]
但我真的不确定那种方法在扩展性方面有多好，因为你将复制原始列表 -- 可能会使用大量内存。
在这里最好的替代方案可能是等待Alex Martelli发布一些令人惊叹的直观、简单和高效的方法。
list作为你要移除的容器。因此，要找到列表中的每个项目都是一个线性操作（O(n)），它必须遍历整个列表直到找到匹配项。list替换为某个其他容器（例如set），该容器使用每个项目的hash()进行排序，则每个匹配项可以更快地执行。list_set = set(original_list)
dict_set = set(zip(original_dict.values(), original_dict.keys()))
difference_set = list(list_set - dict_set)
final_list = []
for item in original_list:
if item in difference_set:
final_list.append(item)
[(i, j) for i, j in myList if myDict.get(j) != i]
尝试像这样做：
myListSet = set(myList)
myDictSet = set(zip(myDict.values(), myDict.keys()))
myList = list(myListSet - myDictSet)
myList转换成一个集合，交换myDict中的键/值并放入一个集合中，然后找到差异，将其转换回列表，并将其重新赋值给myList. :)[i for i in myList if i not in list(zip(myDict.values(), myDict.keys()))]
dict。 - agfdef filter_by_dict(my_list, my_dict):
sentinel = object()
for i in xrange(len(my_list) - 1, -1, -1):
key = my_list[i][1]
if my_dict.get(key, sentinel) is not sentinel:
del my_list[i]
更新 实际上，每个删除操作都需要使用C语言的memmove()将列表指针向下移动，因此如果有d个删除操作，则时间复杂度为O(n*d)而不是O(n**2)。请注意：(1)原帖中建议d约等于0.01 * n，(2)O(n*d)的工作量是将一个指针复制到内存中的其他位置...因此这种方法实际上可能比一眼看上去要快一些。有人做过基准测试吗？
在从字典中删除项目后，您打算如何处理列表？是否可以将字典过滤与下一步操作结合起来？