从字典中删除大量密钥的最快方法

Question

给定一个包含数千万个键值对（字符串：整数）的大型字典（实际上，一个defaultdict）。

根据值的简单条件（例如value > 20），我想删除大约一半的键/值对。

这样做的最快方法是什么？

Answer 1

我觉得字典的基于迭代器的再生是一个好办法：

newdict = dict((k,v) for k,v in d.iteritems() if v > 20) 

或

newdict = {k: v for k,v in d.iteritems() if v > 20} 

在Python 2.7

。

请注意，您必须小心d = {k: v for k,v in d.iteritems() if v > 20}。相反，你应该调用

d.clear() 
d.update({k: v for k,v in d.iteritems() if v > 20}) 

这样，在d数据旧文献也将引用过滤的数据。

编辑：

让我们比较通过基准在这个线程讨论三种方法：

结果显然取决于被“删除”的字典（这也许是不可预测的，但只有比例开线器知道）。它也可能高度依赖垃圾回收的活动，在timeit期间默认为switched off。它被关闭以减少测量中的噪音。但是，这可以完全改变方法的排名。让我们一起来看看：

基准码前期：

from timeit import timeit 

n = 2 
N = "10**7" 
mod = "9999999" 
gc = "False" 
print "N: %s; mod: %s; garbage collection: %s" % (N, mod, gc) 

setup =""" 
N = %s 
mod = %s 
d = {x:1 for x in xrange(N)} 
if %s: 
    gc.enable()""" % (N, mod, gc) 

t = timeit(
'd = {k:v for k, v in d.iteritems() if not k % mod}', 
setup=setup, 
number=n) 
print "%s times method 1 (dict comp): %.3f s" % (n, t) 

t = timeit(
''' 
for k, v in d.items(): 
    if k % mod: 
     del d[k] 
''', 
setup=setup, 
number=n) 
print "%s times method 2 (key deletion within for loop over d.items()): %.3f s" % (n, t) 

t = timeit(''' 
removekeys = [k for k, v in d.iteritems() if k % mod] 
for k in removekeys: 
    del d[k] 
''', 
setup=setup, 
number=n) 
print "%s times method 3 (key deletion after list comp): %.3f s" %(n, t) 

案例1（无字典的项目被过滤掉）：启用

垃圾收集：

N: 10**7; mod: 1; garbage collection: True 
2 times method 1 (dict comp): 4.701 
2 times method 2 (key deletion within for loop over d.items()): 15.782 
2 times method 3 (key deletion after list comp): 2.024 

已禁用垃圾回收：

N: 10**7; mod: 1; garbage collection: False 
2 times method 1 (dict comp): 4.701 
2 times method 2 (key deletion within for loop over d.items()): 4.268 
2 times method 3 (key deletion after list comp): 2.027 

案例2（字典的项目的一半将被过滤掉）：启用

垃圾收集：

N: 10**7; mod: 2; garbage collection: True 
2 times method 1 (dict comp): 3.449 s 
2 times method 2 (key deletion within for loop over d.items()): 12.862 s 
2 times method 3 (key deletion after list comp): 2.765 s 

垃圾收集禁用：

N: 10**7; mod: 2; garbage collection: False 
2 times method 1 (dict comp): 3.395 s 
2 times method 2 (key deletion within for loop over d.items()): 4.175 s 
2 times method 3 (key deletion after list comp): 2.893 s 

案例3（几乎所有的字典的项目被过滤掉）：启用

垃圾收集：

N: 10**7; mod: 9999999; garbage collection: True 
2 times method 1 (dict comp): 1.217 s 
2 times method 2 (key deletion within for loop over d.items()): 9.298 s 
2 times method 3 (key deletion after list comp): 2.141 s 

垃圾收集禁用：

N: 10**7; mod: 9999999; garbage collection: False 
2 times method 1 (dict comp): 1.213 s 
2 times method 2 (key deletion within for loop over d.items()): 3.168 s 
2 times method 3 (key deletion after list comp): 2.141 s 

在Linux上测量64位Python 2.7.3 2.6.32-34-generic o具有24 GB内存的Xeon E5630。峰值内存使用率低于10％（通过顶部进行监控）。

结论

1. 方法1所述的性能和3是独立于垃圾收集的状态。
2. 方法2由垃圾回收显着减慢。方法1和3总是更快，除了禁用垃圾回收的情况，没有项目被过滤掉。
3. 如果大多数项目被期望过滤出来，使用方法1（字典理解）。如果你希望抛出多达一半的键（或者甚至更多，需要更好的基准测试），然后使用方法3.

我会去任何情况下的方法1，因为它是比方法3更干净的代码和性能差异不大。但这完全取决于你。

Answer 2

dict((k,v) for k,v in original_dict.iteritems() if condition) 

这将根据您的病情新的字典，这在内存友好（由于iteritems和发电机）和有效的方式（不是一大堆的功能/方法调用）。

Answer 3

如果你确定与制作新dict：

dict((k, v) for k,v in D.iteritems() if k != "foo") 

如果你真的想修改原始：

removekeys = [k for k, v in D.iteritems() if k == "foo"] 
for k in removekeys: del D[k] 

我不知道这些都是快EST，但他们应该很快。

Answer 4

参考：（我假设模== 0相比处于同一数量级上的< 20的速度，但是这不是真正相关的这些测试）

>>> from timeit import timeit as t 
    # Create a new dict with a dict comprehension 
>>> t('x={k:v for k, v in x.iteritems() if v % 2}', 'x={x:x for x in xrange(10**7)}', number=30) 
100.02150511741638 
    # Delete the unneeded entries in-place 
>>> t('''for k, v in x.items(): 
... if v % 2 != 0: 
...  del x[k]''', 'x={x:x for x in xrange(10**7)}', number=30) 
89.83732604980469 

他们对对于一个非常大的字典来说，这个数量级的数量级相同，但我认为就地速度要快一些。