Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 24
del
O(n) там. Потому что все циклы while на всех итерациях for суммарно выполнятся не более чем n раз. Потому что каждая итерация while уменьшает k но не перескакивает 0. А увеличивается k максимум n раз - по одному на каждой итерации for. Это называется амортизационный анализ.
Это практически тоже самое, только там цикл while заменен на адскую конструкцию из if и i--. Очень плохой подход, в этом коде весьма сложно разобраться. matchIndex - это та же префикс функция. Тут теже самые увеличения на 1 и переход назад по префикс функции.
Ну и, тут применена оптимизация: вместо подсчета префикс функции для текста "pattern$text" тут считается префикс функция только для шаблона, а потом тот же код крутится для текста, но уже ни в какой массив она не сохраняется, потому что префикс функция не может стать больше длины шаблона. Поэтому тут два последовательных цикла for. Это на скорость не влияет практически, но уменьшает потребление памяти.
ну это часть библиотеки, её задача работать максимально оптимально.
Ну авторам библиотеки же приходилось этот код читать, хотя бы во время работы над библиотекой?
Потом, этот подход нисколько не оптимальнее. Автор сэкономил на одном цикле, казалось бы, но на самом деле там теперь на каждую "итерацию" внутреннего while аж 2 проверки: итерация в for и проверка условия if. С циклом while же там только одна проверка, а проверки итеарции по i проходят только по одному разу. Так что даже с точки зрения количества операций там все хуже.
А уж как пляски с индексом i туда-сюда путают всякие спекулятивные подгрузки и исполнение в современных процессорах - это вообще загадка. Этот код может быть на порядки медленнее.
Ну и библиотечный код обычно все-таки стараются вылизывать, ведь это не для себя, это для людей. И куча глаз будет его читать так или иначе. Библиотека не самого высокого класса.
уменьшает потребление памяти
Уменьшение потребления памяти - это другая история. То же самое обычно делают и в той же реализации, что и у автора в статье, разбивая цикл for на 2 последовательных цикла. К извращению while -> if,i-- это не имеет отношения.
Я дал вам полный ответ. Там написан тот же самый алгоритм, только: извращенный control flow и вместо поиска префикс функции в "pattern$text" тут два последовательных цикла for по разным частям текста.
Так вроде бы KMP != построение префикс-функции для "pattern$text". KMP -- это префикс-функция для pattern и проход без доп. памяти по text, так что два последовательных цикла как раз каноничны, а конструкция "pattern$text" используется исключительно в образовательных целях
В этой реализации ищется только первое вхождение подстроки, а не все имеющиеся
Тут каждый шаг амортизированный
Вот как это выглядит:
Мы всегда на каждом шаге берем предыдущее значение k
Каждый заход в цикл while (k>0…){…} уменьшает текущее значение k минимум на 1
Таким образом если на шаге i мы уменьшили k на d (d<k), то следующий шаг может выполнить максимум O(k-d) операций (и далее по индукции можно доказать, что оно сходится к амортизированной O(1)
Каждый раз, пытаясь разобраться в этом алгоритме, понимаю, что это СЛОЖНА и забиваю.
В обычных условиях поиск подстроки в строке и так достаточно быстрый, чтобы упражняться в хитромудрых алгоритмах, придуманных в древности седовласыми мудрецами. Мой Grug мозг больше склоняется к простым, но понятным, а в значительном количестве случаев более быстрым решениям.
Самый простой и понятный способ ускорить - сравнивать сразу первые 4-8 символов за раз, храня их в единственной переменной и используя хитрости битовых сдвигов. Это позволяет отфильтровать подавляющее большинство случаев, когда вхождение подстроки не найдено.
Ещё один подход - скользящее окно с XOR символов. Если этот XOR совпадает с таковым для искомой строки - можно проводить более детальное сравнение, которое в отличие от XOR учитывает порядок символов. На практике это тоже позволяет находить подстроку достаточно эффективно, т. к. совпадение XOR при несовпадении строки - достаточно редко. Дополнительно можно комбинировать этот подход с предыдущим.
В обычных условиях поиск подстроки в строке и так достаточно быстрый, чтобы упражняться в хитромудрых алгоритмах,
Даже на коротких строках это дает ускорение в несколько раз над наивным алгоритмом. И если вы строки много ищите, даже короткие, имеет смысл применить оптимизацию. И это точно не повиснет на каких-нибудь патологических тестах, как все ваши последующие предложения.
Ещё один подход - скользящее окно с XOR символов.
Это здравая идея. Это чуть-чуть допилить, и будет метод полиномиального хеширования.
Спасибо за материал!
Прошу объяснить зачем при каждом заходе в for делается присвоение
int k = pi[i - 1];
ведь значение k наследуется из предыдущей итерации. Достаточно до входа в цикл задать
int k = 0.
Это особенность плюсов?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Доктора Кнут, Моррис и Пратт, или Как я перестал бояться и полюбил префикс-функцию