Реализован ли 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. Поэтому, хотя всем вокруг может быть очевидно, как просто найти исходный код, необходимый для поиска ответа, для меня это не так просто.

Вам просто интересно узнать о реализации? Или речь идет о чем-то практическом? О наблюдаемом поведении? (Например, какие результаты вы получаете или как быстро вы их получаете.)

no comment 02.07.2024 18:29

@nocomment, мне было интересно узнать о практических аспектах производительности (насколько быстро и в каких случаях). Ответ Вима — отличное место для меня, чтобы начать понимать такие вещи, как просмотр исходного кода Python.

Alexander Ites 02.07.2024 20:02

Помните, что любой алгоритм, работающий в прямом направлении, также работает и в обратном направлении. Память не волнует.

Tim Roberts 02.07.2024 20:11
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
4
3
84
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

В источниках легче ориентироваться, если вы знакомы с историей Python. В частности, тип str исторически назывался unicode в CPython и до сих пор называется unicode в источниках 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_slice
  • ucs2lib_rfind_slice
  • ucs4lib_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). Итак, вопрос остается без ответа, теперь речь идет о том, что делают эти звонки.

no comment 02.07.2024 18:27

Кстати, что это за REPL?

no comment 02.07.2024 18:37

@PeteKirkham Спасибо - я все еще нюхал след символов после отсутствия комментариев (так в оригинале). Не будете ли вы так любезны, отредактируйте ответ напрямую?

wim 02.07.2024 18:38

Отличный ответ! Я понятия не имел, что кроличья нора такая глубокая. Судя по результатам timeit, есть некоторая логика в выборе направления итерации в зависимости от количества элементов/символов, если я правильно понял цифры. Что интересно, кажется, что 1000 строк элементов/символов обрабатываются rfind с использованием прямой итерации, а не обратной в случае строк ASCII.

Alexander Ites 02.07.2024 19:59

@nocomment Это REPL для IPython, но я установил IPython.terminal.promts.ClassicPrompts в свои файлы запуска, потому что мне не нравятся In [1]: , Out[1]:.

wim 02.07.2024 20:08

@AlexanderItes «похоже, что 1000 элементов/строк символов обрабатываются rfind с использованием прямой итерации, а не обратной» - Что заставляет вас так говорить? Когда буква «y» стоит в начале, это на 5 нс медленнее.

no comment 02.07.2024 20:35

@wim Этот параметр также позволяет использовать timeit вместо %timeit? Я никогда не видел его без %.

no comment 02.07.2024 20:36

@nocomment Я считаю, что интерактивный IPython по умолчанию позволяет вызывать подобную магию, это не связано с классическими подсказками.

wim 02.07.2024 20:39

Кажется, вы искали только случай, когда подстрока представляет собой один символ. Вопрос не имеет такого ограничения.

no comment 02.07.2024 20:57

Вы правы, обновлено. Кроличья нора становится все глубже.

wim 02.07.2024 21:11

Другие вопросы по теме