Python中更新字典的最快方法

Question

我有一个字典A，和一个可能的词条foo。我知道A[foo]应该等于x，但我不知道A[foo]是否已经被定义。无论如何，如果A[foo]已经被定义，那么它就已经具有正确的值。

执行以下操作更快：

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

或者简单地更新。

A[foo]=x 

因为当计算机找到foo条目时，它可以更新它。否则我就需要调用哈希表两次？

谢谢。

- Pietro Speroni

---

你怎么会遇到这个问题？通常你应该知道你设置了哪些键，或者一次性构建最终的字典。 - Jochen Ritzel

我正在计算代数中的所有元素（和关系）。我必须利用我所知道的来找出我不知道的。有些计算比较困难，所以我把它们留到最后。希望到我计算它们的时候，我可以利用其他元素免费推导出它们。所以很快我就不知道我已经发现了哪些关系，哪些我没有。由于元素很多，关系也很多，我需要快速。 - Pietro Speroni

从问题描述来看，似乎字典存储不会成为您的程序的主要瓶颈。只需编写尽可能清晰的程序，如果速度太慢，请进行分析并在必要时进行优化。根据我的经验，我几乎从不需要进行分析和优化步骤。 - Steven Rumbalski

当你使用 timeit 时，你学到了什么？请发布结果。 - S.Lott

@S.Lott 我刚刚发布了一个使用 timeit 的答案。 - Steven Rumbalski

Answer 1

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

- Alex

Answer 2

可以直接将item添加到字典中，无需检查其是否已存在。我使用了三种不同的方法向一个字典中添加了100000个item，并使用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的问题，而大多数情况下，明显这个问题是在出现任何性能问题之前就被问出来了。我的建议是，专注于编写你能写出的最清晰的程序，如果它太慢了，就使用分析工具找到需要优化的地方进行优化。根据我的经验，我几乎从来没有使用过分析和优化步骤。从问题描述中可以看出，在你的程序中，字典存储不会是主要的瓶颈。

- Steven Rumbalski

---

感谢测试。现在我们知道了。当然，如果我只是对这个程序的速度感兴趣，我应该选择分析。但我不是。我不认识你，但对我来说，经常需要决定是重写字典条目还是先检查。知道哪个更好是一种精神上的清洁。两个数量级是很多的！ - Pietro Speroni

Answer 3

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

非常缓慢，因为A.keys()会创建一个列表，需要 O(N) 时间来解析。

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

之所以更快，是因为检查A中是否存在foo只需花费O(1)的时间。

A[foo] = x 

更好的方法是，因为您已经有了对象x，只需将指针添加到A中（如果它不存在）。

- eumiro

---

我错了吗 :-/ ? 我认为问题是如何将一个项设置到字典中，如果它还不存在... - khachik

他的问题表述有点奇怪，但他的意思是“如果值已经设置，那么它已经被正确地设置了”，所以在这种情况下用完全相同的值进行覆盖是可以的。 - Thomas Vander Stichele

嗨，Thomas，抱歉如果我表达有些奇怪。请随意编辑和纠正它。但是在我看来，你完全理解了我的意思 :-) - Pietro Speroni

Answer 4

foo not in A.keys()

在Python 2中，将创建一个带有键的新列表，然后对其执行线性搜索。这保证会更慢（尽管我主要反对它是因为有更快速且更优雅/惯用的替代方案）。

A[foo] = x

和

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

如果A [foo]已经存在但不是x，则两者是不同的。但由于您“知道”A [foo]将是x，因此从语义上讲并不重要。无论如何，在性能方面都很好（很难在没有基准测试的情况下确定，尽管直觉告诉我if比复制指针需要更多时间）。

因此，答案显然是：选择代码更短且同样清晰的那个（第一个）。

- user395760

Answer 5

如果你“知道”A [foo]“应该”等于x，那么我会这样做：

assert(A[foo]==x)

这将告诉您您的假设是否错误！

- Spacedman

---

虽然如果 foo 不在 A 中，这将会失败并抛出 KeyError 异常。但是，如果程序开始给出错误的结果，可以使用 if foo in A: assert A[foo] == x 进行断言。 - user395760

谢谢，这样做行不通。如果没有报错，foo可能根本没有定义。只有在它被定义的情况下，我才知道它等于x。如果我检查一下，可能会使代码更健壮（实际上我现在确实有那些断言），但会更慢。最终，代码必须在没有这些断言的情况下正常运行。 - Pietro Speroni

Answer 6

肯定有比你的第一个示例更快的方法。但我怀疑直接更新会比任何测试都要快。

- Douglas Leeder

Answer 7

A.setdefault(foo, x) 但我不确定它是否比 if not A.has_key(foo): A[foo] = x 更快。需要进行测试。

- khachik

---

我也考虑过使用setdefault，但我怀疑它是否比A[foo] = x更快。 - Douglas Leeder

它并不更快，但 A[foo]=x 不会实现原作者想要的功能。根据代码片段，在字典中不存在键 foo 时才会添加 foo:x。 - khachik

谢谢Khachik，我（操作者）只需要确保最终A [foo] = x。如果它已经被定义并且a [foo]已经等于x，如果重新分配更快，那么我可以重新分配它。 - Pietro Speroni

@Pietro 确认一下：我刚测试了一下，A[foo]=x 比 A.setdefault(foo, x) 快（1/1.5）。所以如果旧值可以被覆盖，你可以直接重新赋值。 - khachik