24

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

请注意,(在实践中)仅处理 str 键的 dicts 有一条快速路径;这不会影响算法的复杂性,但会显着影响常数因素:典型程序完成的速度。

那么它到底是什么意思呢?

这是否意味着使用字符串作为键总是更快?

如果是,为什么?

更新:

感谢您对优化的建议!但实际上我更感兴趣的是显而易见的事实,而不是我们是否应该或何时应该进行优化。

更新 2:

感谢您提供出色的答案,我将在此处引用@DaveWebb 提供的链接中的内容:

“……

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

……”

另外,对于实验数字,我认为如果没有 int 到 string 的转换,差异的大小会更大

4

2 回答 2

23

Python dict 基础的 C 代码针对字符串键进行了优化。 您可以在此处阅读相关内容(以及该博客所指的书中)。

如果 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%,我不得不承认我对差异的大小感到惊讶。

于 2012-06-22T18:47:58.503 回答
9

由于这仅影响恒定时间,因此可能根本不重要。您真正需要优化的唯一时间是当您使用非常大的数据集时 - 这不会产生任何影响。

这确实意味着,在您有以字符串为键的小型字典的情况下,Python 会很快——这是一种常见用法,因此已针对它进行了优化。

正如 Ignacio Vazquez-Abrams 指出的那样,将您的密钥转换为字符串可能会花费(远远)超过您可能从它作为 dict 的字符串中获得的轻微提升。

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

一些测试:

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

如您所见,虽然基于字符串的 dict 更快,但相比之下转换密钥非常昂贵,完全降低了增益(然后是一些)。

所以是的,如果您使用的数据仅用作字典的键,并且您将它们存储在什么格式中并不重要,那么在小型字典中字符串更可取。实际上,这是一种非常罕见的情况(您可能已经在使用字符串了)。

于 2012-06-22T18:43:58.463 回答