在python中更新字典的最快方法

Question

我有一本字典A和一个可能的条目foo.我知道A [foo]应该等于x,但我不知道A [foo]是否已被定义.在任何情况下,如果定义了A [foo],则意味着它已经具有正确的值.

执行速度更快:

if foo not in A.keys(): 
   A[foo]=x 

或者只是更新

A[foo]=x 

因为当计算机找到foo条目时,它也可以更新它.如果不是,我将不得不两次调用哈希表？

谢谢.

Answer 1

只需将项目添加到字典中,而无需检查它们的存在.我使用3种不同的方法将10万个项目添加到字典中,并使用timeit模块对其进行计时.

1. if k not in d: d[k] = v
2. d.setdefault(k, v)
3. d[k] = v

选项3是最快的,但不是很多.

[ 实际上,我也尝试过if k not in d.keys(): d[k] = v,但是速度慢了300倍(每次迭代都构建了一个键列表并执行了线性搜索).它让我的测试变得如此缓慢以至于我把它留在了这里.]

这是我的代码:

import timeit

setup = """
import random
random.seed(0)
item_count = 100000
# divide key range by 5 to ensure lots of duplicates 
items = [(random.randint(0, item_count/5), 0) for i in xrange(item_count)]
"""
in_dict = """
d = {}
for k, v in items:
    if k not in d:
        d[k] = v
"""
set_default = """
d = {}
for k, v in items:
    d.setdefault(k, v)
"""
straight_add = """
d = {}
for k, v in items:
    d[k] = v
"""
print 'in_dict      ', timeit.Timer(in_dict, setup).timeit(1000)
print 'set_default  ', timeit.Timer(set_default, setup).timeit(1000)
print 'straight_add ', timeit.Timer(straight_add, setup).timeit(1000)

结果如下:

in_dict       13.090878085
set_default   21.1309413091
straight_add  11.4781760635

注意:这一切都毫无意义.我们每天都会收到很多关于在Python中使用x或y的最快方法的问题.在大多数情况下,很明显在遇到任何性能问题之前都会问到这个问题.我的建议？专注于编写您可以编写的最清晰的程序,如果它太慢,请对其进行分析并在需要的地方进行优化.根据我的经验,我几乎从未进行过剖析和优化步骤.从问题的描述来看,似乎字典存储不会成为程序中的主要瓶颈.

Answer 2

if foo not in A.keys(): 
    A[foo] = x 

非常慢,因为A.keys()创建一个列表,必须在O(N)中解析.

if foo not in A: 
    A[foo] = x 

更快,因为它需要O(1)来检查,是否foo存在A.

A[foo] = x 

甚至更好,因为你已经拥有了这个对象x,你只需添加一个指向它的指针(如果它已经不存在)A.

Answer 3

使用内置的update()函数更快.我稍微调整了Steven Rumbalski的例子,它显示了update()是如何最快的.至少有两种方法可以使用它(带有元组列表或另一个字典).前者(如下所示为update_method1)是最快的.请注意,我还改变了一些关于Steven Rumbalski的例子.我的词典每个都有100,000个键,但新值有10%的可能性不需要更新.冗余的可能性取决于您更新字典的数据的性质.在我的机器上的所有情况下,我的update_method1是最快的.

import timeit

setup = """
import random
random.seed(0)
item_count = 100000
existing_dict = dict([(str(i), random.randint(1, 10)) for i in xrange(item_count)])
items = [(str(i), random.randint(1, 10)) for i in xrange(item_count)]
items_dict = dict(items)
"""
in_dict = """
for k, v in items:
    if k not in existing_dict:
        existing_dict[k] = v
"""
set_default = """
for k, v in items:
    existing_dict.setdefault(k, v)
"""
straight_add = """
for k, v in items:
    existing_dict[k] = v
"""
update_method1 = """
existing_dict.update(items)
"""
update_method2 = """
existing_dict.update(items_dict)
"""
print 'in_dict        ', timeit.Timer(in_dict, setup).timeit(1000)
print 'set_default    ', timeit.Timer(set_default, setup).timeit(1000)
print 'straight_add   ', timeit.Timer(straight_add, setup).timeit(1000)
print 'update_method1 ', timeit.Timer(update_method1, setup).timeit(1000)
print 'update_method2 ', timeit.Timer(update_method2, setup).timeit(1000)

此代码导致以下结果:

in_dict         10.6597309113
set_default     19.3389420509
straight_add    11.5891621113
update_method1  7.52693581581
update_method2  9.10132408142