Оптимізація алгоритмів Java, або Історія одного завдання. Частина II

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Всім привіт. Я Сергій Моренець, розробник, викладач, спікер та технічний письменник, хочу поділитися з вами своїм досвідом роботи з такої цікавої теми, як структури даних, алгоритми та їх оптимізація. У першій частині цієї великої статті я описав технічне завдання та 6 найпростіших шляхів її вирішення.

Якщо вам судилося вирішити таке завдання на співбесіді, то у вас буде не так багато часу на аналіз якихось хитромудрих рішень. І швидше за все ви оберете ті варіанти, які були розглянуті у першій частині:

  • Проста заміна рядків.
  • Регулярні вирази.
  • StringBuilder.
  • Stack/ArrayList.

Але якщо це завдання попалося на реальному проекті і потрібно досягти максимальної ефективності, то тут потрібно застосовувати складніші алгоритми, які ми зараз і розглянемо.

Рішення 7. LinkedList

LinkedList чи ArrayList? Таке питання, напевно, прозвучало мільйон разів на технічних співбесідах чи обговореннях технічних рішень проєктів. Думаю, що LinkedList не дуже добре використовувати там, де використовуються операції типу одержання/ видалення елемента за індексом. Але й інші операції використовуються вкрай рідко.

Справа в тому, що якщо ArrayList зберігає операції в масиві, то LinkedList (двозв’язковий перелік) — в об’єктах Node. А створення великої кількості об’єктів — повільніша операція, ніж створення масиву з тією ж кількістю елементів. Я вже мовчу про обсяг пам’яті, що використовується. Зрозуміло, все залежить від кількості елементів у списку.

Наше завдання — вдалий випадок, щоб в одному з варіантів використовувати LinkedList разом з ArrayList та порівняти швидкодію у benchmarks. Адже наші операції — додавання елементів в кінець або видалення останнього елемента досить швидко працюють в LinkedList. Справа в тому, що LinkedList (він з’явився в Java 1.2) реалізує інтерфейс (Deque) — подвійна черга. І його API надає зручні операції для наших потреб, наприклад getLast, removeLast або addLast:

public class LinkedListStringReplacement extends BaseStringReplacement implements StringReplacement {
       public String replace(String text) {
              if (text == null || text.isBlank()) {
                     return text;
              }
 
              Deque<Character> deque = new LinkedList<>();
 
              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;
                                  deque.removeLast();
                                  prevCh = deque.isEmpty() ? 0 : deque.getLast();
                                  break;
                           }
                     }
 
                     if (ch != 0) {
                           deque.addLast(ch);
                           prevCh = ch;
                     }
              }
 
              if (deque.isEmpty()) {
                     return "";
              } else {
                     char[] arr = new char[deque.size()];
                     Iterator<Character> iterator = deque.iterator();
                     int i = 0;
                     while (iterator.hasNext()) {
                           arr[i++] = iterator.next();
                     }
                     return new String(arr);
              }
 
       }
}

Рішення 8. Буфер-приймач

З шести попередніх рішень найефективнішим було використання ArrayList, де один поточний символ з вхідного рядка ми зберігали в окремій змінній:

Як говорилося в попередній частині, найбільші витрати часу — це видалення символів, які потрапили в ArrayList. І найбільш перспективним напрямом щодо поліпшення ефективності, здається, є варіант зберігати не один поточний символ, а два (або три), наприклад:

З іншого боку, це ускладнить сам алгоритм, оскільки потрібно буде приділити більше уваги синхронізації цих символів і ArrayList. Але й відмовлятися від цієї ідеї не варто, лише трохи модифікувати її. А якщо зберігати поточні символи в окремому буфері-приймачі фіксованої довжини (наприклад, 4 символи), тоді алгоритм буде наступним:

  1. Ми додаємо символи з вхідного рядка до буфера, доки він не заповниться.
  2. У разі появи пошукових комбінацій ми видаляємо символи з буфера, не зачіпаючи основний ArrayList. «Видалення символів» полягає просто в зміщенні вказівника ліворуч на 2 елементи.
  3. Якщо буфер переповнюється, то першу його половину копіюємо в ArrayList, а другу половину зрушуємо на місце першої.

На чому базується впевненість у перевазі цього варіанта?

  1. Буфер буде масивом, причому з char, а не Character елементів, що позбавить нас від box-ing/ unboxing.
  2. Масив буде фіксованої довжини, без операцій вставки/ видалення елементів.
  3. Символи, які потрапляють до ArrayList, залишаються там назавжди, тобто цей список тільки зростатиме і ніколи не скорочуватиметься.

У той самий час цей алгоритм дуже чутливий до розміру буфера. Якщо ми використовуємо буфер з 4 елементів, то шматок рядка CCCDDD цей алгоритм розпізнає і «стисне». А ось CCCCDDDD — ні, і перші 2 символи (CC) потраплять в ArrayList і залишаться там назавжди.

Тому тут важливо зрозуміти природу символів з вхідного рядка. Якщо це практично випадкові символи, наявність послідовності CCCCDDDD можна виключити. Якщо ж ні, потрібно просто збільшити розмір буфера. Наскільки? Для цього можна проаналізувати вхідні рядки і визначити це число дослідним шляхом. Сам код виглядатиме таким чином:

public class BufferStringReplacement extends BaseStringReplacement implements StringReplacement {
 
       private static final int BUFFER_SIZE = 4;
 
       public String replace(String text) {
              if (text == null || text.isBlank()) {
                     return text;
              }
 
              List<Character> stack = new ArrayList<>();
 
              char[] buffer = new char[BUFFER_SIZE];
 
              int count = 0;
 
              for (int i = 0; i < text.length(); i++) {
 
                     if (count == BUFFER_SIZE) {
                           stack.add(buffer[0]);
                           stack.add(buffer[1]);
                            buffer[0] = buffer[BUFFER_SIZE - 2];
                           buffer[1] = buffer[BUFFER_SIZE - 1];
                           count -= 2;
                     }
                     buffer[count++] = text.charAt(i);
 
                     if (count > 1) {
                           for (Rule rule : rules) {
                                  if (rule.match(buffer[count-2], buffer[count-1])) {
                                         count -= 2;
                                         break;
                                  }
                           }
                     }
              }
              if (count > 0) {
                     for (int j = 0; j < count; j++) {
                           stack.add(buffer[j]);
                     }
              }
 
              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);
              }
}
}

Рішення 9. Буфер та оптимізований однозв’язковий список

У минулому прикладі ми використовували ArrayList для зберігання основного рядка, який, по суті, схожий на незмінний список. У нього можна додавати елементи, які потім не змінюються і не видаляються. А це дає нам певну свободу маневрів. Замість того, щоб протестувати LinkedList (замість ArrayList), можна спробувати більш просунутий варіант.

Справа в тому, що LinkedList — це класичний двозв’язковий список. Але в нашому варіанті двозв’язність не потрібна, тому що ми не видалятимемо елементи. А це означає, що можна спробувати однозв’язковий. Але де його взяти? Можна пошукати готовий у Java-бібліотеках, а можна вигадати свій.

Навіщо винаходити велосипед? Справа в тому, що можна виграти ще в одному компоненті.

Одна з особливостей generic types у Java — їх не можна параметризувати примітивними типами. На цю тему є запит на покращення, але він тягнеться з 2014 року, і не видно, щоб хтось дуже турбувався про його впровадження. Якщо подивитися на те, як зберігається вузол у LinkedList:

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

То можна помітити, що item буде не char, а Character у цьому об’єкті. Таким чином, якщо замінити Character на char, можна теоретично заощадити 6 байт. Крім того, тут можна видалити поле prev, оскільки воно вже не потрібне. Більше заощадити не вийде, оскільки Java кешує перші 127 символів (а ASCII-коди A-D менше 127) і, відповідно, об’єкти Character не створюються щоразу, а беруться з кешу:

    @IntrinsicCandidate
    public static Character valueOf(char c) {
        if (c <= 127) { // must cache
            return CharacterCache.cache[(int)c];
        }
        return new Character(c);
  }

Якщо уважно вивчити те, як ми копіюємо символи з буфера до основного списку, то можна звернути увагу, що ми завжди копіюємо по два символи:

                      if (count == BUFFER_SIZE) {
                           stack.add(buffer[0]);
                           stack.add(buffer[1]);

Єдиний виняток — якщо кількість символів непарна, і ми скопіюємо останній символ. Тому можна ще додатково покращити наш алгоритм, зберігаючи в одному вузлі відразу два символи. Якщо другий символ буде відсутній, то просто помістимо нуль.

Таким чином, використовуючи оптимізований однозв’язковий список, ми розраховуємо на 4 покращення:

  1. char замість Character.
  2. Однозв’язковий список замість двозв’язкового (не потрібно зберігати посилання на попередній елемент).
  3. Відразу два символи в одному вузлі (тобто кількість вузлів у 2 рази менша).
  4. Немає необхідності в різних перевірках, які використовуються в LinkedList (та й у будь-якій колекції).

У результаті наш вузол буде виглядати так:

       class Node {
              private final char first;
 
              private final char second;
 
              private Node next;
 
              public Node(char first, char second) {
                     this.first = first;
                     this.second = second;
              }
       }

Таким буде наш список:

              class CustomList {
 
              private Node head;
 
              private Node last;
 
              private int size;
 
              public boolean isEmpty() {
                     return head == null;
              }
 
              public void push(char first) {
                     push(first, (char) 0);
              }
 
              public void push(char first, char second) {
                     Node node = new Node(first, second);
                     if (head == null) {
                           head = node;
                           last = node;
                     } else {
                           last.next = node;
                           last = node;
                     }
                     if (second == 0) {
                           size++;
                     } else {
                           size += 2;
                     }
              }
 
              @Override
              public String toString() {
                     char[] arr = new char[size];
 
                     int i = 0;
                     Node current = head;
                     while (current != null) {
                           arr[i++] = current.first;
                           if (i < size) {
                                  arr[i++] = current.second;
                           }
                           current = current.next;
                     }
                     return new String(arr);
              }
        }

І сам клас-замінник рядків:

public class BufferListStringReplacement extends BaseStringReplacement implements StringReplacement {
 
       private static final int BUFFER_SIZE = 4;
 
       public String replace(String text) {
              if (text == null || text.isBlank()) {
                     return text;
              }
 
              CustomList stack = new CustomList();
 
              char[] buffer = new char[BUFFER_SIZE];
 
              int count = 0;
 
              for (int i = 0; i < text.length(); i++) {
 
                     if (count == BUFFER_SIZE) {
                           stack.push(buffer[0], buffer[1]);
                           buffer[0] = buffer[BUFFER_SIZE - 2];
                           buffer[1] = buffer[BUFFER_SIZE - 1];
                           count -= 2;
                     }
                     buffer[count++] = text.charAt(i);
 
                     if (count > 1) {
                           for (Rule rule : rules) {
                                  if (rule.match(buffer[count - 2], buffer[count - 1])) {
                                         count -= 2;
                                         break;
                                  }
                           }
                     }
              }
              if (count > 0) {
                     for (int j = 0; j < count; j += 2) {
                           if (j < count - 1) {
                                  stack.push(buffer[j], buffer[j + 1]);
                           } else {
                                  stack.push(buffer[j]);
                           }
                     }
              }
 
              if (stack.isEmpty()) {
                     return "";
              } else {
                     return stack.toString();
              }
   }

Рішення 10. Бітове зберігання

У минулому варіанті ми почали оптимізацію основного сховища, зберігаючи в одному елементі одразу два символи. Насправді можна з самого початку застосувати ще одну просту оптимізацію — замість char використовувати byte, так як ASCII-коди A-D вміщуються в діапазон 1 байт. Але це не було б рішенням загального вигляду, оскільки не годилося будь-якої комбінації символів. Натомість можна застосувати більш ефективну оптимізацію для будь-якого випадку.

У нас 4 символи. Навіщо нам зберігати їх код, якщо їх можна закодувати наступним чином:

  1. A — 0
  2. B — 1
  3. C — 2
  4. D — 3

І тоді можна в одному байті зберігати інформацію відразу про чотири символи (!). У такому варіанті ми отримуємо максимальне стиснення даних для тимчасового зберігання, причому цей метод підходить для будь-яких 4 символів.

Але яку структуру даних використати у цьому випадку? Стандартне рішення (BitSet) нам не дуже підходить з двох причин:

  1. Він розглядає 0 як відсутність інформації. І практично неможливо відрізнити символ A(00b) від просто незайнятого місця/
  2. Він більше призначений для операцій з окремими бітами. І неможливо однією операцією встановити один біт у «0», а інший у «1»/

Тому створимо власне сховище, знову ж таки? оптимізоване для нашого випадку:

       private class BitStorage {
 
              private byte[] data;
 
              private int length;
 
              public BitStorage() {
                     data = new byte[16];
              }
 
              public void push(char ch) {
                     int offset = length % 4;
                     int index = length / 4;
                     if (index >= data.length) {
                           byte[] newData = new byte[data.length * 2];
                           System.arraycopy(data, 0, newData, 0, data.length);
                           data = newData;
                     }
                     int value = ch - 'A';
                     data[index] |= (value << offset * 2);
 
                     length++;
              }
 
              public void pop() {
                     int offset = (length - 1) % 4;
                     int index = (length - 1) / 4;
                     data[index] &= ~(3 << (offset * 2));
                     length--;
              }
 
              public char peek() {
                     return getChar(length - 1);
              }
 
              private char getChar(int charIndex) {
                     int offset = charIndex % 4;
                     int index = charIndex / 4;
 
                     int value = data[index] & (3 << (offset * 2));
                     if (offset != 0) {
                           value >>= (offset * 2);
                     }
                     return (char) (value + 'A');
              }
 
              public boolean isEmpty() {
                     return length == 0;
              }
 
              @Override
              public String toString() {
                     char[] arr = new char[length];
                     for (int i = 0; i < length; i++) {
                           arr[i] = getChar(i);
                     }
                     return new String(arr);
              }
       }

Воно зберігає дані в байтовому масиві, який розширюється за необхідності. Початковий розмір — 16 байт, хоча можна додати і можливість зміни цього параметра. І ось як виглядає сама реалізація алгоритму:

public class BitStorageStringReplacement extends BaseStringReplacement implements StringReplacement {
       public String replace(String text) {
              if (text == null || text.isBlank()) {
                     return text;
              }
 
              BitStorage stack = new BitStorage();
 
              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 {
                     return stack.toString();
              }
 }

Рішення 11. Паралелізація

Коли йдеться про оптимізацію, не можна уникнути можливості розпаралелювання алгоритмів. У принципі, початкове рішення досить просте:

  1. Ділимо рядок на N блоків.
  2. Кожен блок проходимо одним з алгоритмів, паралельно один від одного.
  3. Потім з’єднуємо всі блоки в один рядок і знову проходимо алгоритмом по об’єднаному рядку.

Таке рішення ймовірно буде швидше однопоточного варіанта, але загальну картину псує третій пункт, тому що нам доведеться проходити двічі одні й ті самі частини рядка (не видалені після пункту 2, і які не видаляться після загального проходу). Тому краще було б трохи підправити цей алгоритм:

  1. Ділимо рядок на N блоків.
  2. Кожен блок проходимо одним з алгоритмів, паралельно один від одного.
  3. Склеюємо блоки (виключаючи порожні) в один рядок, при цьому запускаючи один з алгоритмів для двох суміжних символів сусідніх блоків до тих пір, поки зустрінеться комбінація, яка не видаляється. Ці «спарені» символи ми не видаляємо, а запам’ятовуємо, і не копіюємо в результуючий рядок.

Це позбавить нас необхідності проходити ті самі підрядки двічі. Крім того, для ефективнішого виконання не будемо створювати нові рядки для кожного блоку, а натомість зберігати початок зміщення та розмір кожного блоку у вихідному рядку:

       class BlockInfo {
 
              private int offset;
 
              private int offsetEnd;
 
              private final List<Character> stack;
 
              public BlockInfo(List<Character> stack) {
                     this.stack = stack;
                     offsetEnd = stack.size();
              }
 
              public int length() {
                     return offsetEnd - offset;
              }
}

Worker — об’єкт, який конвертуватиме один з блоків:

       @RequiredArgsConstructor
       class Worker implements Callable<List<Character>> {
              private final int offset;
 
              private final int offsetEnd;
 
              private final String text;
 
              private final List<Character> stack = new ArrayList<>();
 
              public List<Character> call() {
                     char prevCh = 0;
 
                     for (int i = offset; i < offsetEnd; 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;
                           }
                     }
                     return stack;
              } 
       }

Метод findCommonLetters знаходить ті символи в суміжних блоках, які утворюють шукані комбінації і тому не повинні копіюватися в результуючий рядок:

       private int findCommonLetters(List<BlockInfo> blockList) {
              int counter = 0;
 
              BlockInfo prev = blockList.get(blockList.size() - 2);
              BlockInfo current = blockList.get(blockList.size() - 1);
              for (int j = 0; j < Math.min(prev.length(), current.length()); j++) {
 
                     char prevCh = prev.stack.get(prev.stack.size() - 1 - counter);
                     char ch = current.stack.get(counter);
                     for (Rule rule : rules) {
                           if (rule.match(ch, prevCh)) {
                                  counter++;
                                  break;
                           }
                     }
              }
              return counter;
}

Ось як виглядає основний клас. У даному варіанті ми не чекаємо завершення роботи всіх «workers», а приступаємо до склеювання, як тільки виконаються перші два, що теж прискорює загальний процес:

@RequiredArgsConstructor
public class ParallelStringReplacement extends BaseStringReplacement implements StringReplacement {
 
       private final ExecutorService executorService;
 
       private final int blockCount;
 
       public String replace(String text) {
              if (text == null || text.isBlank()) {
                     return text;
              }
 
              List<Future<List<Character>>> futures = IntStream.range(0, blockCount).boxed()
                           .map(i -> new Worker((text.length() * i) / blockCount, (text.length() * (i + 1)) / blockCount, text))
                           .map(executorService::submit).toList();
 
              List<BlockInfo> blocks = new ArrayList<>();
 
              int overallSize = 0;
 
              for (int i = 0; i < futures.size(); i++) {
                     Future<List<Character>> future = futures.get(i);
                     try {
                           List<Character> stack = future.get();
                           if (!stack.isEmpty()) {
                                  blocks.add(new BlockInfo(stack));
 
                                  if (blocks.size() > 1) {
                                         int counter = findCommonLetters(blocks);
                                         BlockInfo prev = blocks.get(blocks.size() - 2);
                                         if (counter > 0) {
                                                BlockInfo current = blocks.get(blocks.size() - 1);
                                                prev.offsetEnd = prev.stack.size() - counter;
                                                current.offset = counter;
                                         }
                                         overallSize += prev.length();
                                  }
                           }
 
                     } catch (InterruptedException | ExecutionException e) {
                           throw new RuntimeException(e);
                     }
              }
              if (blocks.size() > 1) {
                     BlockInfo last = blocks.get(blocks.size() - 1);
                     overallSize += last.length();
              }
              return toString(overallSize, blocks);
       }
 
              private String toString(int overallSize, List<BlockInfo> blockList) {
              if (overallSize == 0) {
                     return "";
              }
              char[] arr = new char[overallSize];
              int offset = 0;
              for (BlockInfo info : blockList) {
                     for (int j = info.offset; j < info.offsetEnd; j++) {
                           arr[offset + j - info.offset] = info.stack.get(j);
                     }
                     offset += info.length();
              }
              return new String(arr);
       }

Benchmarks

Будь-яке дослідження продуктивності має спиратися на benchmarks, причому, включаючи різні набори даних. Для тестування виберемо такий чудовий інструмент як JMH, і наступну конфігурацію:

  • JMH 1.35
  • JDK 18.0.2
  • Intel Core i9, 8 cores
  • 32 GB
  • 10 ітерацій обчислення, 10 ітерацій прогріву (warm-up)

Як вхідний набір було вибрано 4 вхідні рядки:

  1. Три, згенеровані випадковим чином iз символiв A,B,C та D, довжиною 10, 100 та 10 000 символів.
  2. Рядок CABBACCCABBACDCDDDDD, який після трансформації перетворює на порожній рядок.

Це дозволить оцінити розглянуті алгоритми з різних точок зору. Ось як виглядає сам тест (основний блок):

@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 10)
@Measurement(iterations = 10)
public class StringReplacementBenchmark {
 
       private Map<String, StringReplacement> replacements;
 
       private Map<String, String> inputStrings;
       @Param({ "simple", "simpleParallel", "regex", "builder", "stack", "arrayList", "linkedList", "bufferList", "bitStorage", "buffer", "parallel" })
       private String replacement;
 
       @Param({ "10", "100", "10000", "custom" })
       private String size;
 
       @Benchmark
       public String replace() {
              return replacements.get(replacement).replace(inputStrings.get(size));
       }

Benchmarks (рядок CABBACCCABBACDCDDDDD)

Benchmark (replacement) Score Error Units

StringReplacementBenchmark.replace simple 3255.547 ± 5.525 ns/op

StringReplacementBenchmark.replace simpleParallel 23147.149 ± 141.735 ns/op

StringReplacementBenchmark.replace regex 1426.503 ± 16.879 ns/op

StringReplacementBenchmark.replace builder 201.917 ± 0.706 ns/op

StringReplacementBenchmark.replace stack 127.377 ± 2.653 ns/op

StringReplacementBenchmark.replace arrayList 147.139 ± 10.541 ns/op

StringReplacementBenchmark.replace linkedList 149.347 ± 0.776 ns/op

StringReplacementBenchmark.replace bufferList 142.820 ± 0.780 ns/op

StringReplacementBenchmark.replace bitStorage 148.453 ± 44.769 ns/op

StringReplacementBenchmark.replace buffer 167.058 ± 1.298 ns/op

StringReplacementBenchmark.replace parallel 15769.084 ± 74.806 ns/op

Benchmarks (рядок з 10 випадкових символів)

Benchmark (replacement) Score Error Units

StringReplacementBenchmark.replace simple 670.240 ± 0.809 ns/op

StringReplacementBenchmark.replace simpleParallel 7909.280 ± 226.005 ns/op

StringReplacementBenchmark.replace regex 649.213 ± 24.331 ns/op

StringReplacementBenchmark.replace builder 103.060 ± 0.335 ns/op

StringReplacementBenchmark.replace stack 79.179 ± 1.165 ns/op

StringReplacementBenchmark.replace arrayList 95.516 ± 2.103 ns/op

StringReplacementBenchmark.replace linkedList 88.995 ± 0.594 ns/op

StringReplacementBenchmark.replace bufferList 97.969 ± 2.670 ns/op

StringReplacementBenchmark.replace bitStorage 79.017 ± 0.249 ns/op

StringReplacementBenchmark.replace buffer 123.694 ± 0.467 ns/op

StringReplacementBenchmark.replace parallel 15929.431 ± 54.695 ns/op

Benchmarks (рядок із 100 випадкових символів)

Benchmark (replacement) Score Error Units

StringReplacementBenchmark.replace simple 4046.794 ± 4.850 ns/op

StringReplacementBenchmark.replace simpleParallel 36119.101 ± 810.487 ns/op

StringReplacementBenchmark.replace regex 8504.307 ± 39.604 ns/op

StringReplacementBenchmark.replace builder 1049.536 ± 4.766 ns/op

StringReplacementBenchmark.replace stack 793.432 ± 4.403 ns/op

StringReplacementBenchmark.replace arrayList 799.454 ± 4.480 ns/op

StringReplacementBenchmark.replace linkedList 727.457 ± 1.946 ns/op

StringReplacementBenchmark.replace bufferList 841.064 ± 74.309 ns/op

StringReplacementBenchmark.replace bitStorage 635.134 ± 1.108 ns/op

StringReplacementBenchmark.replace buffer 850.442 ± 2.480 ns/op

StringReplacementBenchmark.replace parallel 15754.904 ± 43.528 ns/op

Benchmarks (рядок із 10000 випадкових символів)

Benchmark (replacement) Score Error Units

StringReplacementBenchmark.replace simple 1089268.251 ± 3245.402 ns/op

StringReplacementBenchmark.replace simpleParallel 1111856.618 ± 4519.110 ns/op

StringReplacementBenchmark.replace regex 1632799.341 ± 9501.829 ns/op

StringReplacementBenchmark.replace builder 174004.111 ± 154.164 ns/op

StringReplacementBenchmark.replace stack 91647.165 ± 164.663 ns/op

StringReplacementBenchmark.replace arrayList 88729.933 ± 245.883 ns/op

StringReplacementBenchmark.replace linkedList 109917.186 ± 348.930 ns/op

StringReplacementBenchmark.replace bufferList 100052.354 ± 261.096 ns/op

StringReplacementBenchmark.replace bitStorage 94990.502 ± 230.537 ns/op

StringReplacementBenchmark.replace buffer 90874.696 ± 344.350 ns/op

StringReplacementBenchmark.replace parallel 76515.380 ± 406.090 ns/op

Так як в останньому тесті найкращий результат показав паралельний алгоритм (з пулом з 4 потоків), то додатково ще було тестування цього варіанту з різною кількістю струмів..

Benchmarks (рядок із 10000 випадкових символів, паралельний алгоритм)

Benchmark (size) (threads) Score Error Units

StringReplacementBenchmark.replace 10000 2 81786.148 ± 1611.957 ns/op

StringReplacementBenchmark.replace 10000 4 79545.415 ± 421.482 ns/op

StringReplacementBenchmark.replace 10000 8 74637.462 ± 1110.342 ns/op

StringReplacementBenchmark.replace 10000 16 70088.417 ± 656.944 ns/op

StringReplacementBenchmark.replace 10000 32 69466.629 ± 570.839 ns/op

Витрата пам’яті

Цікаво також оцінити витрату пам’яті, але не кожного з 11 алгоритмів, а різних стратегій зберігання додаткової пам’яті. Спочатку розглянемо варіант, коли вхідний рядок містить 100 символів «A».


Спосіб зберігання (алгоритм)


Об’єм пам’яті (байт)


Примітка


Рядок (простий, regex)


100


1 новий рядок


StringBuilder


100



ArrayList, Stack


818


100 елементів масиву Character (кожне посилання по 8 байт) та один об’єкт Character (18 байт)


LinkedList


3600


100 елементів по 36 байт


Однозв’язний оптимізований список


1200


50 елементів по 24 байта


Bit storage


25


Тепер спробуємо розібрати інший варіант — рядок із 100 символів (перші 50 «A», другі 50 «B»).


Спосіб зберігання (алгоритм)


Об’єм пам’яті (байт)


Примітка


Рядок (простий, regex)


5000


(100 + 0) * 100/2


StringBuilder


50



ArrayList, Stack


418


50 елементів масиву Character (кожне посилання по 8 байт) та один об’єкт Character (18 байт)


LinkedList


1800


50 елементів по 36 байт


Однозв’язний оптимізований список



25 елементів по 24 байта


Bit storage


13


Висновки

Почнемо з витрат пам’яті. Тут беззаперечний лідер — алгоритм, який використовує бітову маску. На другому місці StringBuilder. Найгірше справи у простого алгоритму і LinkedList.

Щодо швидкості роботи, то тут дуже багато нюансів:

  1. Паралельний алгоритм найкраще проявив себе на рядку з 10000 рядків (перше місце) і виявився аутсайдером в інших варіантах. При цьому він непогано розподіляється, досягаючи максимуму продуктивності при 16 потоках.
  2. Алгоритм з бітовою маскою найкраще показав себе на тестах 10 і 100 рядків (перше місце). На 10000 рядків він лише 5-й.
  3. Алгоритм з буфером-приймачем добре показав себе на 10000 рядків (3-е місце), в інших випадках він не увійшов до ТОП-5. Поєднання з однозв’язковим списком добре зарекомендувало себе у варіанті з «палаючим рядком» — 2-е місце, в інших випадках — 6-7-е місце.
  4. Stack дуже добре показав себе у всіх варіантах (скрізь потрапив у ТОП-3), а в першому варіанті взагалі став лідером. Тут можна згадати про оптимізацію в JVM, коли вона прибирає блокування synchronized, якщо об’єкт використовується лише локально (lock elision).
  5. ArrayList також показав стерпні результати (скрізь потрапив у ТОП-4).
  6. LinkedList добре себе показав на невеликих рядках (10 і 100 символів), випередивши ArrayList, але в тесті на 10000 символів ArrayList вже опинився на 20% швидше. Думаю, що далося взнаки створення великої кількості об’єктів.
  7. StringBuilder скрізь посів 6-8 місця.
  8. Варіант з регулярними виразами зайняв місце внизу таблиці, програючи лідерам за часом у 10-20 разів.
  9. Простий варіант показав приблизно схожу продуктивність, десь виграючи, десь програючи.
  10. Найгірше відпрацював варіант з паралельним Streams API, причому чим менше було символів, тим більше було відставання.

Як ви бачите, у кожного з 11 варіантів є свої плюси і мінуси, вибір тільки за тим, що для вас критичніше — компактність, надійність, витрата ресурсів або адаптивність до змін. Сподіваюся, що вам знадобляться ті алгоритми та стратегії оптимізації, розглянуті в цій статті, тому що ви їх можете використовувати в різних завданнях.

👍ПодобаєтьсяСподобалось4
До обраногоВ обраному4
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Як би я вирішував задачу: 2 підходи, залежно від того, чим насправді є строка, умовно невеличким об′єктом, який поміститься в оперативі цілком, тобто матиме довільний доступ, або ж стрімом, який можна пройти по суті лише 1 раз.
Якщо є random access: зробити зі строки масив символів, проходити циклом, пам′ятаючи попередній символ та його номер в масиві. Якщо попередній та поточний потрапляють до фільтра, замінювати обидва на NULL (чи інше легко впізнаване значення) та відкочуватись назад на 1 символ, коригуючи значення попереднього (на 1 менше), наступного (ітератор масиву на 1 більше), попередній символ (перевіряємо на >0 його індекс). Підраховуємо кількість символів у результуючому масиві, щоб створити масив одразу потрібного розміру без зайвих витрат. А потім вже символ за символом копіюємо один масив в інший в циклі, пропускаючи NULL значення.

Якщо стрім — задача є в цілому невирішуваною. Бо по суті потрібно відмотувати масив в обох напрямках. То ж або має бути можливість повторного проходу, або читати потік назад. Це вимагає роботи із файлом не як із потоком. Звісно, для символів таке робити це рідкісний гемор (ми ж пам′ятаємо, що операція запису досить коштовна). Тобто, повторний проход є єдиним оптимальним рішенням. Можна зробити оптимізацію із частковою буферизацією, якщо повторний прохід є коштовною операцією та має бути радикально знижена його ймовірність. На 100% її не знизити.

Візуально ця задача схожа на гру Zuma, спробуйте побачити очима, чому вона не може бути оптимізована для вирішення в 1 прохід, але може бути оптимізована як для пам′яті, так і для кількості операцій її виділення, а також має суттєве зниження ймовірності зхлопування шариків поза буферною (видимою) зоною — хоча можливе й руйнування усього потоку в цілому.

Если стрим то добавлять элементы в список/стек(удаляя комбинации когда они появляются) и повторный проход не нужен. Для больших строк, вероятно, будет лучше создать список маленьких массивов(скажем по 16 или 32 элемента) с аналогичным решением

В том-то и дело, что удалять надо в обе стороны. Каждый следующий элемент имеет право удалить 1 предыдущий, но при этом нужно ДОБЫТЬ тот, что был перед ним. То есть отмотать назад. И в худшем случае у тебя будет пустая строка на выходе, можно так составить, что она вся из середины сколлапсирует.

Я не просто так узнал в этом алгоритме Зуму, представив, как бы я делал это руками.

Максимально после считывания 1 символа вы будете отматывать на 2 элемента назад(что не является большой проблемой). Строка будет распадаться по 1 элементу, а не вся сразу. Таким образом после добавления каждого элемента вам придется сделать О(1) действий. Не думаю что стоит вдаваться в подробности реализации этой искусственной задачи, но, вцелом, если грамотно написать(как подсказывает мой скромный опыт — использование просто списка хуже чем использования списка массивов) то это нормально будет работать. Проблема со стримом была бы только если бы добавление символа приводило бы к схлопыванию сразу нескольких пар символов

В том-то и дело, что стрим назад не умеет. Схлопывание и происходит по нескольку пар, почитай условие задачи. То есть после выкидывания комбинации нужно снова проверить, не получилась ли снова фильтруемая, и если да — она отожрёт ещё 1 символ, и так до половины длины строки в худшем случае. Грубо говоря, строка может коллапсировать полностью.

После выкидывания комбинации не может появиться новая до того как мы считаем следующий элемент. Это не зума где 1 выстрелом можно схлопнуть всю прямую(ведь мы стреляем не в середину, а только в конец), мне кажется вы не правильно понимаете условие

Моё почтение автору, не каждый сможет придумать столько неэффективных решений к этой задаче

І чим краща ця задача ніж 100 500 тищ мільйонів подібного щастя з літкоду і йому подібних помийок? Тупо сурогатна штучна задача, створена під готове рішення. Якщо такі сурогати потрібні щоб пояснити теорію — в мене для вас погані новини.

Був неправий, задача дійсно цікава із точки зору не тільки ефективності, але й неочевидності алгоритмів із надкороткими циклами. Там, де власне сама дія є простою, але таких дій треба виконати мільйони за раз. І недостатньо просто оцінити асимптотичну складність алгоритму, тут треба бачити, що накладні витрати на побудову алгоритму, зокрема, їхня нелінійність, що в рази зменшує швидкодію процесора — впливають ані трохи не менше.

Підписатись на коментарі