Comments 24
KMP люблю и сам его писал в 90-00-е еще до изучения в 2018, но совсем не понимаю теоретическую составляющую с функциями и пи. Алгоритм очень интересный и для меня всегда было загадкой почему не во всех языках он реализован в стандартных библиотеках при работе со строками.
del
for (int i = 1; i < n; i++) {
int k = pi[i - 1];
while (k > 0 && s[i] != s[k]) {
k = pi[k - 1];
}
if (s[i] == s[k]) {
k++;
}
pi[i] = k;
}В общем читал-читал описание доказательства, и как отмечал выше оно мне непонятно в силу моих неспособностей, но вот смотрю на код и на ваше утверждение про while и n-1 и получается что у вас сложность O(n*n) так что вопрос линейного времени тут не самый главный.
Вообще я не помню в KMP такого способа построения суффиксов, мне кажется там O(n) должно быть. Надо поискать свои старые исходники.
O(n) там. Потому что все циклы while на всех итерациях for суммарно выполнятся не более чем n раз. Потому что каждая итерация while уменьшает k но не перескакивает 0. А увеличивается k максимум n раз - по одному на каждой итерации for. Это называется амортизационный анализ.
Спасибо за разъяснение.
Подскажите еще, есть вот такая реализация KMP (C#):
/// <summary>
/// Knuth–Morris–Pratt(KMP) string search implementation.
/// </summary>
public class Kmp
{
/// <summary>
/// Returns the start index of first appearance
/// of pattern in input string.
/// Returns -1 if no match.
/// </summary>
public int Search(string input, string pattern)
{
var matchingInProgress = false;
var matchIndex = new int[pattern.Length];
var j = 0;
//create match index of chars
//to keep track of closest suffixes in pattern that form prefix of pattern
for (var i = 1; i < pattern.Length; i++)
//prefix don't match suffix anymore
if (!pattern[i].Equals(pattern[j]))
{
//don't skip unmatched i for next iteration
//since our for loop increments i
if (matchingInProgress) i--;
matchingInProgress = false;
//move back j to the beginning of last matched char
j = matchIndex[j == 0 ? 0 : j - 1];
}
//prefix match suffix so far
else
{
matchingInProgress = true;
//increment index of suffix
//to prefix index for corresponding char
matchIndex[i] = j + 1;
j++;
}
matchingInProgress = false;
//now start matching
j = 0;
for (var i = 0; i < input.Length; i++)
if (input[i] == pattern[j])
{
matchingInProgress = true;
j++;
//match complete
if (j == pattern.Length) return i - pattern.Length + 1;
}
else
{
//reduce i by one so that next comparison won't skip current i
//which is not matching with current j
//since our for loop increments i
if (matchingInProgress) i--;
matchingInProgress = false;
//jump back to closest suffix with prefix of pattern
if (j != 0) j = matchIndex[j - 1];
}
return -1;
}
}И тут нет классической схемы как в статье, этот вариант лучше/хуже? Я понимаю что оба варианта по сложности будут O(n) но важно так же это 129*n против 5*n или нет.
Это практически тоже самое, только там цикл while заменен на адскую конструкцию из if и i--. Очень плохой подход, в этом коде весьма сложно разобраться. matchIndex - это та же префикс функция. Тут теже самые увеличения на 1 и переход назад по префикс функции.
Ну и, тут применена оптимизация: вместо подсчета префикс функции для текста "pattern$text" тут считается префикс функция только для шаблона, а потом тот же код крутится для текста, но уже ни в какой массив она не сохраняется, потому что префикс функция не может стать больше длины шаблона. Поэтому тут два последовательных цикла for. Это на скорость не влияет практически, но уменьшает потребление памяти.
Очень плохой подход, в этом коде весьма сложно разобраться
ну это часть библиотеки, её задача работать максимально оптимально. А понимать чужой код я вообще не могу (практически) так что для меня оба варианта одинаковые.
ну это часть библиотеки, её задача работать максимально оптимально.
Ну авторам библиотеки же приходилось этот код читать, хотя бы во время работы над библиотекой?
Потом, этот подход нисколько не оптимальнее. Автор сэкономил на одном цикле, казалось бы, но на самом деле там теперь на каждую "итерацию" внутреннего while аж 2 проверки: итерация в for и проверка условия if. С циклом while же там только одна проверка, а проверки итеарции по i проходят только по одному разу. Так что даже с точки зрения количества операций там все хуже.
А уж как пляски с индексом i туда-сюда путают всякие спекулятивные подгрузки и исполнение в современных процессорах - это вообще загадка. Этот код может быть на порядки медленнее.
Ну и библиотечный код обычно все-таки стараются вылизывать, ведь это не для себя, это для людей. И куча глаз будет его читать так или иначе. Библиотека не самого высокого класса.
Ну авторам библиотеки же приходилось этот код читать, хотя бы во время работы над библиотекой?
я не считаю что красота кода - это важное для работы библиотеки, вся суть разработки за последние 50 лет сводилась к использованию тех или иных хаков, что положительно сказывается на скорости или потреблении памяти. Красота кода - это новое современное явление, даже 10 лет назад об этом было сильно меньше разговоров чем сегодня. А авторам вообще удобно так, как им удобно, а не как тут мы на хабре решим. (и автор, насколько я помню - один)
Потом, этот подход нисколько не оптимальнее. Автор сэкономил на одном цикле, казалось бы, но на самом деле там теперь на каждую "итерацию" внутреннего while аж 2 проверки: итерация в for и проверка условия if. С циклом while же там только одна проверка, а проверки итеарции по i проходят только по одному разу. Так что даже с точки зрения количества операций там все хуже.
Ну это другой разговор, вы же раньше написали что Это практически тоже самое и уменьшает потребление памяти что "немного" отличается от этот подход нисколько не оптимальнее хотя я изначально об этом и спрашивал.
А уж как пляски с индексом i туда-сюда путают всякие спекулятивные подгрузки и исполнение в современных процессорах - это вообще загадка. Этот код может быть на порядки медленнее.
Без бенчмарков разговоры о "порядках" не имеют смысла. И я скоро выпущу статью про черепах в лабиринте, наконец-то, и там ваши слова и код сильно разнятся по финальной производительности, так что я вам в голословных утверждениях несколько не доверяю.
Ну и библиотечный код обычно все-таки стараются вылизывать, ведь это не для себя, это для людей
Ну мы по-разному понимаем это. Для меня библиотечный код - это то, куда я точно не полезу, поэтому мне нет никакой разницы через while оно сделано или через if. Я установлю библиотеку, прогоню бенчи и сделаю выбор, а сколько кодеров-перфекционистов при этом пострадало - не важно.
И куча глаз будет его читать так или иначе. Библиотека не самого высокого класса.
У автора не было цели создавать библиотеку самого высокого класса. Он её писал для себя и много лет ей пользовался, а потом оформил в виде пакета. Человек проделал огромный труд для себя и поделился с другими, можете не пользоваться, никто не принуждает же.
99% программистов-перфекционистов вообще никаких библиотек не пишут и ничего не публикуют - так какая от них польза, только что прочитать какие все плохие?
уменьшает потребление памяти
Уменьшение потребления памяти - это другая история. То же самое обычно делают и в той же реализации, что и у автора в статье, разбивая цикл 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.
Это особенность плюсов?
Доктора Кнут, Моррис и Пратт, или Как я перестал бояться и полюбил префикс-функцию