Category Archive: Алгоритмы

Структура данных PackedPerms

Мотивация

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

Использование JWT-токенов - неплохое решение. Токен может содержать имя пользователя, различные сведения о нем, в т.ч. числе его права и полномочия.

Но есть один неприятный момент. Если в нашей системе очень много прав, например, несколько сотен, то передача кодов прав в токене увеличит размер последнего. Само по себе это некритично, но токен передается в заголовке запроса, который по умолчанию в различных веб-серверах и веб-прокси ограничен от 4К до 8К. Можно, конечно же, увеличить размер заголовка, но все равно разумных ограничений может не хватить, тем более каждый такой запрос будет существенного размера. Далее будет предложен вариант передачи большего кол-ва прав/полномочий в токене.

Реализация

Для начала нужно всем правам (полномочиям) присвоить сквозную нумерацию - 0, 1, 2, и т.д. (необязательно начинать нумерацию с 0, допустимы пропуски в нумерации).

Идея состоит в том, что каждому номеру права будет сопоставлен бит в битовом массиве.

Если право есть, то бит по индексу с номером права будет установлен.

Биты будет конвертировать в строку в формате Base64. Далее эта строка добавляется в токен как значение для поля, например, "permissions".

Один символ в Base64 кодирует 6 битов.

Таким образом, 10 тысяч прав займу примерно 1667 байт.

10 000 бит / 6 = 1667 байт. 

Но это неокончательный размер. Из-за того, что структурные части токена кодируются в Base64, размер возрастет на 4/3 (почему 4/3 можете посмотреть в этом блоге). Итоговый размер 10 тысяч прав, передаваемых как часть токена составит 2.17 КБ.

1667 * 4 / 3 = 2223 байт (2.17 КБ).

Общая схема кодирования:

Исходный код реализации структуры данных можно посмотреть на github.

Упаковка прав/полномочий

Статический метод pack упаковывает идентификаторы прав, которые есть у пользователя в строку в формате Base64.

List<Integer> list = Arrays.asList(2, 4, 7, 8, 9, 10, 12, 14, 15, 
        1000, 2005, 10002, 10007);
String pack = PackedPerms.pack(list);
System.out.println(pack);

Результатом будет строка длинною 1668 символов:

KesAAAAAAA...AAAAAh

Проверка прав/полномочий

Проверка осуществляется статическими методами hasPermission и hasAnyPermission.

hasPermission - проверяет наличие одного полномочия

hasAnyPermission - проверяет наличие хотя бы одного полномочия из списка.

List<Integer> permissionIds = Arrays.asList(16, 4, 101);
String pack = PackedPerms.pack(permissionIds);
System.out.println(PackedPerms.hasPermission(pack, 16)); // true
System.out.println(PackedPerms.hasAnyPermission(pack, 100, 101, 102)); // true

Метод hasPermission отрабатывает за константное время O(1) без выделения дополнительной памяти.

Метод hasAnyPermission отрабатывает за линейное время O(k) без выделения дополнительной памяти.

Где k - кол-во проверяемых прав и обычно оно невелико.

Вот такая довольно простенькая структура данных получилась.

Maven Central Repository

PackedPerms выделен в отдельную библиотеку и доступен в Maven Central Repository:

https://mvnrepository.com/artifact/kz.kesh/packed-perms

Эффективность фильтра Блума в памяти

В предыдущей статье был рассмотрен расчет оптимальных параметров фильтра Блума и его реализация.

Со статьей можно ознакомиться здесь: Фильтр Блума

Для оценки эффективности будем рассматривать сколько оперативной памяти потребляют различные структуры данных в Java 11.

Для примера будем размещать в памяти информацию о 20 миллионах ИИН и делать наблюдения через VisualVM.

ИИН представляет собой строку из 12 символов.

Хранение в ArrayList<String>

Хранение 20 миллионов ИИН в ArrayList:

Создается 20 миллионов объектов String, каждый объект String ссылается на массив байт из 12 элементов.

ЭлементРазмерКол-воОбщий размер
String20 B20 000 000553 MB
byte[12]36 B20 000 000687 MB

Суммарно данный способ занимает в памяти примерно 1240 MБ.

Хранение в HashSet<String>

Хранение 20 миллионов ИИН в HashSet<String>:

Создается 20 миллионов объектов таких же как и для ArrayList, дополнительно хранятся узлы корзины HashMap.Node (под капотом HashSet находится HashMap).

ЭлементРазмерКол-воОбщий размер
String20 B20 000 000553 MB
byte[12]36 B20 000 000687 MB
HashMap.Node44 B20 000 000839 MB

Суммарно данный способ занимает в памяти примерно 2079 MБ.

Хранение в HashSet<Long>

Хранение 20 миллионов ИИН в HashSet<Long>:

Создается 20 миллионов объектов Long и HashMap.Node.

ЭлементРазмерКол-воОбщий размер
Long24 B20 000 000458 MB
HashMap.Node44 B20 000 000839 MB

Суммарно данный способ занимает в памяти примерно 1297 MБ.

Хранение в ArrayList<Long>

Создается 20 миллионов объектов Long.

ЭлементРазмерКол-воОбщий размер
Long24 B20 000 000458 MB

Суммарно данный способ занимает в памяти примерно 458 MБ.

Хранение в long[]

Создается массив из 20 миллионов элементов типа long.

ЭлементРазмерКол-воОбщий размер
long8 B20 000 000152 MB

Суммарно данный способ занимает в памяти примерно 152 MБ.

Хранение в MyBloomFilter

В реализации MyBloomFilter используется BitSet, BitSet в свою очередь хранит биты в виде массива long, поэтому основную память забирает этот массив.

В нашей реализации BitSet хранит информацию о 268 435 456 битах.

В один long помещается 64 бит.

268 435 456 / 64 = 4 194 304 (кол-во элементов в массиве)

Практически нет дополнительных потерь при хранении байтов (24 байта транится на сам массив).

268 435 456 бит / 8 = 33 554 432 байт

Суммарно данный способ занимает в памяти примерно 32 MБ.

Хранение в GoogleBloomFilter

Как было рассмотрено в предыдущей статье о фильтре Блума, необходимо рассчитать оптимальное кол-во бит для хранения.

Для 20 миллионов ИИН с вероятностью ошибок 1% оптимальное кол-во бит составляет 191 701 168.

BloomFilter из набора guava для хранения бит использует AtomicLongArray, который в свою очередь использует для хранения бит также long массив (long[]).

Рассчитаем кол-во элементов в массиве:

⌈191 701 168 / 64⌉  = ⌈2 995 330.75⌉ =  2 995 331

Теперь рассчитаем размер в байтах:

191 701 168 бит / 8 = 23 962 646 байт

Суммарно данный способ занимает в памяти примерно 23 MБ.

Итоговая сравнительная таблица

Структура данныхПотребляемая памятьПримечание
HashSet<String>2079 MБОптимальные операции добавления и поиска, но высокое потребление памяти
HashSet<Long>1297 MБДополнительная работа с Long, из-за наличия у ИИН ведущих нулей
ArrayList<String>1240 MБСписок должен быть отсортирован, что была возможность поиска
ArrayList<Long>458 MБСписок должен быть отсортирован. Дополнительная работа с Long, из-за наличия у ИИН ведущих нулей.
long[]152 MБФиксированный размер.
MyBloomFilter32 MБНеоптимальная реализация
Bloom Filter (Google Guava)23 MБОптимальная реализация

Заключение

В данной статье было рассмотрено несколько вариантов хранения информации о 20 миллионах ИИН, где вместо 1-2 гигабайт, можно обойтись 20-30 мегабайтами (экономия на порядок) при допущении заданной вероятности ошибок.

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

Фильтр Блума имеет достаточно специфические варианты использования, и есть небольшая вероятность, что он вам пригодится.

Фильтр Блума на Java

Давно хотелось попробовать реализовать фильтр Блума (хотя я его называют фильтром Блюма).

Фильтр Блума - это вероятностная структура данных, позволяющая проверить принадлежность элемента к множеству. Данная структура может точно ответить на запрос об отсутствии элемента в множестве, но может ошибаться с заданной нами вероятностью о наличии элемента во множестве.

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

Фильтр Блума может использоваться, например, для подсчета уникальных посетителей, для проверки орфографии, в различных СУБД для уменьшения обращения к ПЗУ (постоянное запоминающее устройство).

Будем пробовать фильтр Блума на примере хранения 20 миллионов ИИНов.

ИИН - индивидуальный идентификационный номер физического лица в Республике Казахстан, состоящий из 12 цифр.

Я заранее сгенерировал список из 20 миллионов ИИНов (102 MB).

Скачать список можно здесь: https://drive.google.com/file/d/1SIfp_CRl4cQetc3Kw2jqDcWpF3fYPc2s/view?usp=sharing

Исходные коды генератора можно посмотреть в github: https://github.com/Nyquest/iin_generator

Фильтр Блума должен преобразовать наше множество из 20 миллионов ИИН в набор битов с помощью нескольких хэш-функций.

ИИН считается принадлежащим множеству, если значения всех вычисленных хэш-функции от ИИНа указывают на номера отмеченных бит. Если хотя бы один бит не отмечен, ИИН однозначно не принадлежит множеству.

Формулы

Оптимальное количество бит и достаточное кол-во хэш-функций можно рассчитать по формулам.

Формула оптимального количества бит:

    \[    \displaystyle m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}} \]

m - искомый размер битового массива (кол-во бит);

n - размер исходного множества;

ln - функция натурального логарифма;

ε - желаемая вероятность ошибок (например, 0.01 - ожидаем 1% ошибок)

Формула достаточного кол-ва кэш-функций зависит от выделенного кол-ва бит:

    \[    \displaystyle k={\frac {m}{n}}\ln 2 \]

k - кол-во кэш-функций;

m - кол-во битов в результирующем массиве;

n - кол-во элементов в исходном множестве;

ln - функция натурального логарифма.

Результатом выполнения каждой кэш-функции является номер бита, который нужно выставить (отметить). Таким образом, несколько хэш-функции высталяют различные биты в массиве бит. Хотя номера могут случайно совпадать для различных хэш-функций. Независимость хэш-функции друг от друга позволяет уменьшить повторяемость их результатов.

Реализация формул на Java

Самой главной проблемой при реализации фильтра Блума является выбор хэш-функций.

Первое, что пришло в голову это брать SHA-256 (привет любителям блокчейна) от ИИНа, и части SHA-256 использовать как отдельные значения хэш-функций.

Но, на самом деле, SHA-256 недостаточно, поэтому был взят SHA-384.

Чтобы было удобнее брать части SHA-384 делается выравнивание размера битового массива.

Как и требуется, хэши SHA обладают лавинным эффектом, небольшое изменений в хэшируемых данных меняет хэш до неузнаваемости.

Общая схема работы

Функция расчета оптимального кол-во бит

/**
 * Вычислить оптимальное кол-во бит
 * @param totalCount общее кол-во элементов
 * @param errorProbability вероятность ошибок
 * @return оптимальное кол-во бит
 */
static long optimalBitCount(long totalCount, double errorProbability) {
    return (long) Math.ceil(
            -totalCount * Math.log(errorProbability) / Math.pow(Math.log(2), 2));
}

Подставим наши значения (20 миллионов - кол-во элементов, 0.01 - ожидаем 1% ошибок) и получим размер битового массива, равный 191 701 168:

System.out.println(optimalBitCount(20_000_000, 0.01)); // 191_701_168

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

Это можно увидеть, переведя размер 191 701 168 в двоичный вид 1011011011010010000010110000:

System.out.println(Long.toBinaryString(optimalBitCount(20_000_000, 0.01)));

Чтобы задействовать возможные биты, нужно сделать расчет размера с выравниванием:

/**
 * Вычислить оптимальное кол-во бит с выравниванием
 * @param totalCount общее кол-во элементов
 * @param errorProbability вероятность ошибок
 * @return оптимальное кол-во бит в порции с выравниванием
 */
static long optimalBitCountWithAlignment(long totalCount, double errorProbability) {
    long result = optimalBitCount(totalCount, errorProbability);
    long l = Long.highestOneBit(result);
    return l == totalCount ? totalCount : l << 1;
}

Еще раз подставим наши значения, получим размер, равный 268 435 456

System.out.println(optimalBitCountWithAlignment(20_000_000, 0.01)); // 268_435_456

Переведем 268 435 456 - 1 в двойчный вид 1111111111111111111111111111 (28 бит).

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

System.out.println(Long.toBinaryString(
                optimalBitCountWithAlignment(20_000_000, 0.01) - 1));

Размер стал больше, но зато все биты задействованы.

Таким образом, считаем размер битового массива равным 268 435 456.

Функция расчета кол-ва хэш-функций:

/**
 * Расчет кол-ва хэш-функций
 * @param totalCount общее кол-во элементов
 * @param bitArraySize размер битового массив
 * @return минимальное кол-во хэш-функций
 */
static long hashFunctionCount(long totalCount, long bitArraySize) {
    return (long) Math.ceil(Math.log(2) * ((double)bitArraySize / totalCount));
}

Подставим наши значения, получим 10 хэш-функций:

System.out.println(hashFunctionCount(20_000_000, 268_435_456)); // 10

268 435 456 значений можно закодировать 28 битами, что составляет 3.5 байта.

    \[    \displaystyle 2^{28} = 268 435 456 \]

Для удобства мы можем брать по 4 байта хэш-функции SHA, при этом 3 байта целиком, а один только на половину, другую же половину просто игнорируем.

Итого там потребуется 40 байт, которые есть в SHA-384.

Хэш-функцияКол-во битКол-во байт
SHA-25625632
SHA-38438448

Из SHA-384 можно получить не 10, а 12 функций. Чем больше функций, тем меньше будет ошибок.

Реализация фильтра Блума на Java

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

Для начала реализуем получение хэша от строки (ИИНа) в виде массива байт.

MessageDigest digest = MessageDigest.getInstance("SHA-384");
byte[] digest(String value) {
    return this.digest.digest(value.getBytes(StandardCharsets.UTF_8));
}

Биты будем хранить в стандартной структуре данных BitSet. У данный структуры есть методы set и get для установки и чтения значения соответствующего бита.

BitSet bitSet = new BitSet(1 << 28); // размер BitSet, равный 268_435_456

Реализуем функцию перевода четырех байт в число, являющееся номером позиции бита в BitSet.

/**
 * переводим четыре байта в число
 * @param digest массив байт
 * @param position позиция, от которой берутся 4 байта
 * @return число
 */
private int bitsToInt(byte[] digest, int position) {
    return ((((1 << 4) - 1)) & digest[position]) << 24 // берем половину байта и смещаем его на 24 позиции влево
            | (0xff & digest[position + 1]) << 16 // берем следующий целый байт и смещаем его на 16 позиций влево
            | (0xff & digest[position + 2]) << 8 // берем следующий целый байт и смещаем его на 8 позиций влево 
            | (0xff & digest[position + 3]); // берем следующий целый байт без каких-либо смещений
}

Функция установки битов выглядит следующим образом:

private void saveBits(String value) {
    byte[] digest = digest(value);
    for (int i = 0; i + 3 < digest.length; i += 4) {
        bitSet.set(bitsToInt(digest, i));
    }
}

Функция проверки принадлежности значения множеству:

private boolean checkBits(String value) {
    byte[] digest = digest(value);
    for (int i = 0; i + 3 < digest.length; i += 4) {
        if(!bitSet.get(bitsToInt(digest, i))) {
            return false;
        }
    }
    return true;
}

Тестирование фильтра Блума

Пример применения фильтра Блума на 20 миллионах ИИН https://github.com/Nyquest/bloom_filter

Проверять фильтр Блума будем следующим образом:

  1. Загрузим ИИНы в HashSet;
  2. Загрузим ИИНы в фильтр Блума;
  3. Сгенерим 10 миллионов случайных ИИН и прогоним их через фильтр Блума;
  4. Если фильтр показывает, что ИИН не относится к множеству, но этот ИИН есть в HashSet, то выбрасываем исключение и останавливаем программу;
  5. Если фильтр показывает, что ИИН относится к множеству, но его нет в HashSet, учитываем данный факт как ложноположительное срабатывание;
  6. Подсчитываем ложноположительные срабатывания и их в процент от общего числа запросов.

В примере две реализации: собственная MyBloomFilter и GoogleBloomFilter(BloomFilter из guava).

При создании GoogleBloomFilter указывается вероятность ошибок, которая подтверждается эмпирическим путем.

Но так как наш фильтр модифицирован дважды, эмпирические данные показывают ошибки в 0.18% от всех тестовых запросов:

  1. Набор бит увеличен из-за выравнивания
  2. Взято больше хэш-функций (12 вместо 10)

Теперь рассчитаем ожидаемую вероятность ошибок по формуле:

    \[    \displaystyle (1-e^{-kn/m})^{k} \]

Функция расчета вероятности ошибок на Java

/**
 * Расчет вероятности ошибок
 * @param totalCount общее кол-во элементов
 * @param bitArraySize размер битового массив
 * @param hashFunctionCount кол-во хэш-функций
 * @return вероятность ошибок
 */
public static double errorProbability(long totalCount, long bitArraySize, long hashFunctionCount) {
    return Math.pow(1 - Math.pow(Math.E, 
            -(double)hashFunctionCount * totalCount / bitArraySize), hashFunctionCount);
}
}

Подставим наши значения и получим 0.0018, т.е. теоретические и практические результаты совпали.

System.out.println(errorProbability(20_000_000, 268_435_456, 12));

Заключение

Получилась рабочая версия фильтра Блума, но с рядом недостатков.

Сравнивать будет с реализацией от Google, хотя почему-то в guava Bloom Filter еще в beta-тестировании.

Сравнение, конечно же, не в нашу пользу.

  1. Потребляет больше оперативной памяти из-за выравнивания;
  2. Непараметризирован. Размер битового массива фиксирован под определенную задачу.
  3. Сильная завязка на выравнивание.
  4. Реализация медленнее. С тестовым заданием фильтр в последовательном режиме справляется за 11 секунд, а GoogleBloomFilter за 5 секунд.
  5. Сама реализация как и BitSet без потоковой безопасности (thread-safety), в отличие от Guava Bloom Filter.

В реальных проектах лучше использовать готовые реализации Bloom Filter с потоковой безопасностью.

Основная цель своей реализации была лучше разобраться в этой интересной, вероятностной и магической структуре данных.

В реализации Google используется магия и трюки (см. фрагмент кода BloomFilterStrategies.java по добавлению элемента в множество):

@Override
public <T extends @Nullable Object> boolean put(
    @ParametricNullness T object,
    Funnel<? super T> funnel,
    int numHashFunctions,
    LockFreeBitArray bits) {
  long bitSize = bits.bitSize();
  long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
  int hash1 = (int) hash64;
  int hash2 = (int) (hash64 >>> 32);
 
  boolean bitsChanged = false;
  for (int i = 1; i <= numHashFunctions; i++) {
    int combinedHash = hash1 + (i * hash2);
    // Flip all the bits if it's negative (guaranteed positive number)
    if (combinedHash < 0) {
      combinedHash = ~combinedHash;
    }
    bitsChanged |= bits.set(combinedHash % bitSize);
  }
  return bitsChanged;
}

Здесь один хэш получается из предыдущего. Если в вычислениях случается переполнение, в результате которого образумется отрицательное число, то происходит инверсия бит, чтобы получилось положительное число за счет смены бита, отвечающего за знак в том числе. Чтобы не выходить за пределы битового массива делается закольцовывание с помощью взятия остатка от деления на размер массива.

В следующем блоге смотрите эффективность фильтра Блума с точки зрения расхода памяти: Эффективность фильтра Блума в памяти

Преобразование в сетевой порядок расположения байт (Java)

HtoN (Host to Net) - узловой порядок в сетевой.

Функция htons преобразует узловой порядок расположения байтов в сетевой порядок расположения байтов. В short помещаются все возможные порты от 0 до 65535 (фактически от -32768 до 32767, т.к. в Java знаковый short):

static short htons(short val) {
    return (short) ((val & 0xff) << 8 
            | (val & 0xff00) >>> 8); // >>> - беззнаковый сдвиг
}

Функция htonl() преобразует узловой порядок расположения байтов в сетевой порядок расположения байтов. В int помещаются все возможные адреса IPv4 от 0.0.0.0 до 255.255.255.255 (фактически от -2 147 483 648 до 2 147 483 647, т.к. в Java знаковый int):

static int htonl(int val) {
    return (val & 0xff) << 24
            | (val & 0xff00) << 8
            | (val & 0xff0000) >> 8
            | (val & 0xff000000) >>> 24; // >>> - беззнаковый сдвиг
}
TAG: ,

Алгоритм Ахо-Корасик на Java

Пример реализации алгоритма Ахо-Корасика на Java.

При реализации использовался следующий материал:

  1. https://e-maxx.ru/algo/aho_corasick
  2. https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE-%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA

Данный алгоритм был опробован на задаче: https://www.hackerrank.com/challenges/determining-dna-health/problem

Пример использования:

List<AhoCorasick.Entry> entryList = new ArrayList<>();
 
List<String> list = Arrays.asList("b", "c", "aa", "d", "b");
 
for (String s : list) {
    AhoCorasick.Entry entry = new AhoCorasick.Entry();
    entry.setValue(s);
    entryList.add(entry);
}
 
 
AhoCorasick ahoCorasick = new AhoCorasick(entryList, 26);
 
ahoCorasick.solve("caaab");

Сама реализация алгоритма:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
/**
 * Реализация алгоритма Ахо-Корасика
 */
public class AhoCorasick {
 
    private List<Entry> entryList;
    private int alphabetSize;
    private List<Vertex> vertexList;
    private int vertexCount;
 
    public AhoCorasick(List<Entry> entryList, int alphabetSize) {
        this.entryList = entryList;
        this.alphabetSize = alphabetSize;
    }
 
    // Строка набора
    public static class Entry {
        private String value;
 
        public String getValue() {
            return value;
        }
 
        public void setValue(String value) {
            this.value = value;
        }
 
        @Override
        public String toString() {
            return "Entry{" +
                    "value='" + value + '\'' +
                    '}';
        }
    }
 
    // Вершина бора (состояние конечного детерминированного автомата)
    public static class Vertex {
        private int next[];         // массив сыновей
        private boolean isLeaf;     // терминальная вершина
        private int parent;         // родительская вершина
        private int charIndexFromParent;// символ перехода от родителя
        private int suffixLink;     // суффиксная ссылка
        private int go[];           // массив переходов, используемый для вычисления суффиксных ссылок
 
        public Vertex(int alphabetSize) {
            this.next = newIntArray(alphabetSize);
            this.go = newIntArray(alphabetSize);
            this.parent = -1;
            this.suffixLink = -1;
        }
 
        private int[] newIntArray(int size) {
            int[] ints = new int[size];
            Arrays.fill(ints, -1);
            return ints;
        }
 
        @Override
        public String toString() {
            return "Vertex{" +
                    "next=" + Arrays.toString(next) +
                    ", go=" + Arrays.toString(go) +
                    ", isLeaf=" + isLeaf +
                    '}';
        }
    }
 
    public List<Entry> getEntryList() {
        return entryList;
    }
 
    // добавить строку в набор
    public boolean addEntry(Entry entry) {
        return entryList.add(entry);
    }
 
    // поиск всех строк из заданного набора в тексте
    public void solve(String text) {
        vertexList = new ArrayList<>();
        vertexList.add(new Vertex(alphabetSize));
        vertexList.add(new Vertex(alphabetSize));
        vertexCount = 1;
 
        for (Entry entry : entryList) {
            addToTrie(entry);
        }
 
        int v = 0;
        for (char ch : text.toCharArray()) {
            v = go(v, charToIndex(ch));
            Vertex vertex = vertexList.get(v);
            if(vertex.isLeaf) { // посещение терминальной вершине - это нахождение строки из заданного набора
                System.out.println(v + " " + vertex);
            }
        }
 
    }
 
    // добавить в бор
    private void addToTrie(Entry entry) {
        int v = 0;
        for (char ch : entry.value.toCharArray()) {
            int sym = charToIndex(ch);
            if(vertexList.get(v).next[sym] == -1) {
                Vertex vertex = vertexList.get(vertexCount);
                vertex.suffixLink = -1;
                vertex.parent = v;
                vertex.charIndexFromParent = sym;
 
                vertexList.add(new Vertex(alphabetSize));
                vertexList.get(v).next[sym] = vertexCount++;
            }
            v = vertexList.get(v).next[sym];
        }
        vertexList.get(v).isLeaf = true;
    }
 
    private int charToIndex(char ch) {
        return ch - 'a';
    }
 
    // обычный переход
    private int go(int v, int sym) {
        Vertex vertex = vertexList.get(v);
        if(vertex.go[sym] == -1) {
            if(vertex.next[sym] != -1) {
                vertex.go[sym] = vertex.next[sym];
            } else {
                vertex.go[sym] = v == 0 ? 0 : go(goBySuffixLink(v), sym);
            }
        }
        return vertex.go[sym];
    }
 
    // переход по суффиксной ссылке (к вершине, в которой оканчивается наидлиннейший собственный суффикс строки)
    private int goBySuffixLink(int v) {
        Vertex vertex = vertexList.get(v);
        if(vertex.suffixLink == -1) {
            if(v == 0 || vertex.parent == 0) {
                vertex.suffixLink = 0;
            } else {
                vertex.suffixLink = go(goBySuffixLink(vertex.parent), vertex.charIndexFromParent);
            }
        }
        return vertex.suffixLink;
    }
 
}

Суффиксный массив на Java за N*log^2(N)

public static int[] getSuffixArray(String s) {
 
    System.out.println(s);
 
    int N = s.length();
 
    int steps = Integer.bitCount(Integer.highestOneBit(N) - 1);
 
    int rank[][] = new int[steps + 1][N];
 
    for (int i = 0; i &lt; N; i++) {
        rank[0][i] = s.charAt(i) - 'a';
    }
 
    Tuple tuples[] = new Tuple[N];
 
    for (int step = 1, cnt = 1; step &lt;= steps; step++, cnt &lt;&lt;= 1) {
        for (int i = 0; i &lt; N; i++) {
            Tuple tuple = new Tuple();
            tuple.firstHalf = rank[step - 1][i];
            tuple.secondHalf = i + cnt &lt; N ? rank[step - 1][i + cnt] : -1;
            tuple.originalIndex = i;
 
            tuples[i] = tuple;
        }
 
        Arrays.sort(tuples);
 
        rank[step][tuples[0].originalIndex] = 0;
 
        for (int i = 1, currRank = 0; i &lt; N; i++) {
            if(!tuples[i - 1].firstHalf.equals(tuples[i].firstHalf)
                    || tuples[i - 1].secondHalf.equals(tuples[i].secondHalf)) {
                ++currRank;
            }
            rank[step][tuples[i].originalIndex] = currRank;
        }
 
 
    }
 
    int suffixArray[] = new int[N];
 
    for (int i = 0; i &lt; N; i++) {
        suffixArray[i] = tuples[i].originalIndex;
    }
 
    return suffixArray;
}
 
static class Tuple implements Comparable<tuple> {
    Integer originalIndex;  // хранит оригинальный индекс суффикса
    Integer firstHalf;      // хранит ранг первой половины суффикса
    Integer secondHalf;     // хранит ранг второй половины суффикса
 
 
    @Override
    public int compareTo(Tuple tuple) {
        return this.firstHalf.equals(tuple.firstHalf)
                ? this.secondHalf.compareTo(tuple.secondHalf)
                : this.firstHalf.compareTo(tuple.firstHalf);
    }
 
    @Override
    public String toString() {
        return "Tuple{" +
                "originalIndex=" + originalIndex +
                ", firstHalf=" + firstHalf +
                ", secondHalf=" + secondHalf +
                '}';
    }
}
 
</tuple>

Удаление числа из строки

Иногда мы пользуемся трюком, сохраняя числа (ID из базы данных) в строке через запятую. Например: "1024,15,8,0,55". И теперь, допустим, какое-то число из этого списка не нужно, и его необходимо убрать из исходной строки. Как это реализовать? Первый вариант: 1) разбить строку по запятой 2) отфильтровать удаляемое число 3) собрать строку заново Второй вариант (допустим, удаляем число 55): 1) вырезать из строки подстроки вида: ,55, 2) удаляем подстроки вида 55, и ,55 Реализация 1-го варианта (Java):
String val = "55";
String collect = Arrays.stream(
        "55,1024,55,15,8,0,55".split(","))
        .filter(v -> !v.equals(val))
        .collect(Collectors.joining(","));
System.out.println(collect);//1024,15,8,0
Реализация 2-го варианта (Java):
int del = 55;
String result = "55,1024,55,15,8,0,55"
        .replaceAll("," + del + ",", ",")
        .replaceAll(",?" + del + ",?", "");
System.out.println(result);//1024,15,8,0

Как искать ошибку в программе?

Список подсказок, как найти ошибку:
  1. Проверить, там ли вы ищите/смотрите ошибку. Например, вы могли подключиться не к тому серверу или базе.
  2. Вспомнить и посмотреть, что недавно менялось.
  3. Попросить коллегу посмотреть на проблему незамыленным взглядом
  4. Отстраниться от проблемы. Например, переключиться на другую сферу деятельности, проблему или просто отдохнуть
  5. Внимательно посмотреть сообщение об ошибке, может там уже указана точная причина ошибки или хотя бы указатель на нее
  6. Поискать способ (если возможно) просмотра детализованного лога
  7. Вернуться к первому пункту 🙂

Циклический сдвиг по кругу

Рассмотрим, линейный массив: line По нему мы можем передвигаться вперед и назад, но не выходя за левую и правую границы. Данный массив можно закольцевать. Допустим, у нас есть массив, состоящий из элементов пронумерованных следующим образом: 0 1 2 3 4, мы находимся в позиции с индексом 3 и нам нужно сместиться на три позиции вправо. Наши действия:
  1. Перемещаемся вправо на 4-ю позицию;
  2. Пытаемся переместиться вправо на 5-ю позиции, но ее - нет. Перескакиваем на началом массива в 0-ю позицию;
  3. Перемещаемся вправо на 1-ю позицию. В итоге мы оказались на 1-й позиции.
Теперь рассмотрим обратную ситуацию. Мы в позиции с индекcом 1 и нужно сместиться на три позиции влево:
  1. Перемещаеся влево на 0-ю позицию;
  2. Пытаемся переместиться влево на -1-ю позицию, которой нет, поэтому перемещаемся в конец массива на позицию с индексом 4.
  3. Перемещаемся влево на 3-ю позицию. В итоге оказываемся на 3-й позиции.
circle Реализация смещения вправо:
int[] arr = new int[]{10, 20, 30, 40, 50};
int index = 3;
System.out.println("index = " + index);//Вывод: 3
System.out.println("value = " + arr[index]);//Вывод: 40
int step = 3;
int newIndex = (index + step) % arr.length;
System.out.println("newIndex = " + newIndex);//Вывод: 1
System.out.println("value = " + arr[newIndex]);//Вывод: 20
Реализация смещения влево:
int[] arr = new int[]{10, 20, 30, 40, 50};
int index = 1;
System.out.println("index = " + index);//Вывод: 1
System.out.println("value = " + arr[index]);//Вывод: 20
int step = 13;
int newIndex = (arr.length + (index - step) % arr.length) % arr.length;
System.out.println("newIndex = " + newIndex);//Вывод: 3
System.out.println("value = " + arr[newIndex]);//Вывод: 40
Зацикливание массива реализовано с помощью операции взятия остатка от деления %, это позволяет исключить полностью завершенные циклы.

Вложенный тернарный поиск с золотым сечением

Определение тернарного поиска можно найти в Википедии. Также описание алгоритма можно найти здесь. Реализация у тернарного поиска несложная, давайте убедимся в этом на примере следующей задачи:
triangle_find_alpha Имеется прямоугольный треугольник, у которого гипотенуза равна 100 сантиметрам. Нужно вычислить при каком угле α площадь треугольника будет максимальна.
Хотя данную задачу можно решать другими способами, но для учебных целей решим ее тернарным поиском. Для начала нужно убедиться, что эту задачу вообще можно решить тернарным поиском. Убедимся в унимодальности нашей функции, т.е. на заданном интервале у функции должен быть один экстремум (максимальное или минимальное значение функции на заданном интервале). Мы будем перебирать углы от 0° до 90°, т.е. наш интервал поиска от 0 до 90. При возрастании угла, начиная от 0°, площадь треугольника строго возрастает, затем при приближении к углу 90° площадь треугольнига строго уменьшается, т.е. у нас есть максимальное значение функции на данном интервале, а значит выполняется унимодальность функции, и мы можем применить тернарный поиск. Как работает тернарный поиск. Сначала интервал разбивается на три части, отсюда и название "тернарный" (Ternary переводится как тройной или троичный). На следующем шаге отсеивается участок, в котором точно нет решения, затем снова отрезок разбивается на три части, и это повторяется до тех пор, пока не будет достугнута необходимая точность результата. Классический способ разбиения - это разбиение на три равные части части: ternary_equal Фрагмент кода, обеспечивающий равенство отрезков Lm1 = m1m2 = m2R:
double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;
При сравнении значений функций в точках m1 и m2 у нас возможно три варианта: 1) Мы сдвигаем область поиска вправо, т.е. l становится равным m1 (l = m1); 2) Мы сдвигаем область поиска влево, т.е. r становится равным m2 (r = m2); 3) При равенстве значений функции в обеих точках, мы сдвигаем область поиска с обеих сторон, т.е. l становиться равным m1 (l = m1), а r становиться равным m2 (r = m2) Рассмотрим данные случаи на примере поиска максимального значения. 1) Если f(m1) < f(m2), возможно два случая: когда максимальное значение лежит в центральной части или в правой части, а значит левую часть можно отбросить. Максимальное значение обозначено зеленой точкой. ternary_max_large 2) Если f(m1) > f(m2), аналогично имеется только два случая, когда максимальное значение лежит в центральной или левой части, а значит правую часть можно отбросить. ternary_max_less 3) Если f(m1) = f(m2), то возможен только один вариант, при котором максимальное значение находится в центральной части, а значит левую и правую части можно отбросить. ternary_max_equal Последний вариант, когда f(m1) = f(m2), в целях облегчения алгоритма можно заменить либо на этот случай f(m1) < f(m2), либо на этот f(m1) > f(m2). В скорости из-за этого, конечно же, мы чуть-чуть проиграем, но выиграем в скорости реализации алгоритма и компактности кода. После каждого шага алгоритма от исходной области поиска остается 2/3, т.е. не самая большая скорость сходимости. Можно повысить скорость сходимости, если выбирать точки m1 и m2 ближе друг другу, правда при этом теряется точность. Повышение скорости сходимости может потребоваться в случае, когда вычисление функции f(x) занимает много времени и нужно минимизировать кол-во вызовов этой функции. Очень хорошо при выборе точек m1 и m2 воспользоваться пропорциями золотого сечения. Если тернарный поиск использует пропорции золотого сечения, то это один в один Метод золотого сечения.
Золотое сечение - это такое разбиение целого на две части, при котором отношение большего к меньшему равно отношению целого к большему
Это отношение постоянно и равно примерно 1,618, обозначается как φ и называется золотым числом: phi Для вычисления точек m1 и m2, разбивающих область поиска золотым сечением, воспользуемся следующими формулами: m1_phi m2_phi В процентном соотношении длины отрезков lm1 и lm2 приблизительно равны 38,2% и 61,8% от длины отрезка lr. Благодаря свойствам золотого сечения точка m1 делит отрезок lm2 в пропорциях золотого сечения, а точка m2 делит отрезок m1r также в пропорциях золотого сечения. golden_section_search И так мы видим, что сходимость золотого сечения будет 0,618, что лучше сходимости в случае разбиения области поиска на равные части, где сходимость у нас была 2/3 (0,66). А теперь вернемся к решению задачи... Исходный код решения задачи на Java:
import static java.lang.Math.*;
 
public class angle {
 
	public static void main(String[] args) {
		double l = 0;
		double r = 90;
		double EPS = 1e-6;//точность 0.000001
		double hypo = 100;//гипотенуза
		while(r - l >= EPS){//повторяем цикл пока не достигнем требуемой точности
			double m1 = l + (r - l) / 3;
			double m2 = r - (r - l) / 3;
			if(f(hypo,m1) < f(hypo,m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
		System.out.println((l + r) / 2);//результат 44.99999993498489
	}
 
	//функция расчета площади треугольника по гипотенузе и углу
	static double f(double hypo,double alpha){
		alpha = toRadians(alpha);
		return 0.5 * hypo * hypo * cos(alpha) * sin(alpha);
	}
 
}
Т.е. при угле в 44.999999° (45°) достигается максимальная площадь треугольника. В качестве ответа можно было взять значение из переменной l или r, это возможно благодаря достижению заданной точности результата, также можно взять их середину (l + r) / 2, как в рассмотренном выше коде. Задача на вложенный тернарный поиск В качестве примера применения вложенного тернарного поиска возьмем задачу "Футбольные ворота". С условием задачи можно ознакомиться здесь или здесь. Найти максимальную площадь ворот можно, подобрав углы для палок α и β: football_gate Сперва мы находим углы α1 и α2, которые разбивают область поиска на три равные части (в данной задачи можно не использовать золотое сечение). Далее для угла α1 с помощью вложенного тернарного поиска ищем угол β1, при котором площадь фигуры максимальна, аналогично, для угла α2 находим подходящий угол β2. alpha_beta Найдя пары углов α1 и β1; α2 и β2, вычисляем площадь S1 и S2 соответственно. Можно использовать следующую формулу вычисления площади, где a и b - длины палок:
S = 0.5 * a * a * cos(alpha) * sin(alpha) +
0.5 * b * b * cos(beta) * sin(beta) +
a * b * sin(alpha) * cos(beta)
Сравнив полученные площади, мы можем отсеять треть диапазона углов, которые дают маленькую площадь. И повторяем эти шаги до тех пор, пока не достигнем требуемой точности. Код решения задачи на Java:
import java.io.*;
 
import static java.lang.Math.*;
 
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.util.*;
public class FooballGate {
 
	static int a;//длина 1-ой палки
	static int b;//длина 2-ой палки
	static double EPS = 1e-6;//точность результата
 
	public static void main(String[] args) throws IOException {
		Scanner s = new Scanner(new File("input.txt"));
		s.useLocale(Locale.US);		
		a = s.nextInt();
		b = s.nextInt();
		s.close();
 
		double l = 0;
		double r = 90;
 
		while(r - l >= EPS){
			double m1 = l + (r - l) / 3;
			double m2 = r - (r - l) / 3;
			if(f(m1) < f(m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
 
		double ans = f((l + r) / 2);//результат		
		DecimalFormat df = new DecimalFormat("0.00000000",
				DecimalFormatSymbols.getInstance(Locale.US));
		System.out.println(df.format(ans));//вывод с восемью знаками после запятой
 
	}
 
 
	//функция расчета площади с фиксированным углом alpha,
	//в которой тернарным поиском идет поиск угла beta,
	//при котором площадь максимальна
	static double f(double alpha){
		double l = 0;
		double r = 90;
		while(r - l >= EPS){
			double m1 = l + (r - l) / 3;
			double m2 = r - (r - l) / 3;
			if(f(alpha,l) < f(alpha,r)){
				l = m1;
			}else{
				r = m2;
			}
		}	
		return f(alpha,(l + r) / 2);
	}
 
	//функция расчета площади в зависимости от углов: alpha и beta 
	static double f(double alpha, double beta){
		alpha = toRadians(alpha);
		beta = toRadians(beta);
		return 0.5 * a * a * cos(alpha) * sin(alpha) +
				0.5 * b * b * cos(beta) * sin(beta) +
				a * b * sin(alpha) * cos(beta);
	}
}
Задача на тройную вложенность тернарного поиска с необходимостью применения золотого сечения Задача называется "Космические спасатели". Ознакомиться с условием задачи можно здесь или здесь. planets По условию задачи нам нужно вычислить координаты x,y,z строительства новой спасательной станции, причем расстояние от станции до самой дальней планеты должно быть минимально. Сперва пробуем подобрать координату x тернарным поиском, но координаты y и z - неизвестны, поэтому зафиксировав некоторые точки x, полученные золотым сечением, мы запускаем вложенные тернарный поиск с фиксированной координатой x для поиска координаты y. Далее внутри поиска y запускаем вложенный тернарный поиск координаты z. Когда мы имеем все три зафиксированные координаты мы можем посчитать расстояния до всех планет и из них определить максимальное расстояние, это расстояние и будет значением функции f(x,y,z). Т.к. в условии сказано, что количество планет может быть 100, то вычисление функции f(x,y,z) очень затратно по времени. Чтобы программа уложилась во временные рамки, нужно при тернарном поиске разбивать область поиска золотым сечением, а не на равные части. Тем самым у нас повыситься сходимость, т.е. вызовов функции f(x,y,z) станет меньше. Но при золотом сечении теряется точность, поэтому мы увеличим точность с 10-6 до 10-7. Реализация на Java:
import java.io.*;
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.util.*;
public class SpaceRescuers {
	static int MAX = (int) 1e4;//максимальная граница поиска
	static int MIN = -MAX;//минимальная граница поиска
	static class Point{
		int x;
		int y;
		int z;
		public Point(int x, int y, int z) {
			super();
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}
 
	static class PointD{
		double x;
		double y;
		double z;
		public PointD(double x, double y, double z) {
			super();
			this.x = x;
			this.y = y;
			this.z = z;
		}
 
	}
 
	static Point[] points;
	static double EPS = 1e-7;
	static PointD bestPoint;//лучшая точка
	static double best = Double.MAX_VALUE;//лучшее расстояние (минимальное)
	static double fi = 1 / ((Math.sqrt(5) + 1) / 2);
 
	public static void main(String[] args) throws IOException {
		Scanner s = new Scanner(new File("input.txt"));
		s.useLocale(Locale.US);
		int N = s.nextInt();
		points = new Point[N];
		for(int i = 0; i < N; i++){
			points[i] = new Point(s.nextInt(),s.nextInt(),s.nextInt());
		}
		s.close();
 
		double l = MIN;
		double r = MAX;
		while(r - l > EPS){
			double delta = (r - l) * fi;
			double m1 = r - delta;
			double m2 = l + delta;
			if(f(m1) > f(m2)){
				l = m1;
			}else{
				r = m2;
			}
		}		
		double x = bestPoint.x;
		double y = bestPoint.y;
		double z = bestPoint.z;
		DecimalFormat df = new DecimalFormat("0.000000", 
			DecimalFormatSymbols.getInstance(Locale.US));
		System.out.println(df.format(x) + " " + df.format(y) + " " + 
			df.format(z));
	}
 
	//опредение минимального расстояния при фиксированной координате x
	static double f(double x){
		double l = MIN;
		double r = MAX;
		while(r - l > EPS){
			double delta = (r - l) * fi;
			double m1 = r - delta;
			double m2 = l + delta;
			if(f(x,m1) > f(x,m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
		return f(x,(l + r) / 2);
	}
 
	//определение минимального расстояния при фиксированных координатах x и y
	static double f(double x,double y){
		double l = MIN;
		double r = MAX;
		while(r - l > EPS){
			double delta = (r - l) * fi;
			double m1 = r - delta;
			double m2 = l + delta;
			if(f(x,y,m1) > f(x,y,m2)){
				l = m1;
			}else{
				r = m2;
			}
		}
		return f(x,y,(l + r) / 2);
	}
 
	//определение минимального расстояния при фиксированных координатах x,y и z
	static double f(double x,double y,double z){
		double max = 0;
		for(int i = 0; i < points.length; i++){
			Point p = points[i];			
			double s = 
					(p.x - x) * (p.x - x) + 
					(p.y - y) * (p.y - y) + 
					(p.z - z) * (p.z - z);
			max = Math.max(max, s);
		}
		if(max < best){
			best = max;
			bestPoint = new PointD(x,y,z);
		}
		return max;
	}
 
}
Обратите внимание на некоторые места в коде:
  1. Мы рассчитываем не φ, а 1/φ, чтобы дальше в вычислениях использовать умножение, а не деление, т.к. умножение работает быстрее;
    static double fi = 1 / ((Math.sqrt(5) + 1) / 2);
    double delta = (r - l) * fi;
    double m1 = r - delta;
    double m2 = l + delta;
  2. В первых двух задачах мы рассматривали поиск максимального значения, а данной задаче нас интересует минимально значение, поэтому в условном операторе меняется условие:
    if(f(m1) > f(m2)){
    	l = m1;
    }else{
    	r = m2;
    }
  3. Обратите внимание, что при расчете расстояния извлечение квадратного корня опущено.
    double s = 
    	(p.x - x) * (p.x - x) + 
    	(p.y - y) * (p.y - y) + 
    	(p.z - z) * (p.z - z);
    Извлечение квадратног корня - очень затратная операция. Сравнивать расстояния можно и без извлечения корня, а если бы потребовалось узнать самое минимальное расстояние, то корень можно было бы извлечь в самом конце.