Python字典中长字符串键的效率

Question

我正在解析一些xml（使用Python 3.4代码），想要检索节点中的文本和id属性。例如： <li id="12345"> Some text here </li> 我的当前代码仅围绕文本进行结构化（我现在正在添加id，但以前不需要它）。我正在循环遍历文本/句子列表，然后继续执行某些操作。因此，我考虑创建一个字典，将文本/句子作为键，将该id属性作为值。

然而，这并不是非常有效。文本可以是整个段落，使得键非常长。而id始终具有相对较短的长度（但仍然是str类型，例如一些字母后面跟着一些数字）。 但是，将ids作为键，将文本作为值需要对代码进行一些重写。这并不是非常麻烦，但这让我想知道：与像“ulp_887362487687678”这样的id键相比，将文本（可能是整个段落）作为键会有多么低效？

我可以创建两个反向字典（一个以id为键，另一个以文本为键）并比较构建和查找等。我还发现了一些关于键长度限制的主题（Do Dictionaries have a key length limit?）。但我只是想知道您对此的看法。在字典中拥有如此长的str键是绝对要避免的，还是不是非常大的问题？ 如果您可以分享一些利弊，那就太好了！

- Igor

Answer 1

不，Python字符串的长度几乎不会对字典的性能产生影响。字符串长度可能唯一会对性能产生影响的是用于将键映射到哈希表槽位的hash()函数。

字符串长度对hash()的性能影响非常小：

>>> import random
>>> from timeit import timeit
>>> from string import ascii_letters
>>> generate_text = lambda len: ''.join([random.choice(ascii_letters) for _ in range(len)])
>>> for i in range(8):
...     length = 10 + 10 ** i
...     testword = generate_text(length)
...     timing = timeit('hash(t)', 'from __main__ import testword as t')
...     print(f'Length: {length}, timing: {timing}')
... 
Length: 11, timing: 0.03713229100685567
Length: 20, timing: 0.024632290937006474
Length: 110, timing: 0.020530124893411994
Length: 1010, timing: 0.019442707998678088
Length: 10010, timing: 0.019319916958920658
Length: 100010, timing: 0.01950641698203981
Length: 1000010, timing: 0.019174500019289553
Length: 10000010, timing: 0.0229318750789389

我停在生成一个1000万个字符的字符串上，因为我不想等待我的笔记本电脑生成一个1亿个字符的字符串。

计时几乎是恒定的，因为一旦计算完成，该值实际上会被缓存到字符串对象上。

有一个特殊情况会影响性能：具有极长共同前缀的字符串。字典查找包括两个阶段：哈希查找，选择字典中的一个存储桶，然后与该存储桶中的任何现有键进行相等性测试。如果键不是同一个对象（当使用"is"足够时），非常长，并且它们的大部分前缀相同，相等性测试可能需要很长时间。字符串相等性测试使用"memcomp"，这意味着比较需要O(N)的时间，其中N是共同前缀的长度。

>>> for i in range(7):
...     length = 10 + 10 ** i
...     testword = generate_text(length)
...     testother = testword[:-10] + generate_text(10)
...     timing = timeit('t == o', 'from __main__ import testword as t, testother as o')
...     print(f'Length: {length}, timing: {timing}')
...
Length: 11, timing: 0.03756483399774879
Length: 20, timing: 0.016259542084299028
Length: 110, timing: 0.023491207975894213
Length: 1010, timing: 0.03878312499728054
Length: 10010, timing: 0.28688233299180865
Length: 100010, timing: 2.5207629159558564
Length: 1000010, timing: 25.976553458953276

然而，这种情况应该很少见。不要使用非常长的字符串，这些字符串很可能以相同的文本作为键开始。

- Martijn Pieters

---

对于@JackBrennen提出的关于字典与hash()性能的问题，你有什么想法吗？他暗示字典的性能可能与仅使用hash有明显的区别。 - undefined

@BryanP：啊，是的，查找操作也会执行相等性检查（lookupkey.__eq__(storedkey)），如果你的字符串足够大并且有一个很长的共同前缀，那么这个操作可能会很耗费资源。虽然这种情况并不常见，但理论上是有可能发生的。 - undefined

Answer 2

hash()方法对于字符串的性能确实是 O(n) 的，但结果会被缓存到字符串中，重复调用将使用缓存值。这是因为字符串是不可变的。Martijn 的代码使用了 timeit 的 repeating 特性，因此你无法看到这个效果，因为在最后一个情况下，10000009 次中有 10000010 次哈希码没有被计算。然而，在底层仍然是 O(n) 的。

import random
from timeit import timeit

for i in range(10):
    length = 10 ** i
    # notice number=1 !!!
    timing = timeit('hash(t)', 't = "a" * {}'.format(length), number=1)
    print('Length: {:10d}, timing: {:.20f}'.format(length, timing))

Length:          1, timing: 0.00000437500057159923
Length:         10, timing: 0.00000287900184048340
Length:        100, timing: 0.00000342299972544424
Length:       1000, timing: 0.00000459299917565659
Length:      10000, timing: 0.00002153400055249222
Length:     100000, timing: 0.00006719700104440562
Length:    1000000, timing: 0.00066680999952950515
Length:   10000000, timing: 0.00673243699930026196
Length:  100000000, timing: 0.04393487600100343116
Length: 1000000000, timing: 0.39340837700001429766

由于时间错误、分支预测等原因，两者之间存在差异。

- Antti Haapala -- Слава Україні

---

这难道不包括解释和编译包含长字符串的代码所需的时间吗？ - user48956

@user48956 不是的，该字符串是在设置代码中创建的，而该部分不计入时间。此外，代码并不包含长字符串，而设置代码的形式为 t = "a" * n。 - Antti Haapala -- Слава Україні

在 timing 值中包含单位会很有帮助。 - ingyhere

Answer 3

Python字符串长度对字典性能有很大的影响，但你必须处理非常大的字符串。

问题显然在于一旦找到正确的哈希桶，仍然需要进行字符串比较以查看是否匹配。除非它们是完全相同的内存中的字符串对象（在这种情况下，Python足够聪明地声明相等），否则在两个巨大的字符串上执行字符串比较是昂贵的。

>>> import timeit
>>> for i in range(7):
...   dkey = "X" * (10**i)
...   skey = "X" * (10**i)    # Different object; no fast path
...   d = {dkey: 1}
...   tmp = d[skey]           # Hash is now cached on skey object
...   timing = timeit.timeit('d[skey] == 1', globals=globals(), number=1000)
...   print(len(dkey), " timing is ", timing*1000, " microseconds")
... 
1  timing is  0.119031872600317  microseconds
10  timing is  0.1442211214452982  microseconds
100  timing is  0.1361379399895668  microseconds
1000  timing is  0.16252091154456139  microseconds
10000  timing is  0.5145659670233727  microseconds
100000  timing is  5.568335996940732  microseconds
1000000  timing is  63.68113495409489  microseconds
>>> 

在长度约为1000的字符串中，由于字符串大小的限制，开销很小。但当长度超过10000时，与字符串长度相关的字典查找似乎实际上是O(N)。

- Jack Brennen

---

字符串不一定要很长，但它们需要有一个长的公共前缀。例如，skey = "x" + "X" * (10 ** i - 1)不会显示相同的时间问题。 - undefined

每次成功查找都有一个完整的公共前缀。真正慢的是具有非常长的字符串键的成功查找。 - undefined