從字典中刪除大量密鑰的最快方法

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 

他們對對於一個非常大的字典來說，這個數量級的數量級相同，但我認爲就地速度要快一些。