我正处于一直在进行的项目的最后阶段.一切都运行顺利,但我有一个瓶颈,我无法解决.
我有一个元组列表.该列表的长度范围为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个元组,所以我需要更快.
有一个更好的方法吗？
我可以提供用于测试的代码,如果需要,还可以提供实际应用程序中的pickle数据.
bal*_*pha 20
你必须衡量,但我可以想象这是更高效的:
myList = filter(lambda x: myDict.get(x[1], None) != x[0], myList)
因为查找发生在dict中,这更适合这种事情.但请注意,这将在删除旧列表之前创建一个新列表; 所以有一个记忆权衡.如果这是一个问题,重新考虑您的容器类型为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]
该套装的准备是一次性成本很小,很多时候都会节省进行元组拆包和重新打包或元组索引的操作.Assignign到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)便宜).
每次调用时myList.remove,Python都必须扫描整个列表以搜索该项并将其删除.在最坏的情况下,您查找的每个项目每次都会在列表的末尾.
你有没有尝试过"反向"操作:
newMyList = [(v,k) for (v,k) in myList if not k in myDict]
但是我真的不确定这种扩展程度如何,因为你要制作原始列表的副本 - 可能会占用很多内存.
这里最好的替代方案可能是等待Alex Martelli发布一些令人兴奋的直观,简单和高效的方法.