Python:从列表中删除大量项

您必须进行测量,但我可以想象这会更有效:

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

编辑 :但是,如果有可能,请小心 None

要从大约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 在语义上也很重要(如果有任何其他引用 在周围,仅仅重新绑定名称是不够的——你真的想重新绑定名称吗 目录 !-).

如果值不可散列(例如,它们是子列表),则最快的可能是:

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

myList.remove ,Python必须扫描整个列表才能搜索该项并将其删除。在最坏的情况下,您查找的每个项目每次都会位于列表的末尾。

您是否尝试过以下操作的“反向”操作:

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

[(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

在我看来,问题在于您正在使用 list 作为您试图从中删除的容器,它是一个完全无序的类型。因此,查找列表中的每个项目是一个线性操作( O(n) ),它必须迭代整个列表,直到找到匹配项。

如果你能交换一下 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 for i in myList if i not in list(zip(myDict.values(), myDict.keys()))]

在大多数运行Python的机器上,包含一百万个2元组的列表不是很大。但是,如果您必须在现场进行拆卸,这里有一个干净的正确方法:

def 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]

使现代化 O(n*d) O(n**2) . 注意(1)OP建议d约为== 0.01 * n 及(二)有关 O(不适用) 努力将一个指针复制到内存中的其他位置。。。因此,这种方法实际上可能比快速浏览显示的要快一些。有人吗?

之后 您是否已删除dict中的项目?是否有可能将dict过滤带回到下一步?