在字典中使用字符串作为键总是更快吗？

Question

在这个页面上,我看到一些有趣的东西:

请注意,有一个快速路径的dicts(实际上)只处理str键; 这不会影响算法的复杂性,但它会显着影响常数因素:典型程序的完成速度.

那究竟是什么意思呢？

这是否意味着使用字符串,因为键总是更快？

如果是,为什么？

更新:

感谢有关优化的建议!但实际上我对真实性更感兴趣,而不是我们是否应该进行优化.

更新2:

感谢您的回答,我将引用@DaveWebb提供的链接中的内容:

"......

ma_lookup最初设置为lookdict_string函数(在3.0中重命名为lookdict_unicode),它假定字典中的键和要搜索的键都是标准的PyStringObject.然后,它可以进行一些优化,例如减轻各种错误检查,因为字符串到字符串的比较从不引发异常.也不需要进行富对象比较,这意味着我们避免调用PyObject_RichCompareBool,并且总是直接使用_PyString_Eq.

......"

此外,对于实验数字,我认为如果没有int-to-string转换,差异的大小将更大

Answer 1

Python字典的基础C代码是String键的最佳代码. 你可以在这里阅读(在博客中提到的书中).

如果Python运行时知道你的dict只包含字符串键,它可以做一些事情,例如不能满足字符串到字符串比较时不会发生的错误,并忽略丰富的比较运算符.这将使字符串键的常见情况dict更快一些.(更新:时间显示它不止一点.)

但是,这不太可能对大多数Python程序的运行时间产生重大影响.如果您已经测量并发现dict查找是代码中的瓶颈,那么只需要担心这种优化. 正如着名的名言所说:"过早优化是万恶之源."

看到事情真正有多快的唯一方法就是计时:

>>> timeit.timeit('a["500"]','a ={}\nfor i in range(1000): a[str(i)] = i')
0.06659698486328125
>>> timeit.timeit('a[500]','a ={}\nfor i in range(1000): a[i] = i')
0.09005999565124512

因此,使用字符串键比int键更快约30%,我不得不承认我对差异的大小感到惊讶.

Answer 2

因为这只影响恒定时间,所以根本不重要.您真正需要优化的唯一时间是在处理非常大的数据集时 - 这对您没有任何影响.

这意味着,在你有小字典作为键的字典的情况下,Python会很快 - 这是一种常见的用法,所以它已经过优化.

正如伊格纳西奥·巴斯克斯 - 艾布拉姆斯所指出的那样,将你的钥匙转换成一根绳子的成本(远远超过)可能会从你作为字典的字符串中获得的轻微提升.

简而言之,使用与您的情况相关的内容 - 优化只应在需要时进行,而不是之前进行.

一些测试:

python -m timeit -s "a={key: 1 for key in range(1000)}" "a[500]"
10000000 loops, best of 3: 0.0773 usec per loop

python -m timeit -s "a={str(key): 1 for key in range(1000)}" "a[\"500\"]"
10000000 loops, best of 3: 0.0452 usec per loop

python -m timeit -s "a={str(key): 1 for key in range(1000)}" "a[str(500)]"
1000000 loops, best of 3: 0.244 usec per loop

正如您所看到的,虽然基于字符串的字典更快,但相比之下转换密钥非常昂贵,完全减轻了增益(然后是一些增益).

所以是的,如果您使用的数据仅用作字典的键,并且您的存储格式无关紧要,那么字符串在小字典中更可取.在实践中,这是一种非常罕见的情况(你可能已经在使用字符串了).