Z-алгоритм

Алгоритм находит все вхождения шаблона в тексте.

Идея состоит в том, чтобы объединить шаблон и текст и создать строку «P$T», где P — это шаблон, $ — специальный символ, который не должен присутствовать в шаблоне и тексте, а T — это текст. Создайте массив Z для объединенной строки. В массиве Z, если значение Z в любой точке равно длине шаблона, то шаблон присутствует в этой точке.

Сложность: O(m + n), где длина текста равна n, а шаблона — m

Хеширование

— это процесс генерации выходных данных фиксированного размера из входных данных переменного размера с использованием математических формул, известных как хэш-функции.

Каждый день объем данных в Интернете увеличивается экспоненциально, поэтому нам нужна такая структура данных , которая может хранить эти данные и осуществлять операции с ними таким образом, чтобы это было эффективно.

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

Компоненты хеширования

В основном существует три компонента хеширования:

1. Ключ:
Ключом может быть любая строка или целое число, которое подается в качестве входных данных в хеш-функцию — метод, который определяет индекс или место хранения элемента в структуре данных.

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

3. Хэш-таблица:
Хэш-таблица — это структура данных, которая сопоставляет ключи со значениями с помощью специальной функции, называемой хэш-функцией. Хэш хранит данные ассоциативным образом в массиве, где каждое значение данных имеет свой собственный уникальный индекс.

Хеш-функции, основанные на делении

Хэш-функция — это функция, которая преобразует заданный числовой или буквенно-цифровой ключ в небольшое практическое целочисленное значение. Сопоставленное целочисленное значение используется в качестве индекса в хеш-таблице.

Хеш-функции, основанные на делении, это самый простой и легкий метод генерации хеш-значения. Хэш-функция делит значение k на M, а затем использует полученный остаток.

Плюсы:
⁃ Этот метод вполне хорош для любого значения M.
⁃ Метод деления очень быстрый, поскольку требует всего одной операции деления.

Минусы:
⁃ Этот метод приводит к снижению производительности, поскольку последовательные ключи сопоставляются с последовательными значениями хеш-функции в хеш-таблице.
⁃ Иногда следует проявлять особую осторожность при выборе значения M.

Метод среднего квадрата для хеш-функции

Метод хеширования, который включает в себя два шага для вычисления хеш-значения:
1. Возведите в квадрат значение ключа k, т.е. k2.
2. Извлеките средние цифры r в качестве значения хеш-функции.

Плюсы:
⁃ Производительность этого метода хороша, поскольку в результат вносят вклад большинство или все цифры значения ключа. Это связано с тем, что все цифры в ключе способствуют созданию средних цифр квадрата результата.
⁃ На результат не влияет распределение верхней или нижней цифры исходного значения ключа.

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

Метод складывания цифр для хеш-функции

Этот метод включает в себя два этапа:
1. Разделите ключ-значение k на несколько частей, то есть k1, k2, k3,….,kn, где каждая часть имеет одинаковое количество цифр, за исключением последней части, которая может иметь меньше цифр, чем другие части.
2. Добавьте отдельные части. Хэш-значение получается путем игнорирования последнего переноса, если таковой имеется.

Примечание:
Количество цифр в каждой части варьируется в зависимости от размера хеш-таблицы. Предположим, например, что размер хеш-таблицы равен 100, тогда каждая часть должна содержать две цифры, за исключением последней части, которая может иметь меньшее количество цифр.

Метод обработки коллизий — метод цепочек

Идея отдельной цепочки заключается в реализации массива в виде связанного списка, называемого цепочкой.

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

Преимущества:
⁃ Просто реализовать.
⁃ Хэш-таблица никогда не заполняется, мы всегда можем добавить в цепочку больше элементов.
⁃ Менее чувствителен к хэш-функции или факторам нагрузки.
⁃ Чаще всего используется, когда неизвестно, сколько и как часто ключей можно вставлять или удалять.

Недостатки:
⁃ Некоторые части хеш-таблицы никогда не используются
⁃ Если цепочка становится длинной, то время поиска в худшем случае может стать O(n).
⁃ Использует дополнительное пространство для ссылок

Количество диагоналей в n-стороннем выпуклом многоугольнике

Чтобы найти количество диагоналей в n-стороннем выпуклом многоугольнике, можно воспользоваться следующей формулой:

Количество диагоналей = (n * (n - 3)) / 2

Эта формула выведена из того факта, что в выпуклом многоугольнике с n сторонами каждая вершина может быть соединена с любой другой вершиной диагональю, за исключением самой себя, соседних с ней вершин и двух соседних с ними вершин. В результате из каждой вершины можно провести n — 3 диагонали. Однако вы должны разделить это на 2, чтобы не считать каждую диагональ дважды (поскольку, например, соединение вершины A с вершиной B — это то же самое, что соединение вершины B с вершиной A).

Задача о ходе коня

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

Алгоритм:
1. Создаем шахматную доску n x n, где n - размерность доски.
2. Инициализируем текущую позицию коня на доске.
3. Помечаем текущую позицию как посещенную.
4. Проверяем, есть ли еще непосещенные клетки на доске:
- Если все клетки посещены, то задача решена, и мы можем вернуть найденный маршрут.
- Если не все клетки посещены, переходим к следующему шагу.
5. Находим все возможные ходы коня из текущей позиции:
- Проверяем, что следующий ход находится в пределах доски и не был посещен.
6. Для каждого возможного хода коня:
- Передвигаем коня на следующий ход.
- Рекурсивно вызываем алгоритм для новой позиции коня.
- Если рекурсивный вызов вернул true (маршрут найден), то возвращаем true.
- Если рекурсивный вызов вернул false, отменяем текущий ход и ищем другие возможные ходы.

Сложность: O(8^n), где n - размерность доски.

Задача о сумме подмножеств

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

Для каждого элемента есть две возможности:
1. Включите текущий элемент в подмножество и повторите операцию для остальных элементов с оставшейся суммой.
2. Исключить текущий элемент из подмножества и повторить операцию для остальных элементов.
3. Наконец, если сумма становится равной 0, выведите элементы текущего подмножества.

Сложность: O(n^2)

Поменять местами два числа без использования временной переменной (Используя сложение и вычитание)

Пусть у нас есть два числа a и b, и мы хотим поменять их местами.

Шаги для обмена местами:

Присвоим переменной a новое значение, которое будет суммой a и b.
Вычтем из переменной b исходное значение переменной a (которое мы присвоили в шаге 1).
Присвоим переменной a новое значение, которое будет разностью между новым значением a и исходным значением b.
Теперь переменная a содержит исходное значение b, а переменная b содержит исходное значение a, и мы успешно поменяли местами значения двух переменных.

Поменять местами два числа без использования временной переменной.
(Используя умножения и деления)

Пусть у нас есть два числа a и b, и мы хотим поменять их местами.

Присвоим переменной a новое значение, которое будет произведением a на b.
Присвоим переменной b новое значение, которое будет результатом деления нового значения a на исходное значение b.
Присвоим переменной a новое значение, которое будет результатом деления нового значения a на новое значение b.
Теперь переменная a содержит исходное значение b, а переменная b содержит исходное значение a, и мы успешно поменяли местами значения двух переменных.

Поменять местами биты в заданном числе

Учитывая число X и две позиции (справа) в двоичном представлении X, можно поменять местами n бит в данных двух позициях. Кроме того, предусмотрим, что два набора битов не перекрываются.

Алгоритм:
1) Переместить все биты первого набора в крайнюю правую часть.
set1 = (x >> p1) & ((1U << n) - 1)
Здесь выражение (1U << n) - 1 дает число, которое содержит последние n битов, а остальные биты равны 0. Проделываем операцию & с этим выражением, чтобы биты, отличные от последнего n бит стали 0.
2) Переместить все биты второго набора в крайнюю правую сторону.
set2 = (x >> p2) & ((1U << n) - 1)
3) XOR двух наборов битов
xor = (set1 ^ set2)
4) Вернуть биты xor в исходное положение.
xor = (xor << p1) | (xor << p2)
5) Выполнить XOR xor с исходным номером.
result = x ^ xor

Самый быстрый способ поменять два числа местами

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

Например, XOR для 10 (в двоичном формате 1010) и 5 (в двоичном формате 0101) — это 1111, а XOR для 7 (0111) и 5 (0101) — это (0010).

Проверка четности. Простой способ

Четность числа — это свойство, которое определяет, четное или нечетное количество установленных битов (битов, равных 1) в числе. Если количество установленных битов четное, то четность равна 0 (false), если нечетное — 1 (true).

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

Проверка четности с помощью таблицы поиска. Метод с побитовым сдвигом

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

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

Преимущества использования таблицы поиска:
- Быстродействие: Быстрое вычисление за счет предвычисленных значений.
- Простота: Уменьшение количества битовых операций и циклов.

PostgreSQL и DevOps: управление базой данных через CI/CD и Kubernetes

Как автоматизировать развёртывание, обслуживание и мониторинг PostgreSQL в продакшн-среде? На открытом вебинаре курса OTUS PostgreSQL. Advanced Антон Герасименко покажет, как объединить DevOps-практики и PostgreSQL 17, чтобы упростить работу с базой данных и повысить её отказоустойчивость.

→ 8 декабря, 18:00

PostgreSQL и DevOps — управляем базой данных через CI/CD и Kubernetes
— создание Docker-контейнера для PostgreSQL и его правильная настройка
— использование Kubernetes-операторов для автоматического развертывания
— мониторинг и алертинг через Prometheus и Grafana
— настройка репликации и standby-реплик в PostgreSQL 17
— интеграция миграций и бэкапов в CI/CD-процессы

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

→ Зарегистрируйтесь: https://otus.pw/Wm78h/

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Проверка четности с помощью таблицы поиска. Метод с указателем

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

Метод с указателем заключается в использовании указателя на байты числа и вычисление четности для XOR всех четырех байтов.

Преимущества использования таблицы поиска:
- Быстродействие: Быстрое вычисление за счет предвычисленных значений.
- Простота: Уменьшение количества битовых операций и циклов.

Проверка четности 32-битного числа с использованием умножения

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

Он полезен для приложений, требующих быстрого и эффективного вычисления четности чисел.

Прикладная задача на структуры данных из продакшена Яндекс Еды.

Дано: ~500k ресторанов и ~3M зон доставки в виде многоугольников. Нужно по координате пользователя за ~50 мс найти все рестораны, которые реально могут привезти заказ, причём зоны постоянно меняются.

В статье ребята разбирают, почему для геоиндекса не подошли Geohash и H3, и как в итоге пришли к R-дереву с логарифмическим поиском и отдельными индексами для ресторанов, ритейла и самовывоза. Есть схемы вставки, поиска и оценка сложности.

👉 Ссылка на разбор

Проверка четности 64-битного числа с использованием умножения

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

Он полезен для приложений, требующих быстрого и эффективного вычисления четности чисел.