为什么字符串的 startswith 比 in 慢？

Question

令人惊讶的是，我发现 startswith 比 in 慢：

In [10]: s="ABCD"*10

In [11]: %timeit s.startswith("XYZ")
1000000 loops, best of 3: 307 ns per loop

In [12]: %timeit "XYZ" in s
10000000 loops, best of 3: 81.7 ns per loop

众所周知，in操作需要搜索整个字符串，而startswith只需要检查前几个字符，所以startswith应该更有效率。

当s足够大时，startswith更快：

In [13]: s="ABCD"*200

In [14]: %timeit s.startswith("XYZ")
1000000 loops, best of 3: 306 ns per loop

In [15]: %timeit "XYZ" in s
1000000 loops, best of 3: 666 ns per loop

所以调用 startswith 似乎有一些开销，当字符串很小时它会变慢。

然后我试图弄清楚 startswith 调用的开销是多少。

首先，我使用了一个 f 变量来减少点操作的成本 - 如本 answer 所述 - 这里我们可以看到 startswith 仍然较慢：

In [16]: f=s.startswith

In [17]: %timeit f("XYZ")
1000000 loops, best of 3: 270 ns per loop

此外，我测试了空函数调用的成本：

In [18]: def func(a): pass

In [19]: %timeit func("XYZ")
10000000 loops, best of 3: 106 ns per loop

不考虑点运算和函数调用的成本，startswith的时间约为（270-106）=164ns，而in运算仅需81.7ns。 startswith好像还有一些开销，那是什么？

按照poke和lvc的建议在startswith和__contains__之间添加测试结果：

In [28]: %timeit s.startswith("XYZ")
1000000 loops, best of 3: 314 ns per loop

In [29]: %timeit s.__contains__("XYZ")
1000000 loops, best of 3: 192 ns per loop

Answer 1

这可能是因为 str.startswith() 比 str.__contains__() 做的更多，也因为我相信 str.__contains__ 完全在 C 中运行，而 str.startswith() 必须与 [= 交互17=] 类型。它的签名是 str.startswith(prefix[, start[, end]])，其中 prefix 可以是要尝试的字符串元组。

Answer 2

正如评论中已经提到的，如果你使用 s.__contains__("XYZ") 你会得到一个更类似于 s.startswith("XYZ") 的结果，因为它需要采用相同的路径：成员查找字符串对象，随后是函数调用。这通常有点贵（当然还不够你担心）。另一方面，当您执行 "XYZ" in s 时，解析器会解释运算符并可以缩短成员对 __contains__ 的访问（或者说它背后的实现，因为 __contains__ 本身是只是访问实现的一种方式）。

你可以通过查看字节码来了解这一点：

>>> dis.dis('"XYZ" in s')
  1           0 LOAD_CONST               0 ('XYZ')
              3 LOAD_NAME                0 (s)
              6 COMPARE_OP               6 (in)
              9 RETURN_VALUE
>>> dis.dis('s.__contains__("XYZ")')
  1           0 LOAD_NAME                0 (s)
              3 LOAD_ATTR                1 (__contains__)
              6 LOAD_CONST               0 ('XYZ')
              9 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             12 RETURN_VALUE

因此比较 s.__contains__("XYZ") 和 s.startswith("XYZ") 会产生更相似的结果，但是对于您的示例字符串 s，startswith 仍然会更慢。

为此，您可以检查两者的实现。有趣的是 contains implementation 是静态类型的，只是假设参数本身是一个 unicode 对象。所以这是相当高效的。

然而，startswith implementation 是一种“动态”Python 方法，需要实现来实际解析参数。 startswith 还支持元组作为参数，这使得整个方法的启动速度有点慢：（由我缩短，附上我的评论）：

static PyObject * unicode_startswith(PyObject *self, PyObject *args)
{
    // argument parsing
    PyObject *subobj;
    PyObject *substring;
    Py_ssize_t start = 0;
    Py_ssize_t end = PY_SSIZE_T_MAX;
    int result;
    if (!stringlib_parse_args_finds("startswith", args, &subobj, &start, &end))
        return NULL;

    // tuple handling
    if (PyTuple_Check(subobj)) {}

    // unicode conversion
    substring = PyUnicode_FromObject(subobj);
    if (substring == NULL) {}

    // actual implementation
    result = tailmatch(self, substring, start, end, -1);
    Py_DECREF(substring);
    if (result == -1)
        return NULL;
    return PyBool_FromLong(result);
}

这可能是 startswith 对于字符串较慢的一个重要原因，而 contains 因为它的简单性而很快。

为什么字符串的 startswith 比 in 慢？

Why is string's startswith slower than in?

python

cpython

startswith

python-2.7

python-internals