6

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

1
  • Нужно понимать, что разработчики каждого интерпретатора могут выбирать произвольную реализацию, которая будет соответствовать стандарту языка. Насколько я понимаю, вы говорите про CPython. Думаю, это стоит явно указать в вопросе. 22 ноя 2015 в 7:16

2 ответа 2

10

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

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


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


Источники:

3
  • сам Boyer-Moore алгоритм с упрощениями от Horspool и Sunday описан в effbot.org/zone/stringlib.htm (там же реализация на чистом Питоне (псевдо-код)). Описание говорит, что требование O(nm) в худшем случае.
    – jfs
    22 ноя 2015 в 10:50
  • @jfs если я правильно понял, то это в общем случае, когда ищутся все вхождения (в том числе и перекрывающиеся). В описании функции count этот вариант, вероятно специально, был убран. В случае же отсутствия перекрытий сложность алгоритма уменьшается. 22 ноя 2015 в 17:33
  • точная цитата: "no worse than the current algorithm in worst case (O(nm))", то есть фактический алгоритм может быть лучше. Хотя я не вижу улучшений для count случая по сравнению с псевдо-кодом из статьи с цитатой.
    – jfs
    23 ноя 2015 в 8:39
3

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

#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;
}
1
  • Как можно заметить, здесь нет самого алгоритма, весь алгоритм спрятан в функции FASTSEARCH 22 ноя 2015 в 6:46

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.