Статьи

Java Best Practices — строковая производительность и точное совпадение строк

Декабрь 12, 2018
Продолжая серию статей о предлагаемых практиках при работе с языком программирования Java, мы поговорим о настройке производительности String . Мы сосредоточимся на том, как эффективно обрабатывать операции создания строк, изменения строк и сопоставления строк . Кроме того, мы предоставим наши собственные реализации наиболее часто используемых алгоритмов для точного сопоставления строк. Многие из этих алгоритмов могут обеспечить гораздо более высокую производительность по сравнению с наивным подходом для точного сопоставления строк, доступным в Java Development Kit. Эта статья завершается сравнением производительности между вышеупомянутыми алгоритмами точного совпадения строк.

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

Перед прочтением каждого раздела этой статьи настоятельно рекомендуется ознакомиться с соответствующей документацией по Java API для получения подробной информации и примеров кода.

Все тесты выполняются на Sony Vaio со следующими характеристиками:

  • Система: openSUSE 11.1 (x86_64)
  • Процессор (ЦП): Процессор Intel® Core ™ 2 Duo T6670 с частотой 2,20 ГГц
  • Скорость процессора: 1200,00 МГц
  • Общий объем памяти (ОЗУ): 2,8 ГБ
  • Java: OpenJDK 1.6.0_0 64-битная

Применяется следующая тестовая конфигурация:

  • Одновременный рабочий Темы: 1
  • Тест повторений на одного работника Тема: 1000
  • Всего тестовых прогонов: 100

Настройка производительности строки

Многие люди не думают о производительности, когда используют объекты String . Тем не менее неправильное использование классов String может значительно снизить производительность приложения. Наиболее важные вещи, которые вы должны иметь в виду:

  1. Строковые объекты неизменны. Как только мы создаем объект String, мы не можем его изменить. Каждая операция, которая изменяет строку, приводит к созданию по крайней мере одного нового экземпляра объекта. Например, конкатенация двух строк с использованием оператора конкатенации (+) приводит к созданию двух новых объектов: временного объекта StringBuffer, используемого для фактической конкатенации, и нового экземпляра String, указывающего на конкатенированный результат (операция «toString ()» StringBuffer имеет вид используется для создания экземпляра результирующей строки ). С другой стороны, использование операции String «concat (String ..)» для выполнения конкатенации строк обеспечит гораздо лучшие результаты производительности по сравнению с подходом оператора конкатенации (+). За кулисами операция String «concat (String ..)» использует собственную операцию «System.arrayCopy» для подготовки массива символов с содержимым двух объединенных строк. Наконец, создается новый экземпляр String, который указывает на объединенный результат
  2. Строковые ссылки — это указатели на фактические экземпляры объекта String . Таким образом, использование оператора «==» для сравнения двух экземпляров String, представляющих идентичное литеральное содержимое, вернет «false» в случае, если фактические объекты String отличаются. Кроме того, использование операций String «equals (String ..)» или String «equalsIgnoreCase (String ..)» для сравнения двух экземпляров String дает действительные результаты, но выполняет сравнение символов с символами в случае, если две сравниваемые строки представлены различными экземплярами и их буквальное содержание имеет одинаковую длину. Как вы можете себе представить, операции «equals (String ..)» и «equalsIgnoreCase (String ..)» намного дороже по сравнению с оператором «==», который сравнивает строки на уровне экземпляра. Тем не менее, вышеупомянутые операции выполняют проверку равенства экземпляров ( this == obj ) перед всеми проверками литерального содержимого. Чтобы иметь возможность воспользоваться проверкой равенства this == obj при сравнении экземпляров String , вы должны определить значения String как строковые литералы и / или строковые константные выражения. При этом ваши экземпляры String будут автоматически интернированы JVM. Альтернативный, но не излюбленный, подход заключается в использовании операции intern () для String, чтобы интернировать String вручную. Как четко указано в документации Java для метода intern (),

    «Пул строк, изначально пустой, поддерживается частным образом классом String.

    При вызове метода intern, если пул уже содержит строку, равную этому объекту String, как определено методом equals (Object), возвращается строка из пула.

    В противном случае этот объект String добавляется в пул и возвращается ссылка на этот объект String.

    Отсюда следует, что для любых двух строк s и t s.intern () == t.intern () имеет значение true, если и только если s.equals (t) имеет значение true.

    Все буквенные строки и строковые константные выражения интернированы ».

Мы предлагаем следующие рекомендации по работе с классами String :

  1. Избегайте создания литеральных строк и строковых константных выражений, а не создавайте новые объекты String, используя один из методов конструктора String
  2. Использование символьных массивов для выполнения операций преобразования строк дает лучшие результаты производительности, но является менее гибким подходом
  3. При выполнении операций преобразования строк, таких как удаление, вставка, замена или добавление символов, объединение или разбиение строк, используется либо класс StringBuilder, либо класс StringBuffer . Класс StringBuilder представлен в Java 1.5 и является несинхронизированным аналогом класса StringBuffer . Таким образом, если только один поток будет выполнять операции преобразования String, тогда предпочтение отдается классу StringBuilder, потому что это лучший исполнитель

Pattern First Точное соответствие строк

В языке Java отсутствуют быстрые алгоритмы поиска строк. Строковые операции «indexOf (…)» и «lastIndexOf (…)» выполняют наивный поиск предоставленного шаблона по исходному тексту. Наивный поиск основан на алгоритме точного сопоставления строк с шаблоном «грубой силы». Алгоритм «грубой силы» заключается в проверке во всех позициях в тексте, начинается ли вхождение шаблона там или нет. Затем, после каждой попытки, он смещает шаблон ровно на одну позицию вправо. Тем не менее существует несколько других алгоритмов, которые значительно превосходят алгоритм «грубой силы» как по скорости, так и по эффективности.

Приложения требуют двух видов решения, в зависимости от того, какая строка, шаблон или текст указываются первыми. В нашем случае шаблон предоставляется заранее, что означает, что мы всегда ищем предоставленный шаблон по неизвестному тексту. Для всех приложений, которым требуется полнотекстовый поиск (Text First Exact String Matching), необходим другой набор алгоритмов, обеспечивающих индексированное сканирование. Apache Lucene — одна из самых популярных библиотек текстового поиска, реализующая последнее семейство алгоритмов. Тем не менее, эта статья будет исследовать только алгоритмы первого рода.

Благодаря большой работе, книге под названием « Алгоритмы точного сопоставления строк » Кристиана Чарраса и Тьерри Лекрока из Лаборатории информатики в Руане — Университете Руана , мы смогли реализовать в Java наиболее часто используемые алгоритмы для точного сопоставления строк. где образец дается первым. В приведенном ниже списке отображается имя алгоритма, указанное в книге Кристиана Чарраса и Тьерри Лекрока, а затем в скобках указана реализация алгоритма «кодовое имя». Для получения дополнительной информации о каждом алгоритме, пожалуйста, нажмите на соответствующую ссылку, чтобы перейти в соответствующий раздел книги «Алгоритмы точного сопоставления строк».

В первоначальной версии (1.0.0) пакета Exact String Search Algorithm для каждого алгоритма мы реализовали три служебные операции:

  • compile (String pattern) — Статическая операция, которая выполняет всю необходимую предварительную обработку на основе предоставленного шаблона.
  • findAll (String source) — возвращает список, содержащий все индексы, где алгоритм поиска продиктовал правильное сопоставление с образцом.
  • findAll (String pattern, String source) — это вспомогательная статическая операция, которая включает в себя функциональность обеих вышеупомянутых операций.

Ниже приведен пример использования алгоритма Бойера-Мура (БМ):

Дело 1

1
2
3
4
BM bm = BM.compile(pattern);
List<Integer> idx = bm.findAll(source);
List<Integer> idx2 = bm.findAll(source2);
List<Integer> idx3 = bm.findAll(source3);

Дело № 2

1
List<Integer> idx = BM.findAll(pattern, source);

В первом случае мы компилируем шаблон и выполняем поиск в два отдельных этапа. Этот подход подходит, когда мы должны искать несколько исходных текстов по одному и тому же шаблону. Скомпилировав шаблон один раз, мы можем максимизировать результаты производительности из-за того, что предварительная обработка обычно является тяжелой операцией. С другой стороны, для одного поиска второй подход предоставляет более удобный API.

Мы должны точно определить, что наша предоставленная реализация является поточно-ориентированной и что в настоящее время мы не поддерживаем регулярные выражения в шаблонах.

Ниже приведен пример сравнения производительности между реализациями алгоритмов нашего набора алгоритмов поиска точных строк. Мы искали текст в 1150000 символов для фразы из 37 символов, которая намеренно не существовала, используя полный размер алфавита 65535 символов. Пожалуйста, не забывайте, что это сравнительное сравнение производительности. Результаты производительности для подавляющего большинства предоставленных алгоритмов поиска сильно зависят от предоставленного текста, предоставленного шаблона и размера алфавита. Таким образом, вы должны рассматривать каждое сравнение производительности между строковыми алгоритмами поиска только как относительное.

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

Метод № 1 — Подход indexOf ()

01
02
03
04
05
06
07
08
09
10
11
12
13
14
public static List<Integer> findAll(String pattern, String source) {
  List<Integer> idx = new ArrayList&ltInteger>();
  int id = -1;
  int shift = pattern.length();
  int scnIdx = -shift;
  while (scnIdx != -1 || id == -1) {
   idx.add(scnIdx);
   id = scnIdx + shift;
   scnIdx = source.indexOf(pattern, id);
  }
  idx.remove(0);
  return idx;
 }

Метод № 2 — подход Matcher find ()

1
2
3
4
5
6
7
8
9
public static List<Integer> findAll(String pattern, String source) {
  List<Integer> idx = new ArrayList&ltInteger>();
  Pattern ptrn = Pattern.compile(pattern);
  Matcher mtch = ptrn.matcher(source);
  while(mtch.find())
   idx.add(mtch.start());
  
  return idx;
 }

Ниже мы представляем таблицу сравнения производительности между вышеупомянутыми алгоритмами поиска

Горизонтальная ось представляет среднее время в миллисекундах для каждого алгоритма, необходимого для предварительной обработки и анализа предоставленного текста. Таким образом, чем ниже значения, тем лучше. Как вы можете видеть, наивная реализация Java (подход indexOf ()) превосходит подход «find ()» Java Matcher наряду с почти всеми нашими реализациями алгоритма поиска. Другими словами, когда вы имеете дело с поиском строк малого и среднего размера, предпочтительно реализовать что-то вроде фрагмента кода, который мы предоставили выше, а не использовать более сложный алгоритм поиска строк. С другой стороны, при работе с большими и очень большими документами один из самых быстрых алгоритмов из нашего пакета наверняка пригодится!

Вы можете скачать версию 1.0.0 нашего комплекта Exact String Search Algorithm здесь

Удачного кодирования

Джастин

Статьи по Теме :
Связанные фрагменты:
38
Share: