3

给定一个大字典，（实际上是 a defaultdict）具有数千万个键值对（字符串：整数）。

我想根据值的简单条件（例如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}

在 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. 它被关闭以减少测量中的噪音。但是，这可以完全改变方法的排名。我们来看一下：

预先基准代码：

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

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

结论

  1. 方法 1 和 3 的性能与垃圾回收的状态无关。
  2. 方法 2 因垃圾收集而显着减慢。方法 1 和 3 总是更快，除了禁用垃圾收集和没有项目被过滤掉的情况。
  3. 如果大多数项目预计会被过滤掉，请使用方法 1（字典理解）。如果您希望丢弃多达一半的键（或者甚至更多，需要更精细的基准测试），请使用方法 3。

无论如何我都会选择方法 1，因为它的代码比方法 3 更简洁，而且性能差异不大。但这完全取决于你。

于 2012-09-19T23:12:13.170 回答
2 
dict((k,v) for k,v in original_dict.iteritems() if condition)

这会根据您的条件以内存友好（由于iteritems和生成器）和有效的方式（而不是大量的函数/方法调用）创建一个新字典。

于 2012-09-19T23:11:35.117 回答
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 回答
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 回答