Почему startswith медленнее, чем нарезка

Почему реализация 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

Удивительно, что даже включая вычисление длины, нарезка все еще выглядит значительно быстрее:

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

Примечание: первая часть этого поведения отмечена в Python для анализа данных (глава 3), но никаких объяснений для этого не предлагается.

Если полезно: вот код C для startswith; и вот вывод 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

Ответ 1

Некоторая разница в производительности может быть объяснена с учетом времени, которое требуется оператору . для выполнения своей задачи:

>>> 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

Другая часть разницы может быть объяснена тем, что startswith является функцией, и даже вызовы функции no-op занимают немного времени:

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

Это не полностью объясняет разницу, так как версия с использованием slicing и len вызывает функцию и все еще быстрее (сравните с sw(y) выше - 267 нс):

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

Мое единственное предположение: возможно, Python оптимизирует время поиска для встроенных функций или что вызовы len сильно оптимизированы (что, вероятно, верно). Возможно, это будет возможно проверить с помощью пользовательской функции len. Или, возможно, именно здесь выявлены отличия, отмеченные LastCoder. Заметьте также larsmans, что указывает на то, что startswith на самом деле быстрее для более длинных строк. Вся линия рассуждений выше относится только к тем случаям, когда накладные расходы, о которых я говорю, действительно имеют значение.

Ответ 2

Сравнение не справедливо, поскольку вы измеряете только случай, когда 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

Кроме того, для гораздо более длинных строк 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

Это все еще верно, если нет совпадения.

# 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

Итак, startswith, вероятно, медленнее для коротких строк, потому что он оптимизирован для длинных.

(Trick, чтобы получить случайные строки, взятые из этого ответа.)

Ответ 3

startswith сложнее, чем нарезка...

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

Это не простой цикл сравнения символов для иглы в начале стога сена, который происходит. Мы смотрим на цикл for, который выполняет итерацию через vector/tuple (subobj) и вызывает на нем другую функцию (_string_tailmatch). Множественные вызовы функций имеют накладные расходы в отношении стека, проверки рассуждений аргументов и т.д....

startswith является библиотечной функцией, в то время как нарезка кажется встроенной в язык.

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

Ответ 4

Чтобы процитировать документы, startswith, вы можете подумать больше:

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

Верните True, если строка начинается с префикса, в противном случае верните False. префикс также может быть кортежем для префиксов, которые нужно искать. С дополнительным start, тестовая строка, начинающаяся с этой позиции. С дополнительным концом, стоп сравнивая строку в этой позиции.

Ответ 5

Вызов функции довольно дорог. Я не знаю, однако, если это так и для встроенных функций, написанных на C.

Помните, однако, что нарезка может также включать вызов функции, в зависимости от используемого объекта.