olegchir 12 мар 2020 в 16:07

Пишем поиск подстроки лучше, чем в учебниках

9 мин

16K

Блог компании JUG Ru GroupJava*Алгоритмы*

Перевод

Жизнь инженера полна сюрпризов: особенно, когда приходится иметь дело с производительностью. Например, что произойдет, если попытаться запустить этот кусок Java-кода? Выглядит довольно невинно:

// Для использования String.repeat нужен JDK 11 и выше:
final var needle = "A".repeat(500000) + "B";
final var haystack = "A".repeat(1000000) + "B";
System.out.println(haystack.indexOf(needle));

Мы ждем, ждем, ждем… По крайней мере, на моем ноутбуке 2015 года c OpenJDK 13 поиск иголки в стоге сена занимает около минуты. Наша старая добрая JVM прошла сквозь десятилетия перформанс-тюнинга, в ней эффективно реализованы интринсики для String.indexOf и так далее. Что же могло пойти не так?

Это начало серии из нескольких статей, любезно предоставленных их автором, Linas Medžiūnas, и изначально опубликованых в блоге WiX Engineering.

Присмотритесь к тому, что передано на вход: данные специально выбраны так, чтобы достичь квадратичной производительности в худшем случае (O(nm), где n — длина haystack и m — длина needle) для наивного алгоритма поиска подстроки. Мы бежим по всем символам в haystack, и, если они совпадают с первыми символами needle, мы начинаем бежать по needle во внутреннем цикле — и так до первого несовпавшего символа.

Вы можете возразить, что пример этот бесполезен, ведь такие данные на вход были сконструированы и поданы специально, на практике вы с таким не встретитесь. Подумайте дважды. Что, если вы работаете над веб-сервисом, пользователи которого могут загружать произвольные строки, и где-то в глубине сервиса есть код, запускающий indexOf на этих строках? Тогда всего несклько злонамеренных запросов вроде приведенного выше поставят ваш сервис на колени. Стоит знать, как минимум, о худших случаях для подаваемых на вход данных.

К счастью, существуют алгоритмы подиска подстроки, имеющие линейную сложность (O(n+m)). У них нет проблем с данными из вышеописанного примера. Например, следующий код на Scala делает все то же самое, но выполняется за считаные миллисекунды на том же самом компьютере, той же самой JVM, и используя под капотом совершенно тот же java.lang.String:

val needle = "A" * 500000 + "B"
val haystack = "A" * 1000000 + "B"
println(haystack.indexOfSlice(needle))

Секрет огромной разницы находится внутри метода indexOfSlice, являющегося частью стандартной библиотеки Scala. Она реализует умный линейный алгоритм Кнута-Морриса-Пратта. И нет, я не утверждаю, что язык X лучше, чем язык Y. К сожалению, тут все куда сложнее! Например, indexOfSlice в Scala — это обобщенный метод, который работает не только со строками, но и на других последовательных коллекциях, и может сравнивать не только символы, но и элементы других типов. Он должен быть значительно медленней, чем String.indexOf из Java в среднем случае (об этом мы поговорим дальше). Таким образом, у нас есть эффективный алгоритм с куда лучшей производительностью в худшем случае, но в среднем он медленней, потому что в нем сильно больше константная часть. Дилеммы вроде этой — типичная проблема в тюнинге перформанса. Здесь нет никакой волшебной таблетки, которая решит все проблемы — нужно аккуратно анализировать проблему и делать правильные микробенчмарки.

Вы все еще со мной? Хорошо! Понимаете, это всего лишь вступление. Я хотел замотивировать вас разобраться с теоретической сложностью и практическим перформансом алгоритмов. В оставшейся части статьи мы посмотрим на кое-какие реализации нескольких алгоритмов поиска подстрок и на их бенчмарки.

Мы будем исследовать три алгорима поиска подстрок. Все они работают за линейное время и требуют предобработки, линейно зависящей от длины needle. Предвычисление одной и той же needle требуется лишь однажды, и затем ее можно переиспользовать в нескольких попытках поиска. Это разумно, поскольку во множестве случаев нам нужно искать одну и ту же строку снова и снова. И даже если мы этого не сделаем — предвычисление не является особо дорого операцией.

Все алгоритмы ниже обходят каждый из символов в haystack единственный раз последовательно (никакого случайного доступа по индексу), поэтому все они нормально работают в потоковом режиме. Эта статья возникла в ходе реальной работы над прокси-сервером для продакшена, работающем на основе фреймворка Netty, и это повлияло на часть решений по дизайну API. Кроме того, поскольку нам нужно было делать поиск по буферам байтов, код будет работать именно с Byte, а не с Char.

Кнут-Моррис-Пратт (КМП-алгоритм)

Это широкоизвестный алгоритм поиска подстрок, датирующийся 70-ми годами прошлого века. Он хорошо описан в литературе, поэтому я не буду расписывать его здесь в деталях. КМП основан на конечных автоматах — в ходе фазы предварительного вычисления, массив индексов связей строится на основе needle. В ходе поиска, автомат принимает на вход символы из haystack один за другим, и обновляет свое внутреннее состояние соответственно (а состояние там — это просто индекс в таблице связей).

Вот здесь есть реализация на Scala.

Двоичный алгоритм поиска подстроки

Изначально мне пришлось самостоятельно придумывать название этого алгоритма: нигде в литературе раньше я не видел ничего подобного. В результате, я пришел к названию «Shifting Bit Mask». Позже оказалось, что этот алгоритм и его вариации известен еще с 1964 года под различными англоязычными названиями вроде «Bitap», «Shift-or», «Shift-and», «Baeza-Yates–Gonnet». Спасибо читателям, которые отыскали его для меня. Эта статья написана задолго до этого известия.

Этот алгоритм основывается на очень простой идее и очень хорошо работает, поскольку там почти нет прыжков, и он основывается на нескольких примитивных бинарных операциях. Из-за этого у него есть ограничение на длину needle, которую мы собираемся искать: она не может быть длинней 64 байтов. Это число взялось просто по количеству битов в Long в JVM. Это ограничение — достаточно щедрое для большого количества реальных задач.

Поскольку я изначально разрабатывал этот алгоритм самостоятельно, постараюсь рассказать о нем детальней. Вначале мы предвычисляем контекст поиска для нужной needle:

  def computeBitMasks(needle: Array[Byte]): Array[Long] = {
    require(needle.length <= 64, "Maximum supported search pattern length is 64.")
    val bitMasks = Array.ofDim[Long](256)
    var bit = 1L
    for (c <- needle) {
      bitMasks(toUnsignedInt(c)) |= bit
      bit <<= 1
    }
    bitMasks
  }

Мы предвычисляем bitMask (64-битный Long) для каждого возможного байтового значения (256 штук bitMask-ов). Для какого-то значения байта X, его bitmask содержит содержит единицы во всех местах, где X находится в needle. Например, вот вам битовая маска для строки «abracadabra»:

Кроме того, нужно предварительно вычислить successBitMask, которая поможет понять, что мы нашли точное совпадение. Она выглядит как значение Long, с битом 1 в позиции needle.length — 1:

  def computeSuccessBitMask(needle: Array[Byte]): Long = {
    1L << (needle.length - 1)
  }

И наконец, нужно сделать, собственно, поиск. Единственное мутабельное состояние, которое мы хотим хранить — это currentMask (Long). Для каждого байта в haystack мы сдвигаем currentMask влево на 1 бит, устанавливаем его младший бит в 1, и делаем побитовый and между результатом и bitMask, предвычисленной для текущего обрабатываемого значения байта из haystack (этот and сбрасывает все биты в тех местах currentMask, которые не совпадают с текущим обрабатываемым байтом).

Таким образом, после обработки каждого байта, «выживут» только те биты, которые находятся на подходящих позициях. И с каждым обработанным байтом, все биты сдвигаются влево на одну позицию. Если бит «выживает» на протяжении количества итераций, равных длине needle — мы нашли совпадение! А проверить мы это сможем с помощью successBitMask:

  def process(value: Byte): Boolean = {
    currentMask = ((currentMask << 1) | 1) & bitMasks(toUnsignedInt(value))
    (currentMask & successBitMask) == 0
  }

На заметку: описанный выше метод возвращает false, если что-то нашлось, и это выглядит контринтуитивно. Это можно понимать так, что значение true означает необходимость продолжать поиск, а false останавливает его — это связано с тем, что, как я писал выше, API делалось совместимым с Netty. Если интересно, как запускать поиск, вот здесь есть пример.

В результате, вся логика сводится всего к нескольким простым инструкциям процессора. К сожалению, остается совершенно бесполезная проверка границ индексов массива bitMasks, которую не может удалить ни один JDK (а я посмотрел ассемблер, сгенерированный несколькими разными JDK).

Вот здесь есть полная реализация на Scala.

Ахо-Корасик

Это еще один популярный алгоритм, известный с 1975 года. Его отличительная (и иногда довольно полезная) черта — возможность искать сразу несколько needle одновременно, при этом все символы из haystack обходятся ровно по одному разу (думаю, это просто великолепно!). Идея, на которой все это работает — расширение КМП-алгоритма, конечный автомат с использованием префиксного дерева (которое строится на основе нескольких needle), содержащее ссылки на связи (сравните с одномерным массивом из КМП). На основе этих ссылок внутреннее состояние автомата преключается между узлами префиксного дерева после каждого обработанного символа, и часть узлов указывает на положительный результат поиска какой-то конкретной needle. Фаза предвычисления здесь довольно сложная, а вот фаза поиска — неожиданно очень простая.

Вот ссылка на работающую реализацию на Scala.

Это был совершенно неполный список алгоритмов поиска подстрок. Еще мы пробовали алгоритм Рабина-Карпа и алгоритм Бойера-Мура. Из этих двух, Бойер-Мур показал сравнимую производительность, но они оба не совместимы со стримингом (используют произвольный доступ к haystack по индексу), и поэтому я выбросил их из этого расследования.

Бенчмарки

Мы будем бенчмаркить три вышеописанных алгоритма, и кроме того, посмотрим на результаты для методов String.indexOf (Java) и indexOfSlice (Scala). Если честно, это не совсем правильное сравнение, потому что String.indexOf работает со строками, а все остальные методы — на массивах байтов. Но непохоже, чтобы это обесценивало результаты такого сравнения. Более того, я включил еще и результаты для Bytes.indexOf из Guava (v.28.1). Этот метод работает на массивах байтов. И его написали в Google — все что там пишут супер быстро работает, да?

Писать бенчмарки всегда непросто, потому что можно подавать на вход совершенно разные данные, изменять множеством разных способов — не только по длине needle и haystack, но и по внутреннему содержимому этих строк (которое может очень сильно повлиять на некоторые алгоритмы). На практике, всегда стоит проверять те входные данные, которые максимально похожи на данные из ваших реальных задач (именно этим мы и занимались в нашем проекте).

Чтобы сократить эту статью, я использвал только 2 вида входных данных. Один из них призван отражать реальный случай: haystack размером примерно 1.5 KB (с человекочитаемым текстом внутри), needle — 9 байт, и в haystack этой последовательности нет (это нужно, чтобы заставить алгоритм выполнить полное сканирование).

Другой вид входных данных нужен, чтобы получить худший случай поведения квадратичного алгоритма. Он куда короче, чем данные из самого начала этой статьи: иначе нам пришлось бы ждать целую минуту, помните? Массив haystack задается в формате "AA...AAB" (та же длина, что и у первого типа данных), а needle — 64-байтовый (специально для того, чтобы с ним справился двоичный алгоритм поиска подстроки) массив того же вида (совпадение находится только в самом конце haystack).

Бенчмарк, написанный на фреймворке JMH можно найти здесь. Если у вас есть другие идеи, что и как здесь стоит измерять — можно клонировать этот репозиторий, что-то поменять и опубликовать комментарии.

По предложению Владимира Ситникова, я добавил результаты бенчмарков для java.util.regex.Pattern, он использует алгоритм Бойера-Мура под капотом.

(Примечание переводчика: кстати, Владимир Ситников — участник нескольких программных комитетов в JUG Ru Group и сам делает интересные доклады. Например, по ссылке доступна видеозапись его доклада с JPoint 2019 под названием «Java тормозит: CodeCache edition»).

Результаты бенчмарков

Результаты даны в миллисекундах, меньше — лучше:

# JMH version: 1.21

# VM version: JDK 13.0.1, OpenJDK 64-Bit Server VM, 13.0.1+9

Benchmark (searchInput) Mode Cnt Score Error Units

javaIndexOf REGULAR avgt 5 0.622 ± 0.002 us/op

shiftingBitMask REGULAR avgt 5 1.982 ± 0.017 us/op

regexPattern REGULAR avgt 5 2.184 ± 0.006 us/op

kmp REGULAR avgt 5 2.635 ± 0.016 us/op

scalaIndexOfSlice REGULAR avgt 5 3.202 ± 0.009 us/op

guavaIndexOf REGULAR avgt 5 3.696 ± 0.095 us/op

ahoCorasic REGULAR avgt 5 7.063 ± 0.040 us/op

shiftingBitMask WORST_CASE avgt 5 1.986 ± 0.010 us/op

kmp WORST_CASE avgt 5 5.120 ± 0.006 us/op

ahoCorasic WORST_CASE avgt 5 6.892 ± 0.025 us/op

scalaIndexOfSlice WORST_CASE avgt 5 8.765 ± 0.007 us/op

regexPattern WORST_CASE avgt 5 11.566 ± 0.086 us/op

javaIndexOf WORST_CASE avgt 5 23.029 ± 0.124 us/op

guavaIndexOf WORST_CASE avgt 5 52.927 ± 0.275 us/op

Здесь все как и ожидалось:

Для обычных данных доминирует javaIndexOf, потому что использует внутри высокоэффективную интринсику, из-за которой константная часть мала;
Для нашего специально сконструированного худшего случая, все меняется: даже на довольно небольшом вводе, сложность наивного алгоритма поиска (O(nm)) убивает производительность javaIndexOf, и даже очень маленькая константная составляющая не может спасти ситуацию — она работает медленней любого линейного алгоритма, и shiftingBitMask (двоичный алгоритм поиска) выигрывает с отрывом.
guavaIndexOf страдает от такой же квадратичной сложности, что и у javaIndexOf; кроме того, даже для среднего случая оно работает в 2 раза медленней, чем двоичный алгоритм shiftingBitMask;
scalaIndexOfSlice делает что-то более медленное, чем knuthMorrisPratt, несмотря на то, что они используют одинаковый алгоритм — обобщенный код медленней, чем специализированный;
производительность — не самая сильная черта ahoCorasic (ну или по крайней мере, этой его реализации; должен признаться, что я не очень старался делать в нем микрооптимизации, поскольку добавил его только из-за его отличительной черты: возможности искать сразу по нескольким строкам, и это похоже на тему для отдельной статьи);
входные данные (и длина needle) не влияли на производительность shiftingBitMask и ahoCorasic.

Выводы

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

На основе предствленных данных, я сделал следующие выводы:

Если вы работаете со String-ами И нет риска, что на вход будут подаваться специально сконструированные данные по худшему сценарию, можно использовать String.indexOf (а java.util.regex.Pattern — более безопасная альтернатива с линейной сложностью);
Иначе, если ваша needle не длиннее 64 байт, используйте двоичный алгоритм поиска;
Если длиннее, то испольуйте Кнута-Морриса-Пратта;
Если у вас Scala и вам не хочется писать собственную реализацию КМП-алгоритма (или вам не нужна максимальная производительность), можно использовать indexOfSlice из стандартной библиотеки — он работает довольно хорошо;
Если нужно искать несколько строк, попробуйте Ахо-Корасика.

Вот и все! Если вам нравится читать об алгоритмах, производительности и тому подобном (а еще, о Scala, JVM и Java вообще) — подписывайтесь на автора этой статьи, Linas Medziunas (Medium, Twitter).

GitHub-репозиторий со всем кодом из этой статьи находится здесь.

Переводы статей публикуются при поддержке JUG Ru Group и конференции JPoint.

Теги:

Хабы: