3

defaultdict数千万のキーと値のペア (文字列 : 整数) を含む大きな辞書 (実際には a ) があるとします。

値に対する単純な条件 (例: ) に基づいて、キーと値のペアの約半分を削除したいと考えてvalue > 20います。

これを行う最速の方法は何ですか?

4

4 に答える 4

3

イテレータベースのdictの再生成は良いアプローチだと思います。

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}

Python2.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、フィルタリングされたデータも参照します。

編集：

このスレッドで説明されている3つの方法をベンチマークで比較してみましょう。

結果は明らかに「削除」される辞書の割合に依存します（これはおそらく予測不可能ですが、スレッドオープナーだけが知っています）。また、ガベージコレクションのアクティビティに大きく依存する可能性があります。ガベージコレクションは、デフォルトでtimeit。測定時のノイズを低減するためにオフになっています。ただし、これによりメソッドのランキングが完全に変わる可能性があります。みてみましょう：

ベンチマークコードを事前に：

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

Linux2.6.32-34上の64ビットPython2.7.3で測定-24GBメモリを搭載したXeonE5630で一般的。ピークメモリ使用量が10％未満（上から監視）。

結論

  1. 方法1と3のパフォーマンスは、ガベージコレクションの状態とは無関係です。
  2. 方法2は、ガベージコレクションによって大幅に遅くなります。方法1と3は、ガベージコレクションが無効になっている場合を除いて、常に高速です。
  3. ほとんどの項目が除外されると予想される場合は、方法1（辞書の理解）を使用します。キーの数の最大半分（またはそれ以上、より細かいベンチマークが必要）を破棄することが予想される場合は、方法3を使用します。

いずれにせよ、方法1を選択します。これは、方法3よりもコードがクリーンであり、パフォーマンスの差が大きくないためです。しかし、それは完全にあなた次第です。

于 2012-09-19T23:12:13.170 に答える
2

参考のために：

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

（モジュラス== 0の比較の速度は<20と同じオーダーであると想定していますが、これらのテストには実際には関係ありません。）非常に大きなdictの場合、これらはほぼ同じオーダーの大きさですが、私は推測します。インプレースは少し高速です。

于 2012-09-19T23:25:50.887 に答える
2 
dict((k,v) for k,v in original_dict.iteritems() if condition)

これにより、条件に基づいて、メモリに優しい (iteritemsおよびジェネレーターによる) 効率的な方法 (多くの関数/メソッド呼び出しではない) で、新しい辞書が作成されます。

于 2012-09-19T23:11:35.117 に答える
1

あなたが新しいものを作ることに大丈夫なら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]

これらが最速かどうかはわかりませんが、高速である必要があります。

于 2012-09-19T23:15:14.490 に答える