Python: улучшение поиска подстроки путем внедрения сложных алгоритмов

Я расширяю свой предыдущий вопрос python эффективный поиск подстроки ,

Мне интересно улучшить производительность реализации поиска подстроки,

В некоторых ответах из моего предыдущего вопроса было указано, что поиск подстроки осуществляется с использованием fastsearch, который использует вдохновленный алгоритмом BM, вот исходный код

Больше ответов указало на реализацию алгоритма Бойера-Мура, алгоритма Рабина-Карпа.

будет ли эффективно внедрять c-код в качестве хорошей реализации поиска подстроки с использованием этих алгоритмов (BM, Rabin-Karp )?

One Solution collect form web for “Python: улучшение поиска подстроки путем внедрения сложных алгоритмов”

Вы не указали, что вы подразумеваете под «эффективным». Какие компромиссы вы готовы сделать? Готовы ли вы заплатить цену за потерю производительности при инициализации новой строки? При запуске поиска? Не могли бы вы обменять больше памяти на более высокую скорость?

Разработчики python установили четкие цели, когда они разработали библиотеку строк python:

  • должен быть быстрее, чем текущий алгоритм грубой силы для всех тестовых случаев (на основе реального кода), включая худший случай Джима Хьюгунина
  • небольшие накладные расходы; нет динамического распределения в быстром пути (O (m) для скорости, O (1) для хранения)
  • сублинейное поведение поиска в хороших случаях (O (n / m))
  • не хуже текущего алгоритма в худшем случае (O (nm))
  • должен хорошо работать как для 8-битных строк, так и для 16-битных или 32-разрядных строк Unicode (без зависимостей O (σ)),
  • многие поиски в реальной жизни должны быть хорошими, очень немногие должны быть в худшем случае
  • достаточно простая реализация

Таким образом, разработчики установили некоторые ограничения на производительность для случая поиска и случая установки, требований к хранению, а также эффективности обслуживания. Эти границы исключали Boyer-Moore (так как это требует предварительной обработки строки поиска, стоимости запуска и стоимости хранения), и, хотя я не вижу никаких доказательств того, что разработчики считают Rabin-Karp, это может быть исключено на том же (вам нужно создать хэши и сохранить их).

Границы были установлены на основе множества внутренних компонентов python и опыта использования. Вышеприведенное резюме не было извлечено из воздуха, это всего лишь краткое изложение этого опыта.

Теперь, если у вас есть конкретный случай, когда ваши компромиссы могут быть установлены по-разному, то, конечно, реализация C другого алгоритма вполне может превзойти стандартную реализацию Python. Но он будет более эффективным в соответствии с другим набором критериев.

В любом случае алгоритм поиска Python имеет дело с малым строковым случаем. Если вы попытаетесь применить его к большому тексту текста, алгоритмы не смогут выполнять так же хорошо, как и другие, которые хорошо подходят для больших текстов. И если вам пришлось искать текст через 10 000 000 документов, вы хотели бы использовать какое-то средство индексирования вместо тонкого небольшого поиска строки python.

Сравните это с тем, чтобы сортировать список из 100 элементов с реализацией сортировки по умолчанию, а также сортировать 10 000 000 000 целых чисел. В последнем случае существуют варианты сортировки, которые могут легко превзойти предложение Python по умолчанию.

Следует также отметить, что Python имеет историю инноваций алгоритмов; стандартным алгоритмом сортировки в Python является TimSort , новый алгоритм, изобретенный Тимом Петерсом в соответствии с прагматичными реальными обстоятельствами, с которыми приходится иметь дело с интерпретатором Python. С тех пор этот алгоритм был установлен по умолчанию в Java и платформе Android. Таким образом, я склонен доверять решениям разработчиков Python.

Насколько я знаю, никто не ввел другую реализацию, так как замена по умолчанию не будет работать без исправления кода Python C. Разумеется, вы можете легко создать специализированный тип строки, который реализует другой алгоритм поиска. Там могут быть библиотеки, которые используют C для специализированных алгоритмов поиска, которые используют Boyer-Moore, Rabin-Karp или любой другой алгоритм, так как это может быть лучшим выбором для их конкретной проблемной области.

  • Подписание RSA и верификация с помощью C #, BouncyCastle и импортированного ключа RSA - пример рабочего Python и нерабочий образец кода C # внутри
  • Cython & C ++: передача по ссылке
  • .NET Regex Неопознанная структура группировки
  • использование stdint с swig и numpy.i
  • Почему операции std :: string работают плохо?
  • Соответствие строк: gcc и CPython
  • Установка метакласса завернутого класса с помощью Boost.Python
  • Почему -1/2 оценивается как 0 в C ++, но -1 в Python?
  • Python - лучший язык программирования в мире.