为什么startwith比切片慢

Why is the implementation of startwith slower than slicing?

为什么startwith的实现比切片慢？

In [1]: x = 'foobar'

In [2]: y = 'foo'

In [3]: %timeit x.startswith(y)
1000000 loops, best of 3: 321 ns per loop

In [4]: %timeit x[:3] == y
10000000 loops, best of 3: 164 ns per loop

Surprisingly, even including calculation for the length, slicing still appears significantly faster:

令人惊讶的是，即使包括计算长度，切片仍然显得更快：

In [5]: %timeit x[:len(y)] == y
1000000 loops, best of 3: 251 ns per loop

Note: the first part of this behaviour is noted in Python for Data Analysis (Chapter 3), but no explanation for it is offered.

注意：此行为的第一部分在Python for Data Analysis（第3章）中有说明，但没有提供解释。

。

If helpful: here is the C code for startswith; and here is the output of dis.dis:

如果有用：这是startwith的C代码;这是dis.dis的输出：

In [6]: import dis

In [7]: dis_it = lambda x: dis.dis(compile(x, '<none>', 'eval'))

In [8]: dis_it('x[:3]==y')
  1           0 LOAD_NAME                0 (x)
              3 LOAD_CONST               0 (3)
              6 SLICE+2             
              7 LOAD_NAME                1 (y)
             10 COMPARE_OP               2 (==)
             13 RETURN_VALUE        

In [9]: dis_it('x.startswith(y)')
  1           0 LOAD_NAME                0 (x)
              3 LOAD_ATTR                1 (startswith)
              6 LOAD_NAME                2 (y)
              9 CALL_FUNCTION            1
             12 RETURN_VALUE

5 个解决方案

#1

Some of the performance difference can be explained by taking into account the time it takes the . operator to do its thing:

一些性能差异可以通过考虑它所花费的时间来解释。操作员做它的事情：

>>> x = 'foobar'
>>> y = 'foo'
>>> sw = x.startswith
>>> %timeit x.startswith(y)
1000000 loops, best of 3: 316 ns per loop
>>> %timeit sw(y)
1000000 loops, best of 3: 267 ns per loop
>>> %timeit x[:3] == y
10000000 loops, best of 3: 151 ns per loop

Another portion of the difference can be explained by the fact that startswith is a function, and even no-op function calls take a bit of time:

另一部分差异可以通过以下事实来解释：startswith是一个函数，甚至无操作函数调用也需要一些时间：

>>> def f():
...     pass
... 
>>> %timeit f()
10000000 loops, best of 3: 105 ns per loop

This does not totally explain the difference, since the version using slicing and len calls a function and is still faster (compare to sw(y) above -- 267 ns):

这并不完全解释差异，因为使用切片和len的版本调用函数并且仍然更快（与上面的sw（y）相比 - 267 ns）：

>>> %timeit x[:len(y)] == y
1000000 loops, best of 3: 213 ns per loop

My only guess here is that maybe Python optimizes lookup time for built-in functions, or that len calls are heavily optimized (which is probably true). It might be possible to test that with a custom len func. Or possibly this is where the differences identified by LastCoder kick in. Note also larsmans' results, which indicate that startswith is actually faster for longer strings. The whole line of reasoning above applies only to those cases where the overhead I'm talking about actually matters.

我唯一的猜测是，Python可能会优化内置函数的查找时间，或者len调优被大量优化（这可能是真的）。有可能使用自定义len函数测试它。或者这可能是LastCoder确定的差异所在。请注意larsmans的结果，这表明对于更长的字符串，startswith实际上更快。上面的整个推理仅适用于那些我正在谈论的开销实际上很重要的情况。

#2

The comparison isn't fair since you're only measuring the case where startswith returns True.

比较是不公平的，因为您只测量startswith返回True的情况。

>>> x = 'foobar'
>>> y = 'fool'
>>> %timeit x.startswith(y)
1000000 loops, best of 3: 221 ns per loop
>>> %timeit x[:3] == y  # note: length mismatch
10000000 loops, best of 3: 122 ns per loop
>>> %timeit x[:4] == y
10000000 loops, best of 3: 158 ns per loop
>>> %timeit x[:len(y)] == y
1000000 loops, best of 3: 210 ns per loop
>>> sw = x.startswith
>>> %timeit sw(y)
10000000 loops, best of 3: 176 ns per loop

Also, for much longer strings, startswith is a lot faster:

此外，对于更长的字符串，startswith更快：

>>> import random
>>> import string
>>> x = '%030x' % random.randrange(256**10000)
>>> len(x)
20000
>>> y = r[:4000]
>>> %timeit x.startswith(y)
1000000 loops, best of 3: 211 ns per loop
>>> %timeit x[:len(y)] == y
1000000 loops, best of 3: 469 ns per loop
>>> sw = x.startswith
>>> %timeit sw(y)
10000000 loops, best of 3: 168 ns per loop

This is still true when there's no match.

当没有匹配时，这仍然是正确的。

# change last character of y
>>> y = y[:-1] + chr((ord(y[-1]) + 1) % 256)
>>> %timeit x.startswith(y)
1000000 loops, best of 3: 210 ns per loop
>>> %timeit x[:len(y)] == y
1000000 loops, best of 3: 470 ns per loop
>>> %timeit sw(y)
10000000 loops, best of 3: 168 ns per loop
# change first character of y
>>> y = chr((ord(y[0]) + 1) % 256) + y[1:]
>>> %timeit x.startswith(y)
1000000 loops, best of 3: 210 ns per loop
>>> %timeit x[:len(y)] == y
1000000 loops, best of 3: 442 ns per loop
>>> %timeit sw(y)
10000000 loops, best of 3: 168 ns per loop

So, startswith is probably slower for short strings because it's optimized for long ones.

因此，对于短字符串，startswith可能更慢，因为它针对长字符串进行了优化。

(Trick to get random strings taken from this answer.)

（欺骗从这个答案中获取随机字符串。）

#3

startswith is more complex than slicing...

startwith比切片更复杂......

2924 result = _string_tailmatch(self,
2925 PyTuple_GET_ITEM(subobj, i),
2926 start, end, -1);

This isn't a simple character compare loop for needle in beginning of haystack that's happening. We're looking at a for loop that is iterating through a vector/tuple (subobj) and calling another function (_string_tailmatch) on it. Multiple function calls have overhead with regards to the stack, argument sanity checks etc...

这不是干草堆开始时针头的简单字符比较循环。我们正在寻找一个for循环，它遍历vector / tuple（subobj）并在其上调用另一个函数（_string_tailmatch）。多个函数调用有关于堆栈，参数健全性检查等的开销。

startswith is a library function while the slicing appears to be built into the language.

startswith是一个库函数，而切片似乎内置于该语言中。

2919 if (!stringlib_parse_args_finds("startswith", args, &subobj, &start, &end))
2920 return NULL;

#4

To quote the docs, startswith does more you might think:

引用文档，startwith做了更多你可能想到的：

str.startswith(prefix[, start[, end]])

str.startswith（前缀[，start [，end]]）

Return True if string starts with the prefix, otherwise return False. prefix can also be a tuple of prefixes to look for. With optional start, test string beginning at that position. With optional end, stop comparing string at that position.

如果字符串以前缀开头，则返回True，否则返回False。前缀也可以是要查找的前缀元组。使用可选的启动，测试字符串从该位置开始。使用可选结束，停止比较该位置的字符串。

#5

Calling a function is quite expensive. I don't know, however, if this is the case as well for built-in functions written in C.

调用函数非常昂贵。但是，我不知道是否也是用C编写的内置函数的情况。

Be aware, though, that slicing may involve a function call as well depending on the object which is used.

但请注意，切片可能还涉及函数调用，具体取决于所使用的对象。

#1