Блог

Я хочу понять проблемы с производительностью, которые могут возникнуть при выполнении поиска по подстроке в Java. Я знаю два встроенных метода поиска подстроки в Java.

1. String.indexOf()

Насколько я понимаю, этот метод использует алгоритм перебора поиска подстроки, таким образом, его сложность равна O (nm), где n и m — длины строки и шаблона.

2. Используйте шаблон и средство сопоставления

Я ничего не знаю о том, как реализованы алгоритмы регулярных выражений и об их сложности.

Итак, вопросы:

1) Какой из этих методов предпочтительнее с точки зрения производительности?

2) В чем сложность поиска по регулярному выражению? Зависит ли это от самого регулярного выражения?

Честно говоря, если вас волнует производительность в наихудшем случае, используйте JNI в машинном коде, который вызывает strstr функцию вашей стандартной библиотеки. Хорошо реализованный strstr , как и в последних версиях glibc, имеет линейное время выполнения в наихудшем случае и постоянное использование пространства в наихудшем случае. Я полагаю, что glibc strstr также может выполнять длинные переходы по тексту, подобные Boyer-Moore. Стандартные библиотеки C поддерживаются людьми, которые знают, как писать и поддерживать хорошие библиотеки общего назначения, и практикуются в своем ремесле. Этого нельзя сказать о стандартной библиотеке классов Java.

Вам нужно будет превратить строку Java UTF-16 во что-то подходящее для strstr , например, строку UTF-8. Вам также придется корректно обрабатывать встроенные нулевые байты в строке UTF-8. Кроме этого, вы будете пользоваться преимуществами хорошо написанной и поддерживаемой библиотеки.

Java выполняет поиск по регулярным выражениям (для данного конкретного случая) с использованием поиска по строке Бойера-Мура, взломанного в наивной реализации регулярных выражений. Компиляция a Pattern только с вашей строкой приведет к Matcher относительно хорошей производительности. Однако обратите внимание, что это НЕ распространяется ни на что, кроме поиска строк с помощью библиотеки регулярных выражений; вы по-прежнему придерживаетесь наивной реализации регулярных выражений, которая выполняет обратный поиск, если вы вводите в нее нетривиальное регулярное выражение.

В качестве доказательства того, почему вы не должны использовать Java regex для реальных регулярных выражений, я представляю вам следующее:

 public class regex {
  public static void main(String[] args) throws Exception {
    String haystack = "ab";
    String needle = "abab?.*";
    for (int i = 0; i < 7; i  ) haystack = haystack   haystack;
    for (int i = 0; i < 4; i  ) needle = needle   needle;
    System.out.println(haystack.length()   " "   needle.length());
    long before = System.currentTimeMillis();
    System.out.println(Pattern.matches(needle, haystack));
    long after = System.currentTimeMillis(); // long after indeed...
    System.out.println(after - before);
  }
}
  

Это поиск в 256-символьном стоге сена регулярного выражения needle (это честное регулярное выражение, о котором вы узнали в классе compilers) из 112 символов. На моей машине для завершения требуется около 24 секунд.