Як по-різному оптимізувати алгоритми в Java, або Історія одного завдання. Частина I
Всім привіт. Я Сергій Моренець, розробник, викладач, спікер та технічний письменник, хочу поділитися з вами своїм досвідом роботи з такої цікавої теми як структури даних, алгоритми та їхня оптимізація. Впевнений, що ніхто не розповість про алгоритми краще, ніж Дональд Кнут у його фундаментальній роботі «Мистецтво програмування». Мета цієї статті в іншому — на конкретному прикладі показати досвід використання та застосування різних алгоритмів та структур даних у Java.
Стаття ця не випадкова, а вся історія почалася на одній технічній співбесіді, де мене попросили на стадії Live coding вирішити, здавалося б, просте завдання з трансформації рядка. Причому наголос у реалізації треба було зробити не так на правильність, а саме на ефективність. Більше того, до цього завдання йшли спеціальні тести, який перевіряли продуктивність рішення. Завдання я вирішив і у відведений час вписався, але на цьому історія не закінчилася. Я вважаю, що чим вищий рівень (кваліфікація) спеціаліста, тим більше різних правильних рішень (підходів) він може дати на те саме питання. Обдумування цього завдання привело мене до висновку, що воно не настільки тривіальне, як мені спочатку здалося.
Думаю, що ви знаєте, що будь-який проєкт можна оцінити за допомогою трьох показників (Час, Якість, Фінанси). Ви можете вибрати будь-які два показники, пожертвувавши третім. Аналогічно з технічним рішеннями. Для деяких важлива компактність або читабельність. Для інших — витрата ресурсів та продуктивність.
Мені здалося цікавим знайти всі інші рішення, перевірити їх на продуктивність за допомогою benchmarks, а також пояснити, яке ж рішення в яких випадках варто використовувати. А згодом ми обговорили ці рішення на наших курсах. Я сподіваюся, що стаття буде цікава всім розробникам, оскільки схожі завдання часто зустрічаються на live coding або технічних завданнях. І ви зможете застосувати розглянуті принципи та алгоритми, стратегії оптимізації як на співбесідах, так і в роботі.
Завдання
Отже, необхідно реалізувати інтерфейс StringReplacement:
@FunctionalInterface
public interface StringReplacement {String replace(String text);
}
де метод replace() повинен перетворювати рядок за такими правилами:
- Рядок може бути будь-якого розміру і містити лише символи A, B, C або D.
- Якщо передається порожній рядок (або null), то його потрібно повернути.
- Метод повинен шукати всі комбінації символів AB, BA, CD, DC та замінювати їх на порожній рядок доти, доки таких комбінацій більше не буде.
Декілька прикладів:
- ABC -> C
- AACC -> AACC
- BCDAD -> D
Таким чином, основна складність цього завдання в тому, що ми заздалегідь не знаємо, скільки циклів заміни буде, тому що після кожної заміни можуть з’являтися нові комбінації, які потрібно знову видаляти.
Рішення 1. Просте
Я назвав це рішення простим (або очевидним), оскільки воно одразу випливає з умов завдання. Ми щоразу замінюватимемо у вхідному рядку вихідні комбінації на порожній рядок і зупинимося лише тоді, коли більше не залишиться шуканих комбінацій. Оскільки ці комбінації статичні, то їх простіше зберігати в списку RULES:
private final static List<String> RULES = List.of("AB", "BA", "CD", "DC");У результаті отримаємо:
public class SimpleStringReplacement implements StringReplacement { private final static List<String> RULES = List.of("AB", "BA", "CD", "DC"); public String replace(final String text) { if (text == null || text.isBlank()) {return text;
}
String current = text;
while (containsRules(current)) { for (String rule : RULES) {current = current.replaceAll(rule, "");
}
}
return current;
}
private boolean containsRules(final String text) {return RULES.stream().anyMatch(rule -> text.contains(rule));
}
}
Ми виділили containsRules в окремий метод, оскільки Java не дозволяє використовувати в лямбда-виразах non-final змінні. Отже, це проста, зрозуміла реалізація, до якої є претензії щодо ефективності:
- Ми для кожної комбінації змушені проходити знову весь рядок (що більше комбінацій, тим повільніше працює це рішення).
- containsRules додає ще більше ітерацій проходу рядка.
- При кожній ітерації ми створюємо новий рядок, навіть якщо було замінено лише одну комбінацію (два символи).
Таким чином, цей код виграє у простоті, але програє в швидкості та об’ємі використовуваних ресурсів. Але не можна таке рішення назвати невдалим чи нездатним. Якщо у вас невеличка кількість рядків, а самі рядки невеликого розміру
Рішення 2. Просте з елементами паралелізму
Перший варіант можна спробувати прискорити, якщо згадати, що в Streams API є можливість простого розпаралелювання операцій. Є різні думки на те, як це впливає на ефективність (найчастіше зустрічається думка, що погано), але у нас є чудовий шанс це перевірити, замінивши метод containsRules на:
private boolean containsRules(final String text) {return RULES.parallelStream().anyMatch(rule -> text.contains(rule));
}
Таким чином, перевірка рядка на наявність комбінацій буде здійснюватися в декількох потоках відразу. Як відомо, у цьому випадку Java використовує ForkJoinPool.commonPool().
Весь код виглядає так:
public class SimpleParallelStringReplacement implements StringReplacement { private final static List<String> RULES = List.of("AB", "BA", "CD", "DC"); public String replace(final String text) { if (text == null || text.isBlank()) {return text;
}
String current = text;
while (containsRules(current)) { for (String rule : RULES) {current = current.replaceAll(rule, "");
}
}
return current;
}
private boolean containsRules(final String text) {return RULES.parallelStream().anyMatch(rule -> text.contains(rule));
}
}
Рішення 3. Регулярні вирази
Перші два варіанти страждають тим, що перевірка кожної комбінації призводить до нової ітерації з пошуку та заміни цього підрядка. Крім того, ми використовуємо метод replaceAll для заміни рядків:
current = current.replaceAll(rule, "");
Цей метод, як випливає з sources, внутрішньо використовує клас Pattern:
public String replaceAll(String regex, String replacement) {return Pattern.compile(regex).matcher(this).replaceAll(replacement);
}
Але в нашому завданні список шаблонів із заміни рядка статичний і нам немає сенсу щоразу створювати об’єкт Pattern при новій ітерації. Тому чому б не використовувати один регулярний вираз для всіх комбінацій?
(AB|BA|CD|DC)
Його дуже легко отримати з нашого списку RULES:
private final static List<String> RULES = List.of("AB", "BA", "CD", "DC"); private final static Pattern PATTERN = Pattern.compile(RULES.stream().collect(Collectors.joining("|", "(", ")")));І тоді нова реалізація виглядатиме так:
public class RegexStringReplacement implements StringReplacement { private final static List<String> RULES = List.of("AB", "BA", "CD", "DC"); private final static Pattern PATTERN = Pattern.compile(RULES.stream().collect(Collectors.joining("|", "(", ")"))); public String replace(String text) { if (text == null || text.isBlank()) {return text;
}
String current = text;
Matcher matcher = PATTERN.matcher(current);
while (matcher.find()) { current = matcher.replaceAll("");matcher = PATTERN.matcher(current);
}
return current;
}
}
По суті, це компактна реалізація, яка зручна тим, що ми пошук і заміну підрядка віддаємо на відкуп регулярним виразам. Чи буде цей варіант швидшим? Тут у кожному циклі всього один прохід по рядку, але тільки benchmarks покажуть, наскільки Java швидко працює з такими регулярними виразами.
Рішення 4. StringBuilder
Всі попередні варіанти грішили тим, що вони використовували об’єкт String, який, як відомо, є immutable (незмінним), а це означає, що на кожному кроці ми створюємо новий об’єкт String. Immutability — це чудово, але не тоді, коли нам потрібно вичавити максимум продуктивності. Тому закономірним поліпшенням наших рішень став би перехід до mutable структур даних, які зберігали б проміжний результат операції. Почнемо з класу StringBuilder. Чому не StringBuffer? Як відомо, StringBuffer є thread-safe типом, а для локального об’єкта потокобезпечнiсть не потрібна і лише додає зайвий overhead через блокування.
Думаючи про ефективність, не варто забувати про те, щоб наше рішення було гнучким і розширеним. По суті, наше рішення складається з трьох окремих компонентів:
- Структура даних зберігання проміжного результату (набору символів).
- Прохід по рядку та визначення того, чи є поточні символи замінними (тобто відповідають одній з комбінацій).
- Додавання та видалення символів з проміжного сховища.
По суті, ми можемо розробляти і оптимізувати кожен з компонентів окремо, не боячись, що це зашкодить решті частин. Тому додамо новий інтерфейс Rule, який буде своєрідною абстракцією і який перевірятиме, чи відповідають поточні символи однієї з комбінацій:
@FunctionalInterface
public interface Rule {boolean match(char first, char second);
}
Це дозволить легко додавати нові правила в наш код у разі потреби. І додамо два класи-реалізації цього інтерфейсу:
static class ABIndexRule extends BaseIndexRule implements Rule { ABIndexRule() { super("AB");}
}
static class CDIndexRule extends BaseIndexRule implements Rule { CDIndexRule() { super("CD");}
}
@RequiredArgsConstructor
static abstract class BaseIndexRule {private final String text;
public boolean match(char first, char second) { if (first == second) {return false;
}
return text.indexOf(first) >= 0 && text.indexOf(second) >= 0;
}
}
У методі match ми просто шукаємо, чи є обидва символи в рядку (AB або СD), при цьому нас не цікавить порядок символів (A і B) або (B і A). Сама реалізація буде досить простою:
public class BuilderStringReplacement implements StringReplacement {private final static int TOKEN_LENGTH = 2;
private final static List<Rule> RULES = List.of(new ABIndexRule(), new CDIndexRule());
public String replace(String text) { if (text == null || text.isBlank()) {return text;
}
StringBuilder builder = new StringBuilder();
for (int i = 0; i < text.length(); i++) {builder.append(text.charAt(i));
for (Rule rule : RULES) { if (builder.length() >= TOKEN_LENGTH) { if (rule.match(builder.charAt(builder.length() - 2), builder.charAt(builder.length() - 1))) {builder.delete(builder.length() - TOKEN_LENGTH, builder.length());
break;
}
}
}
}
return builder.toString();
}
Ми додаємо кожен символ з вхідного рядка в StringBuilder, а потім перевіряємо, чи відповідають поточний/попередній символ якомусь правилу. І якщо так, то видаляємо обидва з StringBuilder.
Реалізація досить проста, але має недоліки. Видалення символів з StringBuilder в даному випадку не є особливо витратною операцією, тому що ми видаляємо останні символи (не потрібно зміщувати елементи внутрішнього масиву). Але нам доводиться додавати кожен символ із вхідного рядка, навіть якщо ми його потім видалимо. Тому подальша оптимізація полягає в мінімізації таких операцій.
Рішення 5. Стек
Умови завдання наштовхують на думку, що для тимчасового сховища варто спробувати таку структуру даних, як стек. І справді, ми постійно працюємо з двома головними символами в нашому проміжному сховищі, видаляючи або додаючи їх. На жаль, у Java стек є класом, а не інтерфейсом, тому неможливості вибирати різні реалізації стека, а тільки сам клас Stack, який, до речі, з’явився не в Java 1.2, як багато інших колекцій, а у версії 1.0:
* @author Jonathan Payne
* @since 1.0
*/
public class Stack<E> extends Vector<E> {Чи ми отримаємо виграш у продуктивності, якщо просто замінимо StringBuilder на Stack? Це дуже цікаве питання, тому що залежить від версії Java, яку ви використовуєте:
- У Java 8 і раніше виграшу не буде, тому що в обох випадках ми зберігатимемо символи в масиві char
- Але у Java 9 була додана фітча «Compact Strings», коли і String, і StringBuilder зберігає байтовий масив і використовує 1 байт на символ для Latin-1 символів (у нас саме такі). Таким чином, StringBuilder буде використовувати в 2 рази менше пам’яті, але працювати трохи повільніше через різні перевірки кодувань. Чому ми для стека не використовуємо байтовий масив? Ми це питання обговоримо у другій частині статті
Крім того, використовуючи стек, ми виграємо в читабельності, так як API стека більш зручний для поточних операцій. Для стека ми покращимо наш алгоритм таким чином, що ми не будемо додавати поточний символ відразу в стек, а тільки в тому випадку, якщо останні (поточні) два символи не збігаються з жодною комбінацією:
Код виглядає так:
public class StackStringReplacement extends BaseStringReplacement implements StringReplacement{ public String replace(String text) { if(text == null || text.isBlank()) {return text;
}
Stack<Character> stack = new Stack<>();
char prevCh = 0;
for (int i = 0; i < text.length(); i++) {char ch = text.charAt(i);
for (Rule rule : rules) { if (rule.match(ch, prevCh)) {ch = 0;
stack.pop();
prevCh = stack.isEmpty() ? 0 : stack.peek();
break;
}
}
if (ch != 0) {stack.push(ch);
prevCh = ch;
}
}
if (stack.isEmpty()) {return "";
} else {char[] arr = new char[stack.size()];
for (int i = 0; i < stack.size(); i++) {arr[i] = stack.get(i);
}
return new String(arr);
}
}
Таким чином, у разі збігу комбінації ми видаляємо лише один елемент нашого сховища (stack.pop()). А це означає, що ми виграємо не тільки швидкості, а й в обсягу споживаної пам’яті. Крім того, можна поліпшити ту частину, яка перевіряє символи на збіг. Зараз ми шукаємо наявність кожного символу в рядку:
public boolean match(char first, char second) { if (first == second) {return false;
}
return text.indexOf(first) >= 0 && text.indexOf(second) >= 0;
}
Це не те, щоб повільна операція, але вона включає різні перевірки в самому класі String. І прискорити її можна дуже просто. Для нас AB і BA — по суті одна й та сама комбінація. А це призводить до думки, що ми можемо перевіряти не входження символів, а суму їх ASCII-кодів:
@RequiredArgsConstructor
public abstract class BaseRule {private final int sum;
public boolean match(char first, char second) {return first + second == sum;
}
}
public class ABRule extends BaseRule implements Rule { ABRule() { super('A' + 'B');}
}
Адже сума перестановки не змінюється. А арифметичне порівняння виконується набагато швидше, ніж пошук символів у рядку.
Нові правила зручно виділити в окремий базовий клас:
@RequiredArgsConstructor
public abstract class BaseStringReplacement {protected final List<Rule> rules;
public BaseStringReplacement() {this(List.of(new ABRule(), new CDRule()));
}
}
Якщо повернутися до стека, то його вибір є очевидним, як сховище, але тут є один нюанс. Справа в тому, що Stack — спадкоємець класу Vector, який є thread-safe, тому, як і StringBuffer, не рекомендується для локального використання. Тому в якості наступного варіанту можна розглянути thread-unsafe стек.
Рішення 6. ArrayList
У Java є лише одна реалізація Stack. Але нам ніхто не заважає замінити Stack на ArrayList, в якому немає блокування типу synchronized. Правда, наш код стане не таким читабельним, тому що в ArrayList відсутні операції pop() або peek(), зате більш ефективним:
public class ArrayListStringReplacement extends BaseStringReplacement implements StringReplacement { public String replace(String text) { if (text == null || text.isBlank()) {return text;
}
List<Character> stack = new ArrayList<>();
char prevCh = 0;
for (int i = 0; i < text.length(); i++) {char ch = text.charAt(i);
for (Rule rule : rules) { if (rule.match(ch, prevCh)) {ch = 0;
stack.remove(stack.size() - 1);
prevCh = stack.isEmpty() ? 0 : stack.get(stack.size() - 1);
break;
}
}
if (ch != 0) {stack.add(ch);
prevCh = ch;
}
}
if (stack.isEmpty()) {return "";
} else {char[] arr = new char[stack.size()];
for (int i = 0; i < stack.size(); i++) {arr[i] = stack.get(i);
}
return new String(arr);
}
}
Висновки
У першій частині ми розглянули шість найпростіших і зрозумілих рішень нашого завдання. Ми використовували як різні структури даних (Stack, StringBuilder, ArrayList), так і різні алгоритми перевірки збігу символів. Вивчаючи ці рішення, можна переконатися в тому, що у кожного є свої плюси/мінуси та сфери застосування. У другій частині ми розглянемо п’ять складніших і технічно цікавих алгоритмів. А також протестуємо всі рішення на продуктивність за допомогою benchmarks.
Alina Razumowa
Mykola Makhin
Sergii Voloshyn
Mykola Makhin
Олексій Пєніє
Ілля Бовтрюк
Oleg Kotok
Ілля Бовтрюк
Алексей Алексей
Алексей Алексей
Leo Chashnikov
Олексій Пєніє
Форрест Гамп
Kyrylo Hrechykhin
Yaroslav Kovbas
Форрест Гамп
Tymchyshyn Vitalii
Serhii Harnyk
Ivan Onyshchenko
86 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів