Алгоритм метода count в Python 3

#python #python_3x

Какой алгоритм использовали разработчики в методе count для строки в Python 3? Какая
сложность этого алгоритма?
    

Ответы

Ответ 1

Для стандартной реализации интерпретатора Python, т.е. CPython, насколько я понимаю,
верно следующее:

Для поиска количества вхождений паттерна в строку используется алгоритм Бойера —
Мура. Так как count возвращает количество неперекрывающихся вхождений подстроки в строку,
то сложность работы алгоритма Бойера — Мура будет составлять O(n + m), где n + m —
это сумма длин строки и паттерна.



Я не очень хорошо разбираюсь в структуре исходного кода CPython, но очень похоже,
что метод count действительно описан в файле count.h, приведённом @Suvitruf. Функция,
описанная в нём, содержит единственный вызов -- вызов функции FASTSEARCH, описание
которой я нашёл в файле fastsearch.h, которая содержит вариант алгоритма Бойера — Мура.



Источники:


исходный код count.h
исходный код fastsearch.h
описание алгоритма Бойера — Мура и его вариаций на википедии


Ответ 2

Ну, сам алгоритм вот:

#ifndef STRINGLIB_FASTSEARCH_H
#error must include "stringlib/fastsearch.h" before including this module
#endif

Py_LOCAL_INLINE(Py_ssize_t)
STRINGLIB(count)(const STRINGLIB_CHAR* str, Py_ssize_t str_len,
                const STRINGLIB_CHAR* sub, Py_ssize_t sub_len,
                Py_ssize_t maxcount)
{
    Py_ssize_t count;

    if (str_len < 0)
        return 0; /* start > len(str) */
    if (sub_len == 0)
        return (str_len < maxcount) ? str_len + 1 : maxcount;

    count = FASTSEARCH(str, str_len, sub, sub_len, maxcount, FAST_COUNT);

    if (count < 0)
        return 0; /* no match */

    return count;
}