Як по-різному оптимізувати алгоритми в Java, або Історія одного завдання. Частина I

💡 Усі статті, обговорення, новини про Java — в одному місці. Приєднуйтесь до Java спільноти!

Всім привіт. Я Сергій Моренець, розробник, викладач, спікер та технічний письменник, хочу поділитися з вами своїм досвідом роботи з такої цікавої теми як структури даних, алгоритми та їхня оптимізація. Впевнений, що ніхто не розповість про алгоритми краще, ніж Дональд Кнут у його фундаментальній роботі «Мистецтво програмування». Мета цієї статті в іншому — на конкретному прикладі показати досвід використання та застосування різних алгоритмів та структур даних у Java.

Стаття ця не випадкова, а вся історія почалася на одній технічній співбесіді, де мене попросили на стадії Live coding вирішити, здавалося б, просте завдання з трансформації рядка. Причому наголос у реалізації треба було зробити не так на правильність, а саме на ефективність. Більше того, до цього завдання йшли спеціальні тести, який перевіряли продуктивність рішення. Завдання я вирішив і у відведений час вписався, але на цьому історія не закінчилася. Я вважаю, що чим вищий рівень (кваліфікація) спеціаліста, тим більше різних правильних рішень (підходів) він може дати на те саме питання. Обдумування цього завдання привело мене до висновку, що воно не настільки тривіальне, як мені спочатку здалося.

Думаю, що ви знаєте, що будь-який проєкт можна оцінити за допомогою трьох показників (Час, Якість, Фінанси). Ви можете вибрати будь-які два показники, пожертвувавши третім. Аналогічно з технічним рішеннями. Для деяких важлива компактність або читабельність. Для інших — витрата ресурсів та продуктивність.

Мені здалося цікавим знайти всі інші рішення, перевірити їх на продуктивність за допомогою benchmarks, а також пояснити, яке ж рішення в яких випадках варто використовувати. А згодом ми обговорили ці рішення на наших курсах. Я сподіваюся, що стаття буде цікава всім розробникам, оскільки схожі завдання часто зустрічаються на live coding або технічних завданнях. І ви зможете застосувати розглянуті принципи та алгоритми, стратегії оптимізації як на співбесідах, так і в роботі.

Завдання

Отже, необхідно реалізувати інтерфейс StringReplacement:

@FunctionalInterface
public interface StringReplacement {
 
       String replace(String text);
 }

де метод replace() повинен перетворювати рядок за такими правилами:

  1. Рядок може бути будь-якого розміру і містити лише символи A, B, C або D.
  2. Якщо передається порожній рядок (або null), то його потрібно повернути.
  3. Метод повинен шукати всі комбінації символів 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 змінні. Отже, це проста, зрозуміла реалізація, до якої є претензії щодо ефективності:

  1. Ми для кожної комбінації змушені проходити знову весь рядок (що більше комбінацій, тим повільніше працює це рішення).
  2. containsRules додає ще більше ітерацій проходу рядка.
  3. При кожній ітерації ми створюємо новий рядок, навіть якщо було замінено лише одну комбінацію (два символи).

Таким чином, цей код виграє у простоті, але програє в швидкості та об’ємі використовуваних ресурсів. Але не можна таке рішення назвати невдалим чи нездатним. Якщо у вас невеличка кількість рядків, а самі рядки невеликого розміру (10-20 символів), то подальші спроби покращити продуктивність виглядатимуть як premature optimization.

Рішення 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 через блокування.

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

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

По суті, ми можемо розробляти і оптимізувати кожен з компонентів окремо, не боячись, що це зашкодить решті частин. Тому додамо новий інтерфейс 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, яку ви використовуєте:

  1. У Java 8 і раніше виграшу не буде, тому що в обох випадках ми зберігатимемо символи в масиві char
  2. Але у 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.

👍ПодобаєтьсяСподобалось12
До обраногоВ обраному7
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

Рішення за одну ітерацію із бектрекінгом при видаленні:

package replacer;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.stream.Collectors;

public class Replacer {

  public static void main(String args[]) {
    String input = args.length > 0 ? args[0].toUpperCase().replaceAll("[^ABCD]+", "") : "";

    System.out.print("Input: ");
    System.out.println(input);
    // Speaking of optimizations - know why I did this?
    // To avoid concatenating strings. Imagine a case when input is 1Gb of size.
    // So you do "Input:"+input - which produces a new string of an even bigger size. 2Gb of
    // RAM used for nothing.
    System.out.print("Result: ");
    System.out.println(replace(input));
  }

  public static String replace(String str) {
    LinkedList<String> chars = new LinkedList<>(Arrays.asList(str.split("")));

    ListIterator<String> iter = chars.listIterator();
    String prevLetter = null;
    String curLetter;
    while (iter.hasNext()) {
      if (prevLetter == null) {
        // We're on a first letter
        prevLetter = iter.next();
      } else {
        // We're past 1st letter
        curLetter = iter.next();
        boolean match = isAMatch(prevLetter, curLetter);
        if (!match) {
          // No match - move on
          prevLetter = curLetter;
        } else {
          // We have a match - delete and re-check
          iter.remove();
          iter.previous();
          iter.remove();
          if (iter.hasPrevious()) {
            prevLetter = iter.previous();
          } else {
            // We're on start of a list now, e.g. we had something like "AB???" and we just removed
            // "AB" from the beginning
            prevLetter = null;
          }
        }
      }
    }

    return chars.stream().collect(Collectors.joining());
  }

  private static boolean isAMatch(String prevLetter, String curLetter) {
    return prevLetter.equals("A") && curLetter.equals("B")
        || prevLetter.equals("B") && curLetter.equals("A")
        || prevLetter.equals("C") && curLetter.equals("D")
        || prevLetter.equals("D") && curLetter.equals("C");
  }
}

І тест:

package replacer;

import java.util.Arrays;
import java.util.List;

public class Test {

  public static class StrPair {
    public String a;
    public String b;

    public static StrPair of(String a, String b) {
      StrPair result = new StrPair();

      result.a = a;
      result.b = b;

      return result;
    }
  }

  public static void main(String args[]) {
    List<StrPair> testCases = Arrays.asList(StrPair.of("ABC", "C"), StrPair.of("AACC", "AACC"),
        StrPair.of("BCDAD", "D"), StrPair.of("AAAAABBBB", "A"), StrPair.of("ABBAABBA", ""));

    boolean fails = false;
    for (StrPair testCase : testCases) {
      String result = Replacer.replace(testCase.a);
      if (!testCase.b.equals(result)) {
        fails = true;
        System.out.println("Failed: " + testCase.a + " => " + result + ". Expected " + testCase.b);
      }
    }
    if (!fails) {
      System.out.println("Success!");
    } else {
      System.err.println("Fail!");
    }
  }
}

Я замінив тег code на pre, щоб форматування було кращим.

Хто б уже довісив rich text editor, можливо й не по дефолту, а щоб легко було увімкнути. Для чого потрібен: деякі речі взагалі важко читати, якщо текст довгий. Зокрема, й той самий код, якому б не завадила підсвітка синтаксису.

DOU ж у будь-якому разі залишиться, навіть якщо Україна Москву візьме. Тому треба дивитися у майбутнє, саме на контент для випадково зайшовшого читача, який ще навіть не реєструвався, а просто натрапив через пошуковий сервер чи ще десь підчепив лінк.

Почати варто зі звичайної демократії — а що саме хотілося б змінити у дизайні DOU. Це не обов′язково робити зараз, просто виявити, можливо щось із того є дрібничками, які зробити дуже легко. Наприклад, змінити стиль цитування, зараз текст виглядає слабеньким сірим (наскільки слабеньким — залежить від типу екрану та рівня підсвітки). З тегом pre взагалі проблема — він мав би вставляти текст неформатованим, того самого фону, аж ніяк не створювати за собою темно-сірий бокс. Із картинками та відео ніщо не заважає додати трохи демократизму, щоб вони не були частиною контенту, але були iframe, наприклад щоб користувач самостійно їх відкривав та завантажував, лише коли хоче побачити, натиснувши відповідну кнопку чи спеціальним чином оформлений лінк.

Чому ці дрібнички потрібні: пришвидшення споживання контенту. Це дозволить зробити потік обговорення ще швидшим, що дозволить перетворити відвідини DOU у звичку. А на додачу — дозволити рекламодавцям вставляти рекламні блоки прямо у стрічку чужого матеріалу чи коментів, там де вони захочуть, із автоматичним списанням грошенят за це, звісно ж з обмеженням показу по часу та/або кількості переглядів. Матеріали реклами також мають цензуруватися (інакше рекламуватимуть усяке лайно), бажано відкриватися у iframe, щоб не підпадати під індексування пошуковими серверами. Але факт є фактом, DOU є соціальною мережею, соціальні мережі заробляють на рекламі. А реклама — не завжди погано, це рушій торгівлі, і там де реклама контрольована — вона приносить дохід навіть її споживачам.

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

Чому реклама на подібних ресурсах корисна: читаюча та думаюча аудиторія. Вона цінна. Але її легко отруїти інформаційним сміттям, якщо дати на відкуп стандартним постачальникам реклами, здебільшого орієнтованої на дурнів. Цінну аудиторію можна продати дорожче, і що важливіше, постійним клієнтам. Це аудиторія товарів та послуг, які обирають виважено. Зазвичай замовники якісної реклами розчаровуються, бо їхня реклама потрапляє до загальної помийки, і звідти не приносить продажів. Це величезна ніша насправді. За умови інформаційної гігієни, зокрема забороні реклами фондів, азартних ігор, та «допомоги безголовим діткам», які є майже 100% шахрайськими проектами.

Довіском має бути бонус: розміщення великої рекламної статті саме на DOU, із посиланням вже з неї на лендинг. Це дасть більш високу воронку продажів, бо читач, потрапивши з DOU на DOU зберігає лояльність до «свого» ресурсу, перед тим як перейшов на чужий. Критерій «свій/чужий» є ключовим для формування відношення до інформації. Але рекламна стаття на DOU звичайно ж буде регламентуватися редакційною політикою, ніякого клікбейту та дуркування, або серйозно та з повагою до аудиторії, або ніяк. Політична реклама, до речі, має бути дозволена — ми ж знаємо, що думаюча аудиторія є активною апріорі. Але не плутати із «джинсою» та «чорним піаром», реклама має бути саме рекламою, тобто про себе та від першої особи.

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

Повторюся, якісна реклама якісних продуктів чи послуг — корисна усім сторонам, вона розвиває економіку. У будь-якому разі споживачі витрачають немало часу на пошук цієї інформації, від так, реклама є для них послугою: рекламодавця змушують до краткості банера/тексту з одного боку, і до повноти розкриття інформації з іншого. Щоб реклама не набридала, за опт має бути надбавка. Тобто, показ 1 особі більш ніж 7 разів, але не більше 14 — подвійна оплата за перебір норми, інакше лімітовано. Більше 14 — тільки в індивідуальному порядку.

Чому DOU має заробляти? А чому ні? Наприклад, реклама IT продуктів, зокрема стартапів — ну де його ще рекламувати? Ну не у ютубі ж, там уся краща аудиторія або на преміумі, або на блокираторах, або вже звіріє від реклами шахрайства. Тобто, сама фільтрація реклами і вибір лише такої, за яку не соромно — це власне і є корисна робота, тобто це реально зароблені редактором гроші, при цьому сам ресурс залишається чистим від сміття.

Наскільки конкретна реклама буде неприємна — можна просто давати кнопочку-хрестик для її закриття та зібрати статистику, буде вище якогось ліміту доля невдоволених — автоматично летить повідомлення редактору. Тому, хто натиснув хрестик, саме цю рекламу більш не показувати, хіба що заплатили по двійному тарифу, тоді показати максимум ще 1 раз. Контролювати закриття саме через ту таблицю, де обраховується кількість показів конкретної реклами. Таблиці для обрахування мати дві: одну повну для всієї реклами за увесь час, одну поточну — для активної реклами у поточну добу, а вночі синхронізувати. Це дозволить не засирати оперативну пам′ять бази даних та не задовбувати базу оновленням індексів. Спеціальний показник треба обраховувати — скільки було показів до того, як читач клікнув рекламу. Не-зареєстрованих користувачів просто враховувати як окремого одного користувача. Навряд чи для продажу услуги реклами рекламодавцю знадобиться більша статистика, усе інше нехай сам збирає за своїми лінками. Що саме допустимо передати за лінком з персональних даних — то вже питання етики, але за передзвон одразу після кліку — буде кіпіш.

P.S. Ілля Бовтрюк правильно написав — можна ще оптимізнути не створюючи наперед LinkedList (бо в принципі це ще одна ітерація), а перевіряючи в процесі додавання в LinkedList.

Далі вже мабуть оптимізувати нікуди.

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

А якщо вже бенчмаркаєте, візьміть справді різні дані — наприклад з десяток стрічок в мільярд символів — а не тільки коротенькі приклади.

Якось так:

package replacer;

public class Replacer {

  public static void main(String args[]) {
    String input = args.length > 0 ? args[0].toUpperCase().replaceAll("[^ABCD]+", "") : "";

    System.out.print("Input: ");
    System.out.println(input);
    // Speaking of optimizations - know why I did this?
    // To avoid concatenating strings. Imagine a case when input is 1Gb of size.
    // So you do "Input:"+input - which produces a new string of an even bigger size. 2Gb of
    // RAM used for nothing.
    System.out.print("Result: ");
    System.out.println(replace(input));
  }

  public static String replace(String str) {
    StringBuilder result = new StringBuilder();

    char prevLetter = 0;
    char curLetter;
    for (int i = 0; i < str.length(); i++) {
      curLetter = str.charAt(i);
      if (prevLetter == 0) {
        // We're on a first letter
        prevLetter = curLetter;
        result.append(prevLetter);
      } else {
        // We're past 1st letter
        boolean match = isAMatch(prevLetter, curLetter);
        if (!match) {
          // No match - move on
          prevLetter = curLetter;
          result.append(curLetter);
        } else {
          // We have a match - delete and re-check
          result.setLength(result.length() - 1);
          if (result.length() > 0) {
            prevLetter = result.charAt(result.length() - 1);
          } else {
            // We're on start of a list now, e.g. we had something like "AB???" and we just removed
            // "AB" from the beginning
            prevLetter = 0;
          }
        }
      }
    }

    return result.toString();
  }

  private static boolean isAMatch(char prevLetter, char curLetter) {
    return prevLetter == 'A' && curLetter == 'B' || prevLetter == 'B' && curLetter == 'A'
        || prevLetter == 'C' && curLetter == 'D' || prevLetter == 'D' && curLetter == 'C';
  }
}

P.S. Обійшлись без лінкд ліста лише тому, що видаляєм завжди останній елемент в масиві (StringBuilder в даному випадку нам за масив).

Але ми тут по пам’яті створюєм нову копію в worst case. Наприклад для вводу «AAAAAAAA...» де ніколи нічого не спрощується, або нехай буде десь мінімально одне-два B на мільярд A — ми створим ще новий StringBuilder заповнений цими ж даними.

Теоретично можна було б передавати на вхід якийсь масив в якому одразу робити ті зміни, і мати кращий результат по пам’яті. Але тоді нам на вхід більше підходить власне двозв’язний список.

От тільки навряд чи ми можем змусити користувача використовувати конкретну структуру даних під нас. Але якщо могли б — LinkedList з char-ів на вхід замість String було б ідеально.

Коментар порушує правила спільноти і видалений модераторами.

Коментар порушує правила спільноти і видалений модераторами.

Коментар порушує правила спільноти і видалений модераторами.

Добавляем элементы в двухсвязный список по очереди, если новый элемент с последним неудаленным образовывают пару то удаляем. O(n) по памяти и скорости. Скорость асимптотически, ясно, не улучшить. Память, думаю, тоже, из-за строк вида «аааббб». Легко модифицируется для общего случая(когда в алфавите более 4 букв), просто делаем двумерный массив, в котором отмечены пары которые стоит удалить(первая координата — первая буква, вторая координата — вторая)

Варіантів може бути багато. Тільки benchmarks покажуть, який краще. Але це вже у другій частині.

Там два вложених while і один if, на Codility цю задачку бачив, вона за 5 хвилин робиться.

Тут, мне кажется, достаточно и 1

Чомусь завжди те що бачив — «робиться за 5 хвилин». А те що сам зробив — за тиждень :)

Цікава тема, але трохи дивні варіанти — наперед очевидно неефективні.

Особливо не бачу сенсу використовувати ArrayList замість зв’язного списку.

Зовсім не бачу сенсу робити перевірку на наявність комбінацій а потім заміну окремо, або робити заміни різних комбінацій в окремих проходах. Це ж очевидно неефективно.

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

Яким чином, ви прочитавши код, без performance тестів, відразу сказали, який варіант працюватиме швидше, а який ні?
Тут крім того, можуть бути різні результати, залежно від довжини рядка і того, наскільки часто трапляються шукані комбінації.
Але найбільше здивувало те, що Solution architect каже, що зв’язний список кращий за ArrayList, якщо давно відомо, що ArrayList швидше (використовує менше пам’яті та об’єктів). Це до речі та benchmarks показують.

без performance тестів

Ну очевидно ж що якщо робити зайві речі, яких можна не робити — то буде повільніше.

можуть бути різні результати

Не факт. Маєте приклад?

зв’язний список кращий за ArrayList, якщо давно відомо, що ArrayList швидше (використовує менше пам’яті та об’єктів)

:D
Оце хохма. То ви кажете що LinkedList треба видалити взагалі, бо ArrayList шивдше ЗАВЖДИ? Ви серйозно?

Ви розумієте що відбувається коли ви видаляєте елемент З СЕРЕДИНИ ArrayList? Або з початку?

P.S.

benchmarks показують

Окремо встидно мало б бути вам таке писати. Ви взагалі розрізняєте scalability і performance? Ви розумієте про що big O notation?

Це не про перформенс, це про скалабіліті — про масштабованість а не про швидкість на конкретних випадках.

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

Але все одно — скейляться обидва варіанти лінійно!

Що O(n) що O(n/2) — константи не рахуються в big O, це той самий O(n). Хоча перформить одна з них типу в два рази швидше. Але СКЕЙЛЯТЬСЯ вони ОДНАКОВО.

Якщо n стане в два рази більше, то що перший варіант хеш функції відпрацює вдвічі повільніше, що другий.

Так от до чого це я — видалення поточного елементу з LinkedList, або вставка в LinkedList — це O(1), а з ArrayList (крім випадку видалення з самого кінця) — O(n).

Спробуйте це зрозуміти перед тим як писати, що «на якихось конкретних даних ArrayList все одно вийшов швидше — бенчмарк показав».

и можемо перевіряти не входження символів, а суму їх ASCII-кодів

Щось мені підказує, що для кодів не тільки
В + С == С + В
але й
В + С == А + D == B + B ...
Тобто будуть видалені ще й усі ці комбінації?

А чому

В + С == А + D == B + B ..

?

Ми повинні замінити лише комбінації AB, BA, CD, DC.
Складання ASCII-кодів A і B дає 131.
Жодна інша сума ASCII-кодів символів (AC, BC, DA, BD) не дасть таке число, а це означає, що ми видалимо тільки ту комбінацію, яку і повинні.

Якщо я правильно розумію, то в вхідному рядку можуть бути будь-які символи.
А цьому коду взагалі без різниці, чи це АС, чи ВВ, аби сума збіглась:

if (rule.match(ch, prevCh)) {
public boolean match(char first, char second) {
return first + second == sum;
}

На щастя ні

за такими правилами:
Рядок може бути будь-якого розміру і містити лише символи A, B, C або D.

Тоді так, для послідовних пар воно повинно працювати.
Але розширенню не підлягає.

Розширенню в сенсі якщо умови задачі зміняться, і треба буде дозволяти якісь інші пари чи інші символи? Ну так, очевидно — якщо змінились умови задачі то оптимальне рішення буде інше.

Так, але це код з базового класу. А в спадкоємцях чітко зазначено, яку саме суму ми шукаємо

public class ABRule extends BaseRule implements Rule {

       ABRule() {

              super('A' + 'B');

       }

}

Дякую, реально цікаве дослідження, чудова стаття

Дякую за вiдгук. Це лише перша частина. Друга частина буде набагато цікавішою.

На третій день індіанець Зорке Око помітив, що

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

У цьому маразм «тестових» завдань. Абсолютній більшості програмістів, я б сказав що менше ніж 1 на 1 000 000, знадобиться оптимізувати String replacement. У більшості випадків ділянка коду за весь час існування витратить менше машинного часу, аніж було витрачено на її написання. Тому навіть для нестандартних задач найпростіше (найчитабельніше) рішення зазвичай є найкращим, бо радикально зменшує ймовірність помилок кодування. А якщо задача має стандартне (бібліотечне) рішення — то використати треба саме його.

PS. А навіщо було розбивати на частини? Хіба не простіше усе скласти в одну статтю. Тим більше нічого іноваційного там нема, більшість читатиме її «по діагоналі», пропускаючи лікбез.

PPS. Для бенчмарку варто використати великий текст. Скажімо в мільйон знаків. Звісно ж не примітивно згенерований (що може вплинути на результат статистичним перекосом), а наприклад, Lorem Ipsum.

А навіщо було розбивати на частини?

Можна було й одну статтю. Але в сумі коду тексту близько 25 сторінок, що явно більше, ніж звичайна стаття на ДОУ. Крім того, мені ще хотілося отримати фідбек після першої частини, щоб потім якщо потрібно скоригувати другу частину у бік поліпшення.

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

Тут проблема в тому, що за час, відведений на тестове завдання (а було відведено не більше години), ви просто не встигнете написати тести на всі можливі corner-cases, і звичайно шанси зробити помилку дуже великі.
Крім того, як я і написав, для цього завдання потрібно було написати не просто правильне, а й суперефективне рішення, яке якимось чином перевірялося.

Ще тут підійде LinkedList заюзать, після видалленя, сусіди міняються і можемо знову перевіряти, чи можна видалити

У другій частині статті буде такий варіант. Там є що обговорити

А як щодо заюзати рекурсію + бінарним розбиття з pivot-ом, де точно не можемо видалити, наприклад DA.
Зупинитися, коли вже не можна ділити, і провести clean-операцію.
Далі повторити.

replace(CBABABDDABCCBBAA)

[CBABABDD] [ABCCBBAA]
[CBABAB] [DD] [ABCC] [BBAA]
[CB] [ABAB] [DD] [AB] [CC] [BBAA]

[CB][][DD] [AB] [CC][] clean()

replace(CBDDABCC); повторюємо.

Чи є тут проблеми? Якщо ні, то складність теж порахувати б)

Цікавий варіант, я про нього не думав. Щодо проблем — є ж обмеження на вкладеність стека. І тут можливе обмеження на довжину вхідного рядка.

Імхо, саме такий алгоритм і повинен запропонувати кандидат одразу. Розділяти можна просто порівну. Якщо розділення відбудеться по комбінації, котру ми шукаємо, то вона або вже не буде актуальною після процесінгу двох половин, або вирішиться після з’єднання.
Враховуючи, що літери лише 4, то додаючи hash мапу із вхідним параметром та результатом, алгоритм буде оптимізованим. В гіршому випадку буде O(n), в кращому (це коли перша половина інпуту так сама як і друга) O(logn).

O(logn)

? серйозно. :)

Що буде для «AAAAABBBB» ?

наприклад
AAAAABBBB ->
[AAAA] [ABBBB]
[AA] [AA] [AB] [BBB]

clean()
[AA][AA] [] [BBB]

replace(AAAABBB) ...

Буде efficient, якщо після replace(left) та replace(right) перевірити adjacent літери. В найгіршому випадку (AAAABBBB) то буде O(n). Але ж O(n) і в тих алгоритмах, що описані в статті навіть в кращих випадках.

А це буде коректно заміняти для всіх випадків? Результат при заміні з середини не буде відрізнятись від заміни від початку?

В умовах задачі нічого не сказано про порядок того, як і що видаляти.
Так і в тому і сенс, що ми розбиваємо проблему на дві підпроблеми, кожна за яких може вирішуватись (ABAB), а може ніт. Тобто місце, де з’єднуються результати двох підпроблем, є єдиним місцем, де можуть виникнути комбінації.
І звісно, що видалення комбінацій після з’єднання повинно відбуватись лише у випадку, якщо там вони є.

Я подумав — в принципі немає різниці, тому що правила AB і BA не перетинаються із CD і DC.

А при випадках типу ABA без різниці чи ми заміним AB чи BA — залишиться все одно одне А.

Але тоді виходить що найбільш efficient підхід — просто пройтись до першої комбінації, і по видаленню перевірити сусідів на створення нової комбінації.

Якщо є — знову видалити. Якщо немає — move on.

Так можна і за один прохід мабуть видалити всі.

Так, це дійсно буде дуже простий алгоритм та ефективний. Але це буде O(n). Рекурсивний алгоритм із мемоізацією результатів підпроблем на великих інпутах буде O(logn) в середньому. У випадку ААААВВВВ то звісно буде лінійна складність.

Не може тут бути лог н — полюбому доведеться перевірити всі символи в рядку хоча б раз.

Якщо я пройшовся по масиву раз це O(n).

Якщо розбив на дерево навпіл, а потім пройшовся по кожному елементу дерева — це все одно O(n) на прохід, плюс час на розбивку. n log n хіба, але не просто log n.

Якщо будемо зберігати результати у хеш мапі після кожного виклику рекурсивного методу, то не доведеться проходити по всіх символах. В цьому ж і суть.
(ABBAABBABBBABABA) — рандомний інпут, але лише із двома літерами для прикладу
(ABBAABBA) (BBBABABA)
(ABBA) (ABBA) (BBBA) (BABA)
(AB)(BA) () (BB)() ()()

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

Щоб перекласти масив в хешмапу це вже O(n)

Якщо економія лише на наступних ітераціях — так я ж пропоную метод в ОДНУ ітерацію.

???

Ми ж не кожну літеру будемо туди перекладати. Але навіть якщо і кожну, їх там чотири всього.
insert — O(1)
find — O(1)

Де 4 всього? Ви з всього інпату робите по суті дерево.

Обходите весь інпат все одно, це O(n).

В інпаті не 4 літери.

Ще раз із прикладом:
пишу, як будуть відбуватись коли
в хеш мапу одразу додаємо значення {
“AB”: “‘,
‘BA’: ‘‘,
і т.д.

ABBAABBABBBABABA

replace(ABBAABBA)
replace(ABBA) -> returned ’’, added ‘ABBA’ to hashmap
replace(AB) -> returned ’”
replace(BA) -> returned ""
replace(ABBA) -> returned “" since “ABBA” already in hashmap
replace(BBBABABA) ->
replace(BBBA) ->
replace(BB) -> return “BB”
replace(BA) -> return “"
replace(BBBA) -> returned “BB”, “BBBA” added to hashmap
replace(BABA) -> “‘, ‘BABA’ added to hashmap
replace(BA) -> ’”
replace(BA) -> ""

що ми бачимо.
повторювані комбінації інпуту не обробляються взагалі, тому що результат вже є. Так, звісно, на якихось унікальних інпутах, де комбінації не будуть повторюватись взагалі, то буде О(n). Але саме average та при збільшенні інпуту, то может бути O(logn).

І вам ще раз — врахуйте що щоб покласти стрічку в хеш мапу треба порахувати хеш стрічки. Який рахується від ВСІХ символів в стрічці. Сама функція хеш-код це O(n) де n — довжина стрінга.

Якщо у вас буде інпат гігабайтної дивжини стрічка, ви поділете навпіл по пів гіга, і будете такі стрічкі як ключі в хеш-мапі використовувати — ви думаєте у вас при цьому не O(n) буде, де n — гігабайт? :D

Один лише хеш код для кожної половини порахувати — це O(n) вже.

А ви ще будете рахувати для четвертин і тд.

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

Неможливо написати хеш функцію яка не буде O(n).

Оце класний жарт. Прямо таки неможливо. Не думаю, що тут можна щось ще обговорювати.

Ви явно не розумієте що пишете.
Як ви зібрались писати хеш який ігнорує дані в стрічці? З дуба рухнули?

Ну уявим що написали, наприклад, хеш функцію яка бере кожнен другий символ тільки. Це все одно О(н) бо константи в великому О ігноруються, О(н/2) не буває.

Але це вже паршива хеш фунція бо не вірдрізняє АБ від АА.

Тож заплатити прийдеться хеш колізіями. І хеш мапа вже не дасть О(1). Вона насправді і не дає — О(1) там це best case.

Це не обійти принципово.

Як не крути, доведеться пройти ВСІ символи в стрічці, це О(н), і цього в принципі в цій задачі уникнути неможливо.

Дивно що хтось цього не розуміє.

Я не казав, що ігнорувати потрібно. Я казав, що можна написати хеш функцію таку, котра буде задовольняти вас по швидкості. Вона може враховувати специфічний інпут, як от лише чотири літери — блок із 4 літер буде займати лише 1 байт. Так само можна враховувати довжину інпуту. Наприклад кількість повних пар в цьому інпуті. І враховувати лише певну кількість блоків літер, якщо ви так переймаєтесь перформансом.
Хеш колізії будуть, звісно. Але вони будуть і з стандартними хеш-функціями і то не є чимось, що аж так сильно впливає на перформанс.
Але (!) враховуючи все це рекурсивний алгоритм все одно буде O(logn) в бест кейс сценаріо — ABABABABABABABABABABA та O(n) в ворст кейс — AAAAAAAAAABBBBBBBBBB.

І з рекурсивним алгоритмом бест кейс сценаріо НЕ буде проходити всі літери — воно навіть і половини літер проходити не буде. Тобто коли ви кажете, що

Як не крути, доведеться пройти ВСІ символи в стрічці, це О(н), і цього в принципі в цій задачі уникнути неможливо.

 то це просто брехня.

Якщо не вмієте в рекурсивні функції, так і скажіть ;)

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

Ні, ви сказали що можна хеш функцію написати, яка буде скейлитись константно. Але це неможливо.

Вона може враховувати специфічний інпут

Це ніяк не міняє суті. Пройти ввід доведеться весь.

враховуючи все це рекурсивний алгоритм все одно буде O(logn) в бест кейс сценаріо

:facepalm:
Ні, не буде.

Ні, ви сказали що можна хеш функцію написати, яка буде скейлитись константно. Але це неможливо.

Та як це неможливо? Ви ж розумієте, що в певних випадках навіть просто перша літера сабстрінги помножена на довжину сабстрінги вже може бути хеш функцією за певних умов? І буде рахуватись константно незалежно від довжини інпуту. А ви кажете неможливо.

Це ніяк не міняє суті. Пройти ввід доведеться весь.

Якби ви знали, що певний інпут складається лише із двох літер, ви б теж його хешували як звичайний стрінг?

Та як це неможливо?

Принципово. Принципово не можливо. В принципі.

Ви ж розумієте, що в певних випадках навіть просто перша літера сабстрінги помножена на довжину сабстрінги вже може бути хеш функцією за певних умов?

Не буду розказувати що size порахувати це вже O(n), просто скажу що це не хеш функція.

Ви можете вигадати якісь умови, де вам ця функція підійде — але ця функція це не хеш функція, це раз, і не підходить до вашого рішення, де ви кожен раз ділете ввід на рівного розімру частинки, це два.

Оці ваші [AD, AB, AC, AA] всі будуть мати те саме значення цієї функції (яку ви помилково називаєте хеш функцією). Це все коллайднеться в хеш мапі, і ви там будете мати O(n) тоді а не O(1).

Ви просто переміщуєте цей O(n) з одного місця в інше, але зникнути він не може — принципово.

Бо вам щоб вирішити задачу НЕОБХІДНО прочитати всі значення в стрінгу, а не половину чи чверть. НЕОБХІДНО — це не можна обійти.

Зрозумійте.

Якщо не вмієте в рекурсивні функції, так і скажіть ;)

Ваша рекурсивна фунція все одно проходить весь інпут.

Там, де вона лізе в хеш мапу — у вас рахується хеш, а хеш рахується від всіх символів стрічки все одно.

Тому у вас О(н) + рекурсія яка log n, тому n*log n. А не просто log n.

Ще раз. В кращому випадку (ABABABABABABABAB) буде O(logn)

replace(ABABABABABABABAB)
replace(ABABABAB)
replace(ABAB)
replace(AB) -> return ""
replace(AB) -> return «"
replace(ABAB) -> return «„. Результат цього інпуту в нас вже є.
replace(ABABABAB) -> return “», тому що ми вже знаємо результат з попереднього колу. Все. Тобто половину інпуту ми навіть не перевіряємо.

Ваш закид про хеш функцію — душна спроба вийти правим.

буде O(logn)

Ні, не буде. Не верзіть дурниць.
Ви кожен раз маєте O(n) на пошук в хеш мапі. Або коли рахуєте хеш, або якщо ви замість хеш фунції повноцінної зробили оцей аналог return 0 — то O(n) буде при колізії в хеш мапі. Він у вас нікуди не подівся.

Ви просто робите вигляд що його немає, «бо хеш мапа дає О(1)». НЕ ДАЄ! Це лише BEST CASE! Але ніхто вам best case не гарантує! Для цього треба нормальний хеш як мінімум, а це вже O(n).

Ви кожен раз маєте O(n) на пошук в хеш мапі. Або коли рахуєте хеш, або якщо ви замість хеш фунції повноцінної зробили оцей аналог return 0 — то O(n) буде при колізії в хеш мапі. Він у вас нікуди не подівся.

Ось це буде ЛИШЕ в найгіршому випадку із неоптимізованою хеш функцією.
Пошук в хешмапі рівний до O(n) буде лише у worst case scenario, коли саме таблиця є ДУЖЕ малою. Але ж ви мене не чуєте. Колізії в таблиці розміром 2 ** 64 будуть за дуже великим виключенням. І це типу вже від вас залежить, чи рахувати хеш із всього інпуту чи ні.

Бтв, то я реально вперше бачу, щоб хтось так сильно відстоював свою точку зору, що put/find в хешмапі — то O(n). Зазвичай то амортизована O(1). Ви на роботі не використовуєте хешмапу через те, що вона повільна?

Ви, вочевидь, не зовсім розумієте як працює хешування(замість цього ви сліпо повторюєте данні з завчених таблиць), але давайте закладемося на 200 евро що ви не напишете алгоритм для цієї задачі що працює швидше за O(n) навіть для найкращого випадку

На гроші я в таке грати не буду. Але я подивлюсь, що можна написати. Якщо то дійсно гон, то ок, my bad :)

питання не в хешмапі і не в хеші як такому. подивіться на задачу під трохи іншим кутом. коли я прошу своїх студентів оцінити складність знизу і є підозра на лінію, то я їм кажу задавати таке питання: чи можете Ви вирішити задачу, не подивившись хоч на один символ рядка чи масиву? бо якщо ні, то складність точно не краща лінійної, просто тому що треба подивитися кожен символ. і не важливо, чи ми їх дивилися щоб рахувати хеш, чи ще з якихось причин, але ми їх дивилися, був доступ до комірки пам’яті. ну от треба перейти на такий мета-рівень: чи можливий алгоритм (не важливо, знаєм ми як то імплементити чи ні, чисто принципово), що подивиться всі символи крім одного і дасть правильну відповідь _для_будь-якого_рядка_? І в даному випадку відповідь — ні. візьміть рядок БАБАБ*БАБАБА. частину точно можна повикидати, ок, залишилось Б*, а далі що? повертати пустий рядок, чи оці два символи?

відстоював свою точку зору, що put/find в хешмапі — то O(n)

?
O(n) у вас не через put/find в хешмапі, а через те що всі ваші дані це і є ключ в хешмапі, відповідно розрахунок хешу це O(n).

Про O(n) в хеш мапі це стосувалось вашої «оптимізованої» так званої «хеш функції» — тої що перший символ на довжину множить. От з таким барахлом замість хеш функції буде у вас той же O(n), тільки на цей раз в іншому місці — в хеш мапі. А з нормальною хеш функцією цього не буде.

Інша справа що нормальна хеш функція для стрінга дає вже O(n), де n — довжина стрінга.

Ви взагалі нічого не розумієте що вам пишуть.

За константний час вона зможе переглянути константу кількість символів -> функція хешування буде жахлива

return 0; Оце і вся «хеш функція» буде.

Потім врахуйте що щоб покласти стрічку в хеш мапу треба порахувати хеш стрічки. Який рахується від ВСІХ символів в стрічці. Сама функція хеш-код це O(n) де n — довжина стрінга.

Чомусь про це часто забувають.

Лінійний час то мінімум, тут лише питання чи можно краще по пам’яті зробити ніж за лінію

Та можна — йти за один прохід, але після видалення метчу зробити backtrack на 1 символ.

Як приклад, AAABBB — після видалення AB повернутись до попереднього A.

Але це все одно лінійна пам’ять. Половину символів ви збережете

Нехай у нас AAAABABA
Це поділиться на [AAAA, BABA] і далі на [AA, AA, BA, BA].

ПО умові мала б бути перше заміна AB, Але тут заміняться останні BA BA, і вийде AAAA

Але якщо б ми послідовно заміняли AB, то лишилось би лише AAA

P.S. А, ще останне A доклеїться.
В принципі результат той самий ніби, але порядок видалень інший. Треба подумати чи немає такого інпату при якому результат відрізнятиметься.

На інпуті ABABA немає різниці, яку комбінацію спершу видаляти. Але так, то звісно не доказ. Сюди потрібен якийсь math geek, котрий зможе довести це математично :)

тут звісно ж worst-case виходить, тому какзати що алгоритм неефективний із-за 1-2 кейсів то таке

Ем, а де аналіз саме продуктивності алгоритмів? Ну там, О(n), оце все

У другій частині будуть і інші варіанти, і аналіз, і benchmarks.

А це не аналіз продуктивності, а аналіз складності. До того ж, а що в даному випадку вважати n, бо тут у задачі насправді кілька змінних. Наприклад, патерн у 2 символи і у 2000 — може дати сильно різний результат. Кількість елементів масиві патернів може вплинути. Чи можуть вони бути різної довжини?

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

Це не «продуктивність» а scalability, масштабованість.

Зазвичай про масштабованість говорять при проектуванні навантажених розподілених систем. У задачках на програмування говорять про часову складність і складність по пам´яті як фунції від розміру вхідних даних.

Так, але це «складності» є мірою того, наскільки алгоритм «масштабується» в залежності від кількості даних.

Згоден, пояснювати можна різними словами. Але є ризик, що неправильно зрозуміють. У мене, наприклад, із словом scalability асоціюється system design interview, а з задачками типу цієї — coding interview, time and space complexity.

Це вже тонкі нюанси.

Головна ідея в тому, що big O notation це не про швидкість (чи кількість пам’яті) як таку — а про те, як вона змінюється із зміною кількості вхідних даних.

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