为什么比较匹配的字符串比不匹配的字符串快？

以下是两个衡量标准:

timeit.timeit('"toto"=="1234"', number=100000000)
1.8320042459999968
timeit.timeit('"toto"=="toto"', number=100000000)
1.4517491540000265

如您所见，比较两个匹配的字符串比比较两个大小相同但不匹配的字符串要快。 这非常令人不安: 在字符串比较过程中，我认为 Python 是在逐个字符地测试字符串，因此 "toto"=="toto"的测试时间应该比 "toto"=="1234"长，因为在进行非匹配比较时，需要针对一个字符进行四次测试。也许比较是基于散列的，但是在这种情况下，两种比较的计时应该是相同的。

为什么？

7062 次浏览
小开
最佳答案

Combining my comment and the comment by @khelwood:

TL;DR:
When analysing the bytecode for the two comparisons, it reveals the 'time' and 'time' strings are assigned to the same object. Therefore, an up-front identity check (at C-level) is the reason for the increased comparison speed.

The reason for the same object assignment is that, as an implementation detail, CPython interns strings which contain only 'name characters' (i.e. alpha and underscore characters). This enables the object's identity check.

Bytecode:

import dis


In [24]: dis.dis("'time'=='time'")
1           0 LOAD_CONST               0 ('time')  # <-- same object (0)
2 LOAD_CONST               0 ('time')  # <-- same object (0)
4 COMPARE_OP               2 (==)
6 RETURN_VALUE


In [25]: dis.dis("'time'=='1234'")
1           0 LOAD_CONST               0 ('time')  # <-- different object (0)
2 LOAD_CONST               1 ('1234')  # <-- different object (1)
4 COMPARE_OP               2 (==)
6 RETURN_VALUE

Assignment Timing:

The 'speed-up' can also be seen in using assignment for the time tests. The assignment (and compare) of two variables to the same string, is faster than the assignment (and compare) of two variables to different strings. Further supporting the hypothesis the underlying logic is performing an object comparison. This is confirmed in the next section.

In [26]: timeit.timeit("x='time'; y='time'; x==y", number=1000000)
Out[26]: 0.0745926329982467


In [27]: timeit.timeit("x='time'; y='1234'; x==y", number=1000000)
Out[27]: 0.10328884399496019

Python source code:

As helpfully provided by @mkrieger1 and @Masklinn in their comments, the source code for unicodeobject.c performs a pointer comparison first and if True, returns immediately.

int
_PyUnicode_Equal(PyObject *str1, PyObject *str2)
{
assert(PyUnicode_CheckExact(str1));
assert(PyUnicode_CheckExact(str2));
if (str1 == str2) {                  // <-- Here
return 1;
}
if (PyUnicode_READY(str1) || PyUnicode_READY(str2)) {
return -1;
}
return unicode_compare_eq(str1, str2);
}

Appendix:

  • Reference answer nicely illustrating how to read the disassembled bytecode output. Courtesy of @Delgan
  • Reference answer which nicely describes CPython's string interning. Coutresy of @ShadowRanger
小开

It's not always faster to compare strings that match. Instead, it's always faster to compare strings that share the same id. A proof that identity is indeed the reason of this behavior (as @S3DEV has brilliantly explained) is this one:

>>> x = 'toto'
>>> y = 'toto'
>>> z = 'totoo'[:-1]
>>> w = 'abcd'
>>> x == y
True
>>> x == z
True
>>> x == w
False
>>> id(x) == id(y)
True
>>> id(x) == id(z)
False
>>> id(x) == id(w)
False
>>> timeit.timeit('x==y', number=100000000, globals={'x': x, 'y': y})
3.893762200000083
>>> timeit.timeit('x==z', number=100000000, globals={'x': x, 'z': z})
4.205321462000029
>>> timeit.timeit('x==w', number=100000000, globals={'x': x, 'w': w})
4.15288594499998

It's always faster to compare objects having the same id (as you can notice from the example, the comparison between x and z is slower compared to the comparison between x and y, and that's because x and z do not share the same id).


提交答案