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)

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

score 13 · Accepted Answer

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

然后比较字符串时，它会首先测试它是否是相同的指针（例如，一个内部字符串）：

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

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

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

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

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

score 4 · Accepted Answer

我只是在做疯狂的猜测，但您问的是“可能发生什么”而不是什么，所以这里有一些可能性：

2 回答 2