比较startswith()和in()的速度

Question

我曾以为startswith必须比in更快，因为in需要进行更多的检查（允许搜索的单词可以在字符串中的任何位置）。但我有些怀疑，所以我决定使用timeit来测试一下。如下是计时代码，您可能会注意到我并没有做太多计时；这段代码非常简单。

import timeit

setup1='''
def in_test(sent, word):
    if word in sent:
        return True
    else:
        return False
'''

setup2='''
def startswith_test(sent, word):
    if sent.startswith(word):
        return True
    else:
        return False
'''

print(timeit.timeit('in_test("this is a standard sentence", "this")', setup=setup1))
print(timeit.timeit('startswith_test("this is a standard sentence", "this")', setup=setup2))

结果：

>> in:         0.11912814951705597
>> startswith: 0.22812353561129417

所以startswith要慢两倍！...鉴于我之前的说法，我觉得这种行为非常令人困惑。我在计时这两个函数时是否做错了什么，或者in确实更快？如果是这样，为什么呢？

请注意，即使它们都返回False，结果也非常相似（在这种情况下，in必须在简单的短路之前实际遍历整个句子）：

print(timeit.timeit('in_test("another standard sentence, would be that", "this")', setup=setup1))
print(timeit.timeit('startswith_test("another standard sentence, would be that", "this")', setup=setup2))

>> in:         0.12854891578786237
>> startswith: 0.2233201940338861

如果我需要从头开始实现这两个函数，它们大致如下（伪代码）： startswith：一次一个地将word的字母与sentence的字母进行比较，直到a）用尽word（返回True）或b）检查返回False（返回False） in：对于可以在sentence中找到word的初始字母的每个位置调用startswith。

我就是不明白...

---

请注意，in和startswith是不等价的；我只是谈论需要在字符串中找到的单词必须是第一个的情况。

- Ma0

Answer 1

这是因为你需要查找和调用一个方法。 in 是专门的，直接导致 COMPARE_OP (调用 cmp_outcome，进而调用 PySequence_Contains)，而 str.startswith 经过较慢的字节码处理：

2 LOAD_ATTR                0 (startswith)
4 LOAD_FAST                1 (word)
6 CALL_FUNCTION            1              # the slow part

将 in 替换为 __contains__，并强制在该情况下进行函数调用，基本上抵消了速度差异：

setup1='''
def in_test(sent, word):
    if sent.__contains__(word):
        return True
    else:
        return False
'''

而且，时间安排如下：

print(timeit.timeit('in_test("this is a standard sentence", "this")', setup=setup1))
print(timeit.timeit('startswith_test("this is a standard sentence", "this")', setup=setup2))
0.43849368393421173
0.4993997460696846

"in在这里胜出，因为它不需要经过整个函数调用设置，并且由于它所呈现的有利情况。"

- Dimitris Fasarakis Hilliard

---

优化的情况似乎没有这样的影响，悲观的情况产生了相同的结果。更像是字符串的长度和“startswith”的开销。 - Ma0

我应该更加详细一些 @Ev.Kounis :-) 我所指的是长度是有利的情况。在一个小字符串中是否匹配并不会产生太大的差异。 - Dimitris Fasarakis Hilliard

现在我们又回到了同一页 xD。 - Ma0

cmp_outcome 链接 https://github.com/python/cpython/blob/4a8bcdf79cdb3684743fe1268de62ee88bada439/Python/ceval.c#L4933 - Roney Island

Answer 2

你正在比较对字符串的操作和属性查找以及函数调用。即使第一个操作在大量数据上需要很长时间，第二个操作的开销也会更高一些。此外，如果你想要查找第一个单词，如果匹配成功，“in” 将查看与 “startswith()” 相同数量的数据。为了看到区别，你应该考虑悲观情况（找不到结果或在字符串结尾处匹配）。

setup1='''
data = "xxxx"*1000
def ....

print(timeit.timeit('in_test(data, "this")', setup=setup1))
0.932795189000899
print(timeit.timeit('startswith_test(data, "this")', setup=setup2))
0.22242475600069156

- viraptor

---

感谢您的回答。悲观情况已经在编辑后的帖子中了。 - Ma0

你的悲观案例非常简短。看着4个字符与40个字符相比只是一个舍入误差。但当你将4与4000进行对比时，才能真正看到差异。 - viraptor

我了解，但我想使用其中一种来检查这样的小句子而不是整个文本。但现在它有更多意义了。 - Ma0

所以我们可以争论in是O(n)，而startswith是O(c)，但对于小的n来说，O(n)更好，对吧？ - Ma0

没错 :) 就是这样 - viraptor

Answer 3

如果您查看函数生成的字节码：

>>> dis.dis(in_test)
  2           0 LOAD_FAST                1 (word)
              3 LOAD_FAST                0 (sent)
              6 COMPARE_OP               6 (in)
              9 POP_JUMP_IF_FALSE       16

  3          12 LOAD_CONST               1 (True)
             15 RETURN_VALUE

  5     >>   16 LOAD_CONST               2 (False)
             19 RETURN_VALUE
             20 LOAD_CONST               0 (None)
             23 RETURN_VALUE

你会注意到有很多与字符串匹配无直接关系的开销。在一个更简单的函数上进行测试：

def in_test(sent, word):
    return word in sent

会更可靠。

- Błotosmętek