为什么字符串的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 变量来减少点运算的成本 - 就像这个 答案 中提到的那样 - 但我们可以看到 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

- WKPlus

---

为了获得更相似的结果，您可以执行s.__contains__("XYZ")，因为这将采用与s.startswith("XYZ")相同的路线（使用in运算符将快捷成员访问）。然而，对我来说，startswith仍然较慢。 - poke

我认为性能差异的剩余部分是由于__contains__在C中完全类型化，而startswith则执行实际的参数解析和其他操作（您还可以传递元组）。 - poke

你使用的Python版本是什么？在3.4.3上，我获得了s.startswith("XYZ")报告153ns和s.__contains__("XYZ")报告169ns。正如@poke所说，使用in将使用完全不同的查找规则，它可以直接从C级别的函数指针进行查找，而方法查找则需要进行两个字典搜索，然后必须进行Python级别的函数调用。分别计时这些操作可以给你一些关于差异的想法，但不一定是准确的。根据你的数据，减去这两个开销会使startswith的时间变为负数！ - lvc

我进一步检查了%timeit "XYZ" == s[0:3]，结果为10000000 loops, best of 3: 94 ns per loop，而%timeit "XYZ" in s的结果为10000000 loops, best of 3: 59.2 ns per loop。这是使用Python 3.4.3测试的。似乎在我的情况下，切片会带来一些额外的开销，因为%timeit "XYZ" in s[0:3]的结果为10000000 loops, best of 3: 101 ns per loop。 - Marandil

@LightnessRacesinOrbit 虽然这是正确的，但 s 是字符串 "ABCD" 的重复，因此必须搜索整个字符串才能得出结论，即 "XYZ" 不包含在内。 - poke

Answer 1

如评论中所述，如果您使用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仍然会更慢。

为了达到这个目的，您可以检查两者的实现。有趣的是，包含实现是静态类型的，并且假定参数本身就是Unicode对象。因此这很有效率。

startswith实现，然而是一种“动态”的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的字符串来说速度较慢的一个重要原因，因为后者更加简单。

- poke

---

实现的链接已经失效。 - mounaim

据@mounaim所说，Python的Mercurial服务器刚刚宕机了几秒钟。现在已经恢复正常了。 - poke

Answer 2

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

- Cyphase

---

“Does more”是含糊不清的，可能并不正确。高效地查找子字符串并非易事。算法列表。相比之下，查找前缀相当容易且通常更快。 - Paul Draper

你说得对@PaulDraper; 我写那篇文章时很晚:P。感谢@LightnessRacesinOrbit的编辑:)。 - Cyphase