python - 什么会影响超过 64 个字符的字符串的 Python 字符串比较性能？

Question

我正在尝试评估比较两个字符串是否会随着长度的增加而变慢。我的计算表明比较字符串应该花费一个摊销的常数时间，但我的 Python 实验产生了奇怪的结果:

这是字符串长度(1 到 400)与时间(以毫秒为单位)的关系图。自动垃圾收集被禁用，并且 gc.collect 在每次迭代之间运行。

我每次比较 100 万个随机字符串，计数匹配如下。该过程重复 50 次，然后取所有测量时间的最小值。

for index in range(COUNT):
    if v1[index] == v2[index]:
        matches += 1
    else:
        non_matches += 1

长度 64 左右突然增加的原因可能是什么？

注意:假设 v1 和 v2 是两个长度为随机字符串的列表，可以使用以下代码段尝试重现该问题n 和 COUNT 是它们的长度。

timeit.timeit("for i in range(COUNT): v1[i] == v2[i]",
  "from __main__ import COUNT, v1, v2", number=50)

进一步说明:我做了两个额外的测试:将字符串与 is 而不是 == 进行比较完全抑制了问题，并且性能约为 210ms/1M 比较。由于提到了实习，我确保在每个字符串后添加一个空格，这应该可以防止实习；这不会改变任何事情。那除了实习还有别的事吗？

Answer 1

Python 可以 'intern' 短字符串；将它们存储在一个特殊的缓存中，并重新使用该缓存中的字符串对象。

然后在比较字符串时，它会首先测试它是否是同一个指针(例如一个实习字符串):

if (a == b) {
    switch (op) {
    case Py_EQ:case Py_LE:case Py_GE:
        result = Py_True;
        goto out;
// ...

只有当指针比较失败时，它才会使用大小检查和 memcmp 来比较字符串。

Interning 通常只发生在标识符(函数名、参数、属性等)上，但不适用于在运行时创建的字符串值。

另一个可能的罪魁祸首是字符串常量；代码中使用的字符串文字在编译时存储为常量并在整个过程中重复使用；再次只创建一个对象，并且对这些对象进行身份测试更快。

对于不相同的字符串对象，Python 测试相等的长度，相等的第一个字符，然后在内部 C 字符串上使用 memcmp() 函数。如果您的字符串没有被实习或以其他​​方式重用相同的对象，所有其他速度特征都归结为 memcmp() 函数。