python 字典中长 (str) 键的效率
efficiency of long (str) keys in python dictionary
我正在解析一些 xml（使用一些 python 3.4 代码）并希望从节点及其 id 属性中检索文本。例子：
<li id="12345"> Some text here </li>
我当前的代码仅围绕文本构建（我现在正在添加 id，但之前不需要它）。我正在遍历 text/sentences 的列表，然后继续做一些事情。所以我想制作一个以 text/sentence 为键的字典，并将此 id 属性作为值。
然而，这感觉效率不高。文本可以是一整段，使密钥很长。而 id 的长度总是相当有限（但仍然是 str 类型，例如一些字母字符后跟一些数字）。
但是使 ids 成为键而文本成为值需要对代码进行一些重写。所有问题都不是很大，但这只是让我想知道：与像 "ulp_887362487687678" 这样的 id 作为键相比，将文本（可能是整个段落）作为键的效率有多低？
我可以制作两个反向词典（一个以 id 为键，另一个以 text 为键）并比较构造和查找等等。而且我还发现了一些关于密钥长度限制 (Do Dictionaries have a key length limit?) 的主题。但我只是想知道你对此有何看法。在你的 dict 中有这么长的 str 键是不是你绝对想避免的事情，或者这不是什么大不了的事？
如果你能分享一些专业的's/con，那就太好了！
不，Python 字符串长度对字典性能几乎没有影响。字符串长度可能产生的唯一影响是 hash() 函数用于将密钥映射到散列 table 槽。
字符串长度对hash()的性能影响很小：
>>> import random
>>> from timeit import timeit
>>> from string import ascii_letters
>>> generate_text = lambda len: ''.join([random.choice(ascii_letters) for _ in xrange(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 'Length: {}, timing: {}'.format(length, timing)
...
Length: 11, timing: 0.061537027359
Length: 20, timing: 0.0796310901642
Length: 110, timing: 0.0631730556488
Length: 1010, timing: 0.0606122016907
Length: 10010, timing: 0.0613977909088
Length: 100010, timing: 0.0607581138611
Length: 1000010, timing: 0.0672461986542
Length: 10000010, timing: 0.080118894577
我在生成 1000 万个字符的字符串时停止了，因为我懒得等待笔记本电脑生成 1 亿个字符的字符串。
时间几乎是恒定的，因为计算后该值实际上缓存在字符串对象上。
对于字符串，hash()的性能确实是O(n)，但是结果被缓存在字符串中——重复调用将使用缓存值。这是可能的，因为字符串 不可变 。 Martijn 的代码使用了 timeit 的 repeating 特性，所以你看不到这个效果，因为在最后一个例子中，10000010 次中有 10000009 次没有计算哈希码。
下面还是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
差异是由于计时错误、分支预测等原因造成的。
在大多数情况下，@Martijn Pieters 的回答是正确的，也就是说，理论上是正确的。
但是，实际上，在性能方面您需要考虑很多事情。
我最近 运行 遇到了这个 将长字符串散列为键 的问题，我在练习中遇到了超时错误，只是因为 python的字典键散列。我知道这一点是因为我使用 JavaScript 对象作为 "dictionary" 解决了这个问题并且它工作得很好，这意味着没有超时错误。
然后因为我的键实际上是一长串数字列表，所以我将它们改为数字元组（不可变对象可以是键）。这也很完美。
话虽这么说，我还是用@Martijn Pieters 在示例中写的散列函数测试了时间，其中一长串数字列表作为元组版本 的键。 元组版本在 repl.it 上花费的时间更长，他们的 python 编译器。我不是在谈论 0.1 的差异。这是 0.02 和 12.02 之间的 差异。
奇怪不是吗？！ :>
现在的重点是，每个环境都不同。您的操作量累积。因此，您 CANNOT 只需说明某个操作是否需要更长或更短的时间。即使是 0.01 秒的操作，只执行 1000 次，也会让用户等待 10 秒。
对于任何生产环境，您确实希望在需要时尝试优化您的算法，并始终使用更好的设计。对于普通软件，它可以节省用户的宝贵时间。对于云服务，这将是我们正在谈论的美元钞票。
最后，我绝对不要推荐使用长字符串作为键，因为我在不同环境中得到的结果不一致。如果需要，您肯定希望使用 id 作为键并遍历字符串值以查找 id。但是如果你必须使用长字符串作为键，可以考虑限制对字典的操作次数。保留两个版本绝对是浪费space/RAM。性能和内存的主题是另一课。
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)。
我正在解析一些 xml（使用一些 python 3.4 代码）并希望从节点及其 id 属性中检索文本。例子：
<li id="12345"> Some text here </li>
我当前的代码仅围绕文本构建（我现在正在添加 id，但之前不需要它）。我正在遍历 text/sentences 的列表，然后继续做一些事情。所以我想制作一个以 text/sentence 为键的字典，并将此 id 属性作为值。
然而，这感觉效率不高。文本可以是一整段，使密钥很长。而 id 的长度总是相当有限（但仍然是 str 类型，例如一些字母字符后跟一些数字）。 但是使 ids 成为键而文本成为值需要对代码进行一些重写。所有问题都不是很大，但这只是让我想知道：与像 "ulp_887362487687678" 这样的 id 作为键相比，将文本（可能是整个段落）作为键的效率有多低？
我可以制作两个反向词典（一个以 id 为键，另一个以 text 为键）并比较构造和查找等等。而且我还发现了一些关于密钥长度限制 (Do Dictionaries have a key length limit?) 的主题。但我只是想知道你对此有何看法。在你的 dict 中有这么长的 str 键是不是你绝对想避免的事情，或者这不是什么大不了的事？ 如果你能分享一些专业的's/con，那就太好了！
不，Python 字符串长度对字典性能几乎没有影响。字符串长度可能产生的唯一影响是 hash() 函数用于将密钥映射到散列 table 槽。
字符串长度对hash()的性能影响很小：
>>> import random
>>> from timeit import timeit
>>> from string import ascii_letters
>>> generate_text = lambda len: ''.join([random.choice(ascii_letters) for _ in xrange(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 'Length: {}, timing: {}'.format(length, timing)
...
Length: 11, timing: 0.061537027359
Length: 20, timing: 0.0796310901642
Length: 110, timing: 0.0631730556488
Length: 1010, timing: 0.0606122016907
Length: 10010, timing: 0.0613977909088
Length: 100010, timing: 0.0607581138611
Length: 1000010, timing: 0.0672461986542
Length: 10000010, timing: 0.080118894577
我在生成 1000 万个字符的字符串时停止了，因为我懒得等待笔记本电脑生成 1 亿个字符的字符串。
时间几乎是恒定的，因为计算后该值实际上缓存在字符串对象上。
对于字符串，hash()的性能确实是O(n)，但是结果被缓存在字符串中——重复调用将使用缓存值。这是可能的，因为字符串 不可变 。 Martijn 的代码使用了 timeit 的 repeating 特性，所以你看不到这个效果，因为在最后一个例子中，10000010 次中有 10000009 次没有计算哈希码。
下面还是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
差异是由于计时错误、分支预测等原因造成的。
在大多数情况下，@Martijn Pieters 的回答是正确的，也就是说，理论上是正确的。 但是，实际上，在性能方面您需要考虑很多事情。
我最近 运行 遇到了这个 将长字符串散列为键 的问题，我在练习中遇到了超时错误，只是因为 python的字典键散列。我知道这一点是因为我使用 JavaScript 对象作为 "dictionary" 解决了这个问题并且它工作得很好，这意味着没有超时错误。
然后因为我的键实际上是一长串数字列表，所以我将它们改为数字元组（不可变对象可以是键）。这也很完美。
话虽这么说，我还是用@Martijn Pieters 在示例中写的散列函数测试了时间，其中一长串数字列表作为元组版本 的键。 元组版本在 repl.it 上花费的时间更长，他们的 python 编译器。我不是在谈论 0.1 的差异。这是 0.02 和 12.02 之间的 差异。
奇怪不是吗？！ :>
现在的重点是，每个环境都不同。您的操作量累积。因此，您 CANNOT 只需说明某个操作是否需要更长或更短的时间。即使是 0.01 秒的操作，只执行 1000 次，也会让用户等待 10 秒。
对于任何生产环境，您确实希望在需要时尝试优化您的算法，并始终使用更好的设计。对于普通软件，它可以节省用户的宝贵时间。对于云服务，这将是我们正在谈论的美元钞票。
最后，我绝对不要推荐使用长字符串作为键，因为我在不同环境中得到的结果不一致。如果需要，您肯定希望使用 id 作为键并遍历字符串值以查找 id。但是如果你必须使用长字符串作为键，可以考虑限制对字典的操作次数。保留两个版本绝对是浪费space/RAM。性能和内存的主题是另一课。
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)。