Реализован ли s.rfind() в Python с использованием итераций в обратном направлении?
rfind перебирает строку от конца до начала?
Я прочитал документацию https://docs.python.org/3.12/library/stdtypes.html#str.rfind и вижу
str.rfind(sub[, начало[, конец]])
Возвращает наибольший индекс в строке, где найдена подстрока sub, такая, что sub содержится в s[start:end]. Необязательные аргументы start и end интерпретируются как в нотации среза. Возврат -1 в случае неудачи.
И документ мало что говорит о реализации. Возможно, где-то еще в документации есть примечания по реализации.
Я попытался найти исходный код с помощью своей IDE (визуальный код), и он показал мне что-то вроде заглушки интерфейса для какого-то скрытого собственного (C/C++) кода.
def rfind(self, sub: str, start: SupportsIndex | None = ..., end: SupportsIndex | None = ..., /) -> int: ...
Затем я попытался найти подходящий исходный код на Github в репозиториях Python, но это оказалось не так просто.
Я новичок в Python. Поэтому, хотя всем вокруг может быть очевидно, как просто найти исходный код, необходимый для поиска ответа, для меня это не так просто.
@nocomment, мне было интересно узнать о практических аспектах производительности (насколько быстро и в каких случаях). Ответ Вима — отличное место для меня, чтобы начать понимать такие вещи, как просмотр исходного кода Python.
Помните, что любой алгоритм, работающий в прямом направлении, также работает и в обратном направлении. Память не волнует.
Ответы 1
В источниках легче ориентироваться, если вы знакомы с историей Python. В частности, тип str исторически назывался unicode в CPython и до сих пор называется unicode в источниках C.
Итак, для строковых методов:
- заголовки находятся в Include/unicodeobject.h
- реализацию можно найти в Objects/unicodeobject.c
Python str.rfind в конечном итоге доберётся до C unicode_rfind_impl. В основной ветке вы можете найти автоматически сгенерированные объявления по адресу Objects/clinic/unicodeobject.c.h#L1074-L1116 и impl по адресу Objects/unicodeobject.c#L12721-L12731..
Примечание. Эти объявления, сгенерированные Argument Clinic , являются относительно недавней разработкой gh-117431: адаптируйте str.find и его друзей для использования соглашения о вызовах METH_FASTCALL (апрель 2024 г.), и они не используются ни в одной официально выпущенной версии. еще. Текущую версию 3.12.4 вам следует посмотреть непосредственно в unicodeobject.c.
Вы заметите, что unicode_rfind_impl вызывает Any_find_slice , передавая в направлении -1. Это direction <= 0 используется для выбора конкретной реализации в зависимости от ширины базового юникода:
asciilib_rfind_slice(для обеих строк ASCII)ucs1lib_rfind_sliceucs2lib_rfind_sliceucs4lib_rfind_slice
Эти вызовы попадают в подпрограммы stringlib ( stringlib/find.h:rfind_slice -> stringlib/find.h:rfind -> stringlib/fastsearch.h:FASTSEARCH ). Затем, для особого случая односимвольной подстроки, мы продолжаем stringlib/fastsearch.h:rfind_char и в конечном итоге оказываемся здесь , где CPython, похоже, использует либо memrchr , либо обратную итерацию , в зависимости от версии glibc. Для более длинных подстрок мы идем в stringlib/fastsearch.h:default_rfind , реализованный здесь , который выглядит как своего рода алгоритм Бойера-Мура с фильтром Блума . старая страница effbot описывает более раннюю версию этого кода как «упрощение (так в оригинале) Бойера-Мура, включающее идеи Хорспула и Санди… (с)… простым фильтром Блума», но реализация детали, возможно, несколько изменились с тех пор (2006 г.).
Наконец, вы можете использовать stdlib timeit в интерактивном режиме, чтобы эмпирически убедиться, что str.rfind не замедляется существенно при работе с более длинными строками. Само по себе это не гарантирует наличия обратной итерации, но это определенно свидетельствует о том, что реализация не является просто наивной итерацией с самого начала.
>>> s1 = 'x' * 1000 + 'y'
>>> s2 = 'x' * 1_000_000 + 'y'
>>> timeit s1.rfind('y')
68.7 ns ± 0.183 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
>>> timeit s2.rfind('y')
68.9 ns ± 0.00835 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
Сравните с буквой «y» в начале, когда мы переходим от нано к микро:
>>> s1 = 'y' + ('x' * 1000)
>>> s2 = 'y' + ('x' * 1_000_000)
>>> timeit s1.rfind('y')
73.6 ns ± 0.00866 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
>>> timeit s2.rfind('y')
22.3 μs ± 10.8 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
В any_find_slice нет итераций. Направление -1 используется только для выбора вызовов, например asciilib_rfind_slice(buf1, len1, buf2, len2, start, end). Итак, вопрос остается без ответа, теперь речь идет о том, что делают эти звонки.
Кстати, что это за REPL?
эти вызовы попадают в stringlib github.com/python/cpython/blob/… и либо использовать расширение gnu memrchr, либо выполнять итерацию в обратном направлении github.com/python/cpython/blob/…
@PeteKirkham Спасибо - я все еще нюхал след символов после отсутствия комментариев (так в оригинале). Не будете ли вы так любезны, отредактируйте ответ напрямую?
Отличный ответ! Я понятия не имел, что кроличья нора такая глубокая. Судя по результатам timeit, есть некоторая логика в выборе направления итерации в зависимости от количества элементов/символов, если я правильно понял цифры. Что интересно, кажется, что 1000 строк элементов/символов обрабатываются rfind с использованием прямой итерации, а не обратной в случае строк ASCII.
@nocomment Это REPL для IPython, но я установил IPython.terminal.promts.ClassicPrompts в свои файлы запуска, потому что мне не нравятся In [1]: , Out[1]:.
@AlexanderItes «похоже, что 1000 элементов/строк символов обрабатываются rfind с использованием прямой итерации, а не обратной» - Что заставляет вас так говорить? Когда буква «y» стоит в начале, это на 5 нс медленнее.
@wim Этот параметр также позволяет использовать timeit вместо %timeit? Я никогда не видел его без %.
@nocomment Я считаю, что интерактивный IPython по умолчанию позволяет вызывать подобную магию, это не связано с классическими подсказками.
Кажется, вы искали только случай, когда подстрока представляет собой один символ. Вопрос не имеет такого ограничения.
Вы правы, обновлено. Кроличья нора становится все глубже.
Вам просто интересно узнать о реализации? Или речь идет о чем-то практическом? О наблюдаемом поведении? (Например, какие результаты вы получаете или как быстро вы их получаете.)