在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

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

这个方法很慢，因为 A.keys() 会生成一个列表，而这个列表需要花费 O(N) 的时间来处理。

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

这个方法更快，因为检查 foo 是否在 A 中只需要 O(1) 的时间。

A[foo] = x 

这个方法更好，因为你已经有了对象 x，只需要（如果它还不存在的话）把它的指针添加到 A 中。

Answer 2

使用内置的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

Answer 3

只需往字典里添加项目，而不需要检查它们是否存在。我用三种不同的方法往字典里添加了100,000个项目，并用timeit模块来计时。

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

第三种方法是最快的，但差别不大。

[ 其实，我还试过 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的最快方法的问题。在大多数情况下，很明显这些问题是在遇到性能问题之前就提出的。我的建议是？专注于写出最清晰的程序，如果速度太慢，再去分析和优化。在我的经验中，我几乎从来没有机会进行分析和优化。从问题的描述来看，字典存储似乎不会是你程序中的主要瓶颈。