расход времени на применение алгоритма Бойера-Мура

Александр Петросян (PAF) 26.05.2005 12:32 / 26.05.2005 12:35

имеет смысл только при определённых ситуациях.
причём дело не столько в длине строки
сколько в том, сколько раз в этой строке мы намерены что-то искать.
или намерены ли мы там искать сложное выражение или простое.

оценка количества сравнений при простом поиске «N*M» = оценка сверху, типичные ситуации я бы оценил в N*(M/10).


.NET
насколько я понял завёрнутый код
\sscli\fx\src\regex\system\text\regularexpressions\regexfcd.cs, метод Prefix
там применяется некая хитрая эвристика чтобы решить — применять ли BM алгоритм.

для однократного поиска простой строки расход времени на предварительный просмотр всей строки — непозволительная роскошь.

поэтому рассуждения в приведённой статье, вероятно, относятся к многократным поискам данных внутри одной и той же строки. автор об этом ничего не пишет.

могу предположить, что он банально проделал некорректный эксперимент, поставив проблемную операцию в цикл и получив данные, что match быстрее.

если же в цикле применять алгоритм к разным входным строкам, то, уверен, простой однократный поиск подстроки положит match на все лопатки.

Perl
там пользователю предлагается самому решить, собирается ли он искать в строке многократно или сложные вещи, и на то есть отдельный оператор
«study»

Parser
в используемой у нас библиотеке PCRE необходимый функционал присутствует.
вариант:

$studied[^string.study[]]
^string.match[$studied][regex][options]

так будет немного похоже на Perl, но мне это нравится мало, поскольку не в духе Parser.

вариант:

^string.study[]
^string.match[regex][options]

так совсем похоже на Perl, однако несколько замедлит все match, поскольку перед match надо будет посмотреть, нет ли у нас данных от study.

диагноз: я не считаю, что задачи, стоящие перед нами требуют интенсивных регулярных выражений, работающих с большими строками — обычно поиск/замена идёт в небольшом куске, соответственно, ускорять их не нужно.

---