Category: Алгоритмы

21
Ноя
2022

🙌 12 алгоритмов, которые должен знать каждый разработчик: объясняем на гифках

Алгоритмы давно заняли особую нишу как в Computer Science, так и в разработке ПО. Однако какую роль они играют в жизни разработчика и что конкретно из них следует изучить и знать? Об этом вы узнаете из нашей статьи.

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

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

Поэтому мы собрали 12 алгоритмов, которые должен проработать начинающий разработчик, чтобы развивать и применять алгоритмическое мышление.

Бинарный поиск

Бинарный поиск – это одна из первых вещей, с которыми сталкиваются в начале изучения computer science. Это возможно самый простой пример того, как немного изобретательности может сделать решения, в буквальном смысле, экспоненциально более эффективными.

Его суть в том, что нам дан отсортированный массив. Необходимо итеративно делить его пополам, брать значение в середине и сравнивать его с элементом, который хотим найти: если он больше – ищем в правой половине, если меньше – в левой. И так до тех пор, пока элемент не будет найден.

Бинарный поиск. Источник: <a href="https://brilliant.org/wiki/binary-search/" target="_blank" rel="noopener noreferrer nofollow">brilliant.org</a>
Бинарный поиск. Источник: brilliant.org

Сортировки пузырьком, выбором, вставками

Алгоритмы сортировки – один из фундаментальных инструментов, которые разработчик должен иметь в своем арсенале. Квадратичные сортировки (пузырьком, выбором, вставками) – первое, что следует проработать начинающему разработчику. В случае когда скорость имеет значение, вы вряд ли будете их использовать, но работа с ними является хорошим введением в работу с массивами.

Сортировки пузырьком. Источник: <a href="https://commons.wikimedia.org/wiki/File:Bubble-sort-example-300px.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Сортировки пузырьком. Источник: Wikipedia
Сортировка выбором. Источник: <a href="https://codepumpkin.com/selection-sort-algorithms/" target="_blank" rel="noopener noreferrer nofollow">Codepumpkin.com</a>
Сортировка выбором. Источник: Codepumpkin.com
Сортировка вставками. Источник: <a href="https://studiousguy.com/insertion-sort-in-data-structure/" target="_blank" rel="noopener noreferrer nofollow">Studiousguy.com</a>
Сортировка вставками. Источник: Studiousguy.com

Быстрая сортировка и сортировка слиянием

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

Быстрая сортировка. Источник: <a href="https://commons.wikimedia.org/wiki/File:Quicksort-example.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Быстрая сортировка. Источник: Wikipedia
Сортировка слиянием. Источник: <a href="https://commons.wikimedia.org/wiki/File:Merge-sort-example-300px.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Сортировка слиянием. Источник: Wikipedia

Кодирование Хаффмена

Кодирование Хаффмена – это основа современного сжатия текстов. Суть его заключается в анализе частотности появления символов в тексте и построения на его основе дерева из этих символов.

Уделение времени разбору как работает кодирование Хаффмана – это хороший способ освоиться в работе с представлением данных и обходом деревьев, что является двумя наиболее важными проблемными вопросами, с которыми приходится сталкиваться специалистам по Computer Science.

Кодирование Хаффмена. Источник: <a href="https://commons.wikimedia.org/wiki/File:Huffman_huff_demo.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Кодирование Хаффмена. Источник: Wikipedia

Поиск в ширину

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

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

Поиск в ширину. Источник: <a href="https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Поиск в ширину. Источник: Wikipedia

Поиск в глубину

Поиск в глубину является вторым основным подходом нахождения элемента в дереве. Вместо обхода дерева поуровнево, он исследует дерево ветка за веткой.

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

Поиск в глубину. Источник: <a href="https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Поиск в глубину. Источник: Wikipedia

Градиентный спуск

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

Градиентный спуск – это способ оптимизации функций, основанный на вычислениях. В контексте машинного обучения или регрессии это значит нахождение значений весов алгоритма ML, минимизирующих ошибку в предсказаниях. И хотя математически он более сложен, чем остальные алгоритмы, при работе с данными и предсказаниями понимание его работы имеет огромное значение.

Градиентный спуск. Источник: <a href="https://commons.wikimedia.org/wiki/File:Gradient_descent.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Градиентный спуск. Источник: Wikipedia

Алгоритм Дейкстры

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

Алгоритм Дейкстры – это способ поиска кратчайшего пути между узлами в графе. Он является базой в задачах поиска пути и находит широкое применение начиная с искусственного интеллекта и заканчивая созданием игр.

Алгоритм Дейкстры. Источник: <a href="https://commons.wikimedia.org/wiki/File:Dijkstra_Animation.gif" target="_blank" rel="noopener noreferrer nofollow">Wikipedia</a>
Алгоритм Дейкстры. Источник: Wikipedia

Обмен ключами Диффи-Хеллмана

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

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

Обмен ключами Диффи-Хеллмана. Источник: <a href="https://gfycat.com/ru/consciousminorhuia-diffie-hellman-key-exchange-university-of-nottingham" target="_blank" rel="noopener noreferrer nofollow">Gfycat</a>
Обмен ключами Диффи-Хеллмана. Источник: Gfycat

Решение практических задач

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

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

На них вы найдете трудные, но решаемые алгоритмические задачи и отточите свои навыки.

Так каков итог?

Повторимся – не стоит просто зазубривать алгоритмы и думать, что это сделает тебя лучше как разработчика. Разработка ПО, прежде всего, заключается в умении понимать проблемы и создавать их решения. Изучение алгоритмов важно не потому, что вам придется в точности их имплементировать в своей работе. Оно важно, потому что учит вас находить подход к задаче.

***

Мне сложно разобраться самостоятельно, что делать?

Алгоритмы и структуры данных действительно непростая тема для самостоятельного изучения: не у кого спросить и что-то уточнить. Поэтому мы запустили курс «Алгоритмы и структуры данных», на котором в формате еженедельных вебинаров вы:

  • изучите сленг, на котором говорят все разработчики независимо от языка программирования: язык алгоритмов и структур данных;
  • научитесь применять алгоритмы и структуры данных при разработке программ;
  • подготовитесь к техническому собеседованию и продвинутой разработке.

Курс подходит как junior, так и middle-разработчикам.

29
Авг
2022

🤖🎨 ИИ для рисования: раскрываем секреты нейронного переноса стиля

Раскладываем по полочками, как «думает» нейронная сеть VGG-19, когда ей прилетает задача скопировать стиль художника из вида Homo sapiens.

В мире, в котором NFT продаются за миллионы долларов, следующим прибыльным бизнесом может стать создание уникальных виртуальных сущностей, и кто же лучше выполнит эту работу, чем искусственный интеллект? Фактически задолго до бума NFT, в октябре 2018-го, первый портрет, сгенерированный ИИ, был продан за $432.500. С этого момента люди использовали свое глубокое знание передовых алгоритмов для создания потрясающих предметов искусства. Например, Рефик Анадол – художник, использующий ИИ для создания захватывающих картин (ознакомиться с его работами можно по этой ссылке). Другой цифровой художник, Петрос Вреллис, в 2012 году выставил интерактивную анимацию знаменитой работы Ван Гога «Звездная ночь», которая собрала более 1.5 миллиона просмотров за три месяца.

Однако творческие возможности ИИ не ограничиваются живописью. Люди создают интеллектуальные системы, способные писать стихи, песни, сценарии, и, возможно, делать и другую творческую работу. Движемся ли мы к миру, в котором всем творческим людям придется конкурировать с компьютерами? Возможно, но это не то, что я собирался обсудить. Моя цель – погрузиться в принципы работы элегантного алгоритма нейронного переноса стиля (neural style transfer), способного превратить даже ужасных художников вроде меня в виртуозов.

1. Идея нейронного переноса стиля

Любое изображение можно разделить на две составляющие: содержание и стиль. Содержание – это хитросплетение объектов, а стиль – это общая тема. Эти составляющие можно также интерпретировать как локальные и глобальные сущности в изображении. Например, на приведенном ниже изображении содержание – это детализированный дизайн Эйфелевой башни, а тени заднего плана (голубое небо, зеленые деревья и трава) создают стиль (тему).

<span>Фото </span><a href="https://unsplash.com/@k_drew" target="_blank" rel="noopener noreferrer nofollow"><span>Кирстен Дрю</span></a><span> на </span><a href="https://unsplash.com" target="_blank" rel="noopener noreferrer nofollow"><span>Unsplash</span></a>
Фото Кирстен Дрю на Unsplash

Идея нейронного переноса стиля (NST) в том, чтобы взять одно изображение и переделать его содержимое в стиле какого-нибудь другого изображения. Перенос темы (стиля) с более привлекательного изображения – такого, как знаменитая картина «Звездная ночь» Ван Гога – может привести к потрясающим переделкам.


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

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека data scientist’а»

2. Сверточные нейронные сети для переноса стиля

Поскольку мы работаем с изображениями, вас не должно удивлять, что основным механизмом переноса стиля являются сверточные нейронные сети. Также, поскольку множество сверточных нейронных сетей добились прекрасных результатов в задачах обработки изображений, нам не придется обучать отдельную сеть для переноса стиля. Я использую сеть VGG-19 (transfer learning для переноса стиля), но вы можете использовать любую другую предобученную сеть или обучить свою.

Сеть VGG-19 имеет следующую архитектуру:


Для начала давайте посмотрим, что распознают некоторые из этих слоев. В каждом слое есть не менее 64 фильтров, выделяющих признаки из изображений. Для простоты мы используем выходы первых десяти слоев, чтобы увидеть, чему они обучаются. Если вы хотите увидеть код, смотрите его на Kaggle либо в GitHub.

<span>Block_1_conv_1</span>
Block_1_conv_1
<span>Block_2_conv_1</span>
Block_2_conv_1
<span>Block_3_conv_1</span>
Block_3_conv_1
<span>Block_4_conv_1</span>
Block_4_conv_1
<span>Block_5_conv_1</span>
Block_5_conv_1
<span>Block_5_conv_2</span>
Block_5_conv_2

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

Затем, по мере прохождения изображения по нейронной сети, выходы слоев размываются. Выходы фильтров этих слоев, особенно block_5_conv_2 (последний), фокусируются на конкретных локациях и извлекают информацию о формах различных объектов. Например, два следующих фильтра интересуются мелкими деталями Эйфелевой башни. Возможно, в задаче классификации такие локальные признаки помогли бы сверточной нейронной сети отличить Эйфелеву башню от любого другого здания похожей структуры – например, от опоры ЛЭП.

<span>Выход слоя block_5_conv_2 (фильтр 4)</span>
Выход слоя block_5_conv_2 (фильтр 4)
<span>Выход слоя block_5_conv_2 (фильтр 13)</span>
Выход слоя block_5_conv_2 (фильтр 13)

Разделимость глобальных и локальных компонентов изображения при обработке с помощью сверточных нейронных сетей – именно то, что лежит в основе передачи стиля. Авторы нейронного алгоритма художественного стиля и оригинальной статьи о нейронной передаче стиля (Гейтис и пр.) сообщают, что поскольку глубокие слои хорошо идентифицируют детализированные признаки, они используются для получения содержимого изображения. Аналогично, начальные слои, способные хорошо усваивать контуры объектов, используются для получения стиля изображения (темы или глобальных признаков).

3. Создание нового изображения

Наша цель – создание нового изображения, сочетающего содержимое одного изображения и стиль другого. Давайте сначала разберемся с содержимым.

3.1. Информация о содержимом

В прошлом разделе мы установили, что выходы глубоких слоев нейронной сети помогают определить содержимое изображения. Теперь нам нужен алгоритм для получения этого содержимого. Для этого мы используем уже знакомые математические методы: функции потерь (loss) и обратное распространение (backpropagation).

<span>Изображение из шума (сгенерированное на Python)</span>
Изображение из шума (сгенерированное на Python)

Рассмотрим приведенное выше изображение, состоящее из шума (X). Для простоты примем, что сверточная нейронная сеть, которую мы выбрали для передачи стиля, состоит всего из двух слоев, A1 и A2. Передавая целевое изображение (Y) через сеть и используя выходы A2, A2(A1(Y)), мы получаем информацию о его содержимом. Чтобы изучить/выделить эту информацию, мы передаем X через ту же сеть. Поскольку X состоит из случайно распределенных значений пикселей, A2(A1(X)) также будет случайным. Затем мы определяем функцию потерь содержимого как:

Lcontent=12∑i,j(A2(A1(X)−A2(A1(Y)))2

Здесь i и j – обозначения индексов массива изображения (размеры целевого изображения с содержимым и изображения с шумом должны быть одинаковыми). Фактически, если результирующие массивы A2(A1(X)) и A2(A1(Y)) имеют размерность (m, n), функция потерь вычисляет их разницу в каждой точке, возводит ее в квадрат, а потом суммирует все эти квадраты. С помощью такой функции потерь мы заставляем X стать таким изображением, которое выдает такую же информацию о содержимом, что и Y. Мы можем минимизировать потери с помощью обратного распространения, как мы делали это в любой нейронной сети, но есть небольшая разница. В нашем случае обучаемые параметры – не веса нейронной сети, а сам массив X. Вот как выглядит финальное уравнение:

Xnew=X−α∂Lcontent∂X

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

3.2. Информация о стиле

Получение информации о стиле сложнее, чем получение информации о содержимом. Оно требует понимания матриц Грама.

3.2.1. Матрицы Грама

Рассмотрев архитектуру VGG-19 (см. пункт 2), вы можете увидеть, что выход слоя block_1_conv_1 имеет размерность (m, n, 64). Для простоты примем, что m,n = 3,2, и количество фильтров тоже равно 2, а не 64.

<span>Выходы двух фильтров</span>
Выходы двух фильтров

Как вы знаете, фильтры сверточной нейронной сети обучаются распознавать различные пространственные признаки вроде краев/линий, интенсивности цветов и т.д. Давайте скажем, что приведенные выше фильтры распознают оттенки красного и синего цветов в разных локациях. То есть, значение пикселей (от 0 до 1) в каждой ячейке фильтра 1 представляет интенсивность красного цвета в этой локации, а в фильтре 2 – интенсивность синего цвета. Теперь склеим оба выходных массива вместе и умножим результат на его же транспонированное значение. Что мы получим в результате?


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


Следовательно, матрица Грама, в контексте сверточных сетей – это матрица корреляции между всеми признаками, извлекаемыми всеми фильтрами слоя. Давайте посмотрим, как они помогают в переносе стиля.

3.2.2. Стиль и комбинированные потери

<span>Фото </span><a href="https://unsplash.com/@steve_j" target="_blank" rel="noopener noreferrer nofollow"><span>Стива Джонсона</span></a><span> на </span><a href="https://unsplash.com" target="_blank" rel="noopener noreferrer nofollow"><span>Unsplash</span></a>
Фото Стива Джонсона на Unsplash

Предположим, мы хотим передать стиль из приведенного выше изображения. Заметьте, что наличие множества полос (вертикальных и горизонтальных линий) голубого цвета, переходящего в белый. Матрицы Грама двух фильтров, обнаруживающих линии и светло-голубой цвет, покажут высокую корреляцию между этими признаками. Следовательно, алгоритм обеспечит, чтобы в реконструированном изображении эти два признака встречались вместе, что прекрасно послужит для передачи стиля. В реальности каждый слой сверточной сети имеет множество фильтров, что приводит к огромным матрицам Грама, но идея остается все той же. Например, матрица Грама для выходов слоя block_1_conv_1 в VGG19, будет матрицей корреляции между 64 признаками.

Затем нам нужно определить функцию потерь для стиля. Предположим, что пропустив наше целевое изображение через block_1_conv_1, мы получили матрицу Грама G. Мы пропускаем через тот же слой наше зашумленное изображение X и рассчитываем ее матрицу Грама P. Тогда потери стиля можно рассчитать так:

Lstyle,layer=l=1(2∗H∗W∗N)2∑i,j(Pi,j−Gi,j)2

Здесь (i,j) – обозначения индексов в матрицах Грама. Минимизируя эту функцию, мы обеспечиваем, что матрица X будет иметь такую же корреляцию между признаками, как наше целевое изображение со стилем.

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

Lstyle=∑0lwlLstyle,layer=l

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

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

Loss=aLstyle+bLcontent
Xnew=X−α∂Loss∂X

4. Изменение гиперпараметров

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

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

Мы используем для своих экспериментов следующие изображения:


4.1. 5 слоев с одинаковыми весами потерь, 1 слой содержимого

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


4.2. Повышаем вес функции потерь стиля с 0.005 до 0.1

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


4.3. Используем один слой для стиля

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


4.4. Используем другой слой в функции потерь содержимого

Использование слоя block_1_conv_1 для информации содержимого заставляет сеть забирать глобальные признаки из целевого изображения содержимого. Это, вероятно, интерферирует с глобальными признаками из изображения стиля, и передача стиля получается ужасной. По-моему, результат демонстрирует, почему для нейронной передачи стиля рекомендуется выбирать глубокие слои. Они концентрируются исключительно на локальных деталях, относящихся к важнейшим объектам в изображении содержимого, что обеспечивает беспрепятственную передачу темы изображения стиля.


4.5. Назначаем веса слоев стиля вручную [0.4, 0.3, 0.2, 0.05, 0.05]

Хотя разница между изображением из п. 4.1 и этим невелика, мне кажется, что это изображение имеют общую светлую тень. Возможно, это следствие большего веса, назначенного слою block_1_conv_1, что, в соответствии с п. 4.3, генерирует белый тон из картины «Звездная ночь».


4.6. Назначаем веса слоев стиля вручную [0.05, 0.05, 0.2, 0.3, 0.4]

Это куда более удачная комбинация цветов, чем 4.5. Назначение больших весов глубоким слоям обеспечивает гораздо более привлекательные результаты. Возможно, матрицы Грама для этих слоев вычисляют корреляцию между более доминантными глобальными признаками из «Звездной ночи».


4.7. Передача стиля из нескольких изображений

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

Lstyle,image=i=∑0lwlLstyle,layer=l

Однако, общая функция потерь выглядит вот так:

Lstyle=Ai∑0i∑0lwlLstyle,layer=l,image=i

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


5. Заметки

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

6. Ссылки

***

Материалы по теме

16
Авг
2022

🤖 5 классических алгоритмов машинного обучения, о которых вам обязательно следует знать

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

Данная статья является переводом. Ссылка на оригинал.

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

Почему именно такой формат?

  1. Практическое применение. Знания бесполезны, если они не могут быть применены. Разбивка на основные группы по применению даст лучшее понимание того, какие задачи вы можете решить, используя тот или иной алгоритм.
  2. Актуальность. Правда в том, что не все алгоритмы машинного обучения сохраняют свою актуальность. Вы сразу увидите, что такие традиционные алгоритмы, как наивный байесовский алгоритм, не включены в статью просто потому, что они деклассированы более совершенными алгоритмами.
  3. Усвояемость. Есть тысячи онлайн ресурсов, которые научат тебя реализовывать модели, о которых пойдет далее разговор. Мы же больше сфокусированы на оптимальном применении каждого типа алгоритмов.

С учетом вышесказанного разделим алгоритмы машинного обучения на 5 наиболее важных классов:

  1. Ансамблевые алгоритмы.
  2. Объяснительные алгоритмы.
  3. Алгоритмы кластеризации.
  4. Алгоритмы понижения размерности.
  5. Алгоритмы схожести.

1. Ансамблевые алгоритмы (Random forest, XGBoost, LightGBM, CatBoost)


Что такое ансамблевые алгоритмы?

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

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

В этом случае класс студентов – это аналог ансамблевого алгоритма, в котором несколько небольших алгоритмов работают вместе для выведения финального ответа.

Когда используются?

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

Примеры алгоритмов

  • Random Forest (Случайный лес);
  • XGBoost;
  • LightGBM;
  • CatBoost.
Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека data scientist’а»

2. Объяснительные алгоритмы (Линейная регрессия, Логистическая регрессия, SHAP, LIME)


Что такое объяснительные алгоритмы?

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

С точки зрения регрессии, очень много внимания уделяется статистически значимым переменным. Почему? Практически всегда вы будете работать с выборкой данных, являющейся подмножеством всей совокупности. Для того чтобы сделать верные выводы о совокупности по выборке, важно убедиться, что результат статистически значим.

Недавно появились два метода: SHAP и LIME. Они используются для интерпретации моделей машинного обучения.

Когда используются?

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

На практике возможность объяснить, как ваша модель работает, так же важна, как и качество модели. Если вы не можете объяснить, никто не поверит ей и никто не будет её использовать. Это особенно актуально для банковской сферы, где все модели должны быть интерпретируемыми.

Примеры алгоритмов

Традиционные объяснительные модели, основанные на проверке гипотез:

  1. Линейная регрессия.
  2. Логистическая регрессия.

Алгоритмы для объяснения моделей машинного обучения:

  • SHAP;
  • LIME.

3. Алгоритмы кластеризации


Что такое алгоритмы кластеризации?

Алгоритмы кластеризации используются, чтобы проводить кластерный анализ задач, – обучение без учителя – заключающийся в группировке данных в кластеры. В отличие от обучения с учителем, где целевая переменная известна, в кластерном анализе её нет.

Когда используются?

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

Также кластеризация позволяет нам идентифицировать отдельные сегменты в наборе данных, основанном на различных переменных. Одна из самых распространенных задач кластерной сегментации – сегментация пользователей.

Примеры алгоритмов

Самые распространенные алгоритмы кластеризации – k-means и иерархическая кластеризация, хотя существуют и другие.

  • K-means;
  • иерархическая кластеризация.

4. Алгоритмы понижения размерности (PCA, LDA)


Что такое алгоритмы понижения размерности?

К алгоритмам понижения размерности относятся методы, уменьшающие число поступающих на вход переменных (или признаков) в датасете. Понижение размерности тесно связано с феноменом «проклятие размерности», утверждающим что с ростом размерности (число поступающих на вход переменных) увеличивается объем пространства, в результате чего данные становятся разреженными.

Когда используются?

Алгоритмы понижения размерности используются во многих случаях:

  1. Когда у вас сотни и даже тысячи признаков в датасете и вам нужно выбрать только самые полезные.
  2. Когда алгоритм машинного обучения переобучается на исходных данных.

Примеры алгоритмов

Ниже представлены два самых распространенных алгоритма понижения размерности:

  • метод главных компонент (PCA);
  • линейный дискриминантный анализ (LDA).

5. Алгоритмы схожести (KNN, расстояния: Евклида, косинусное, Левенштейна, Джаро-Винклера, SVD и т. д.)


Что такое алгоритмы схожести?

Алгоритмы схожести вычисляют сходство пары записей/узлов/точек/текстов. Есть алгоритмы, которые вычисляют расстояние между двумя значениями данных, такими как расстояние Евклида. А также есть алгоритмы, вычисляющие схожесть текстов, такие как алгоритм Левенштейна.

Когда используются?

Алгоритмы сходства применяются повсеместно, но чаще всего в рекомендательных системах.

  1. Какие статьи предложит тебе Medium, основываясь на прочитанном тобой ранее?
  2. Какие ингредиенты вы можете использовать для замены голубики?
  3. Какие треки предложит тебе Spotify, основываясь на треках, которые тебе уже нравятся?
  4. Какие продукты Amazon предложит тебе, основываясь на истории покупок?

Это только некоторые примеры применения алгоритмов сходства в повседневной жизни.

Примеры алгоритмов

Ниже приведены самые популярные алгоритмы сходства:

  • К-ближайших соседей;
  • расстояние Евклида;
  • косинусное сходство;
  • алгоритм Левенштейна;
  • алгоритм Джаро-Винклера;
  • сингулярное разложение (SVD).
***

Материалы по теме

04
Авг
2022

🏭 Порождающие шаблоны проектирования: структура и применение на простых примерах

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

17
Июн
2022

📐 10 алгоритмов для работы с графами, которые должен знать каждый кодер

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

Данная статья является переводом. Ссылка на оригинальную статью.

Зачем вообще изучать графовые алгоритмы?

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

Данные алгоритмы применяют на сайтах социальных сетей, в моделировании конечного автомата, а также во многих других сферах. Я приложил свой исходный код для всех алгоритмов, про которые мы будем говорить ниже.

1. Поиск в ширину (Breadth First Searching)

Поиск в ширину — это рекурсивный алгоритм поиска всех вершин графа или дерева. Обход начинается с корневого узла и затем алгоритм исследует все соседние узлы. Затем выбирается ближайший узел и исследуются все неисследованные узлы. При использовании BFS для обхода любой узел графа можно считать корневым узлом.

Простой алгоритм для BFS, который нужно запомнить:

  1. Перейдите на соседнюю нерассмотренную вершину. Отметьте как рассмотренную. Отобразите это. Вставьте ее в очередь.
  2. Если смежная вершина не найдена, удалите первую вершину из очереди.
  3. Повторяйте шаг 1 и шаг 2, пока очередь не станет пустой.

Схематическое представление обхода BFS:

Поиск в ширину (Breadth First Searching)
Поиск в ширину (Breadth First Searching)

Ссылка на код: Поиск в ширину

2. Поиск в глубину (Depth First Searching)

Поиск в глубину или обход в глубину — это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных.

Алгоритм поиска в глубину (DFS) осуществляет поиск вглубь графа, а также использует стек, чтобы не забыть «получить» следующую вершину для начала поиска, когда на любой итерации возникает тупик.

Простой алгоритм, который нужно запомнить, для DFS:

  1. Посетите соседнюю непосещенную вершину. Отметьте как посещенную. Отобразите это. Добавьте в стек.
  2. Если смежная вершина не найдена, то вершина берется из стека. Стек выведет все вершины, у которых нет смежных вершин.
  3. Повторяйте шаги 1 и 2, пока стек не станет пустым.

Схематическое представление обхода DFS:

Поиск в глубину (Depth First Searching)
Поиск в глубину (Depth First Searching)

Ссылка на код: Поиск в глубину

Если хочешь подтянуть свои знания по алгоритмам, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

  • углубишься в теорию структур данных;
  • научишься решать сложные алгоритмические задачи;
  • научишься применять алгоритмы и структуры данных при разработке программ.

3. Топологическая сортировка (Topological Sorting)

Топологическая сортировка для ориентированного ациклического графа (DAG) — это линейное упорядочивание вершин, при котором вершина u предшествует v для каждого направленного ребра uv (в порядке очереди). Топологическая сортировка для графа невозможна, если граф не является DAG.

Для одного графа может применяться более одной топологической сортировки.

Простой алгоритм, который следует запомнить, для топологической сортировки:

1. Отметьте u как посещенную

2. Для всех вершин v, смежных с u, выполните:

2.1. Если v не посещенная, то:

2.2. Выполняем TopoSort (не забывая про стек)

2.3. Цикл выполнен

3. Запишите u в стек

Схематическое представление топологической сортировки:

Топологическая сортировка (Topological Sorting)
Топологическая сортировка (Topological Sorting)

Пример топологической сортировки для этого графа:

5 → 4 → 2 → 3 → 1 → 0

Ссылка на код: Топологическая сортировка

4. Обнаружение цикла с помощью алгоритма Кана (Kahn’s Algorithm)

Алгоритм топологической сортировки Кана — это алгоритм обнаружения циклов на базе эффективной топологической сортировки.

Работа алгоритма осуществляется путем нахождения вершины без входящих в нее ребер и удаления всех исходящих ребер из этой вершины.

Ссылка на код: Обнаружение цикла с использованием алгоритма Кана

5. Алгоритм Дейкстры (Dijkstra’s Algorithm)

Алгоритм Дейкстры позволяет найти кратчайший путь между любыми двумя вершинами графа. Он отличается от минимального остовного дерева тем, что кратчайшее расстояние между двумя вершинами может не включать все вершины графа.

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


После применения алгоритма Дейкстры:

Алгоритм Дейкстры (Dijkstra's Algorithm)
Алгоритм Дейкстры (Dijkstra’s Algorithm)

Ссылка на код: Алгоритм Дейкстры

6. Алгоритм Беллмана-Форда (Bellman Ford’s Algorithm)

Алгоритм Беллмана-Форда помогает нам найти кратчайший путь от вершины ко всем другим вершинам взвешенного графа. Он похож на алгоритм Дейкстры, но может обнаруживать графы, в которых ребра могут иметь циклы с отрицательным весом.

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

Алгоритм Беллмана-Форда (Bellman Ford's Algorithm)
Алгоритм Беллмана-Форда (Bellman Ford’s Algorithm)

Результат алгоритма Беллмана-Форда:

Результат алгоритма Беллмана-Форда
Результат алгоритма Беллмана-Форда

Ссылка на код: Алгоритм Беллмана Форда

7. Алгоритм Флойда-Уоршалла (Floyd-Warshall Algorithm)

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

Алгоритм, лежащий в основе алгоритма Флойда-Уоршалла:

Dij(k) ← min ( Dij(k-1), Dij(k-1)+Dkj(k-1))

Ссылка на код: Алгоритм Флойда-Уоршалла

8. Алгоритм Прима (Prim’s Algorithm)

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

Простой алгоритм для алгоритма Прима, который следует запомнить:

  1. Выберите минимальное остовное дерево со случайно выбранной вершиной.
  2. Найдите все ребра, соединяющие дерево с новыми вершинами, найдите минимум и добавьте его в дерево.
  3. Продолжайте повторять шаг 2, пока мы не получим минимальное остовное дерево.

Получим:

Алгоритм Прима (Prim's Algorithm)
Алгоритм Прима (Prim’s Algorithm)

Ссылка на код: Алгоритм Прима

9. Алгоритм Краскала (Kruskal’s Algorithm)

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

Простой алгоритм Краскала, который следует запомнить:

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

Ссылка на код: Алгоритм Краскала

10. Алгоритм Косараджу (Kosaraju’s Algorithm)

Если мы можем достичь каждой вершины компонента из любой другой вершины этого компонента, то он называется сильно связанным компонентом (SCC). Одиночный узел всегда является SCC. Алгоритм Флойда-Уоршалла относится к методам полного перебора. Но для получения наилучшей временной сложности мы можем использовать алгоритм Косараджу.

Простой алгоритм Косараджу, который следует запомнить:

  1. Выполните обход графа DFS. Поместите узел в стек перед возвратом.
  2. Найдите граф транспонирования, поменяв местами ребра.
  3. Извлекайте узлы один за другим из стека и снова в DFS на модифицированном графе.

Получим:

Алгоритм Косараджу (Kosaraju's Algorithm)
Алгоритм Косараджу (Kosaraju’s Algorithm)

Ссылка на код: Алгоритм Косараджу

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

  • живые вебинары 2 раза в неделю;
  • 47 видеолекций и 150 практических заданий;
  • консультации с преподавателями курса.
***

Материалы по теме

13
Июн
2022

🌳 Деревья и графы: что это такое и почему их обязательно нужно знать каждому программисту

В этой части материала мы рассмотрим деревья и графы, а также теорию, которая стоит за ними. Выполним реализацию на языке Python и покажем, как можно использовать эти понятия на примере челленджей Leetcode.

Деревья. Теория

Деревья расширяют идею связного списка. Кроме того, они позволяют узлам иметь более одного последующего узла, который связан с предыдущим.

Узлы дерева могут иметь любое количество дочерних узлов. Благодаря этому, данные представлены в виде гибкой схемы ветвления, что позволяет хранить и извлекать их с полной отдачей.

Один из типов деревьев – двоичное дерево поиска (BST – binary search tree). В предыдущих частях материала мы упоминали, насколько эффективно BST извлекают данные. Эта эффективность обусловлена двумя важными правилами, которые определяют структуру BST:

  1. Узел может иметь не более двух дочерних узлов.
  2. Каждый узел в левом поддереве должен содержать меньшее значение, а каждый узел в правом поддереве – большее.

Поиск значения в BST занимает O(log n) времени. Это означает, что можно очень быстро найти требуемое значение среди миллионов или даже миллиардов записей.

Предположим, мы ищем узел со значением x. Чтобы быстро найти его в BST, воспользуемся следующим алгоритмом:

  1. Начать с корня дерева.
  2. Если x = значению узла: остановиться.
  3. Если x < значения узла: перейти к левому дочернему узлу.
  4. Если x > значения узла: перейти к правому дочернему узлу.
  5. Перейти к шагу 2.

При отсутствии уверенности в существовании искомого узла, необходимо изменить шаги 3 и 4 для остановки поиска.

***

Если хочешь подтянуть свои знания по алгоритмам, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

  • углубишься в теорию структур данных;
  • научишься решать сложные алгоритмические задачи;
  • научишься применять алгоритмы и структуры данных при разработке программ.

Реализация

Создание узла TreeNode идентично созданию узла ListNode. Единственное отличие в том, что вместо одного атрибута у нас два: left и right, которые ссылаются на левые и правые дочерние узлы.

        class TreeNode:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
      return f"TreeNode со значением {self.val}"
    

Таким образом, мы создаем дерево с тремя уровнями. Стоит отметить, что данное дерево – просто бинарное, а не BST, потому что значения не отсортированы.

        # Уровень 0
root = TreeNode('a')

# Уровень 1
root.left = TreeNode('b')
root.right = TreeNode('c')

# Уровень 2
root.left.left = TreeNode('d')
root.left.right = TreeNode('e')

root.right.left = TreeNode('f')
root.right.right = TreeNode('g')

#            a
#          /   \
#         b     c
#        / \   / \
#       d   e f   g
    

Примеры

При работе с двоичными деревьями у нас могут возникнуть вопросы. Как правило, они касаются различных способов обхода узлов.

Обход дерева начинается с корневого узла. Далее, используем набор шагов для обработки каждого узла, включая дочерние. Порядок обработки узлов зависит от того, в какой последовательности идет подготовка родительского узла относительно дочерних: до (pre-order), между левым и правым (in-order) и после (post-order). На примерах, приведенных ниже, обход начинался с корневого узла. Однако, порядок обработки узлов был различен.


Эти три типа обхода могут быть реализованы следующими методами:

  • с итерацией – использование цикла while и стека. В этом случае удаление данных возможно только с конца.
  • с рекурсией – использование функции, которая вызывает сама себя.

Есть четвертый тип обхода – порядок уровней (level-order traversal). Этот способ использует очередь (queue). Удаление данных здесь возможно только с начала.


Для первых трех типов обработки узлов паттерны практически идентичны. Просто выберем обход в порядке возрастания. Ниже разберем итеративный и рекурсивный методы для LC 94: Binary Tree Inorder Traversal, начиная с итеративной версии:

        # Итеративный обход
def traverse_in_order(root: TreeNode) -> List[int]:
    """
    Обход двоичного дерева, возвращается список значений по порядку
    """
    answer = []
    stack = [(root, False)]   # (узел, посещен ли он еще)

    while stack:
        node, visited = stack.pop()

        if node:

            if visited:
                answer.append(node.val)
            else:
                stack.append((node.right, False))
                stack.append((node, True))
                stack.append((node.left, False))

    return answer
    

Алгоритм действий:

  1. Строки 6-7: Создаем список для ответа (answer) и для стека (stack). List содержит кортеж корневого узла и переменную False, которая указывает на то, что этот узел еще не был затронут.
  2. Строка 9: Запускаем цикл while. Он будет выполняться до тех пор, пока в стеке есть хотя бы один элемент.
  3. Строки 10-12: Удаляем последний элемент из стека с помощью .pop. Далее проверяем существование node (узла). Node не всегда будет существовать в последующих итерациях для узлов без дочерних элементов.
  4. Строки 14-15: Добавляем значение узла к ответу. Действие происходит только в том случае, когда node существует и мы уже затрагивали этот узел.
  5. Строки 16-19: Добавляем правый дочерний, текущий и левый дочерний узлы. На правый и левый узлы ставим пометку (флаг), которая показывает, что они не были проиндексированы на данном этапе выполнения программы. На текущий узел ставим флаг, который показывает, что он был замечен программой. Действие происходит до момента, когда мы посетили этот узел.
  6. Строки 9-19: Повторяем шаги 3-6, пока не обработаем все узлы.
  7. Строка 21: Возвращаем список значений узлов, которые отсортированы по порядку.

Примечание: Добавление узлов в стек (строки 17-19), может показаться неупорядоченным. Однако, стеки работают по принципу Last In First Out. Первый узел, который нужно обработать, должен быть последним узлом, который добавляется в стек. Поэтому, сначала добавляется правый, и только потом левый узел.

Далее расскажем о рекурсивном методе:

        # Рекурсивный обход
class Solution:
    def __init__(self):
        self.answer = []

    def traverse_inorder(self, root: TreeNode) -> List[Any]:
        """
        Проходим двоичное дерево, и возвращаем список значений в порядке их следования
        """
        self._traverse(root)
        return self.answer

    def _traverse(self, node: Optional[TreeNode]) -> None:
      """
      Рекурсивная функция для последовательного обхода
      """
        if not node:
            return None

        self._traverse(node.left)
        self.answer.append(node.val)
        self._traverse(node.right)
    

Алгоритм действий:

  1. Строки 2-4: Создаем класс, который инициализируется списком для ответа (self.answer).
  2. Строки 6-11: Определяем функцию traverse_inorder, которая принимает корневой узел дерева, вызывает рекурсивную функцию _traverse и возвращает self.answer.
  3. Строки 13-22: Определяем рекурсивную функцию _traverse, которая принимает узел. Функция проверяет существование node перед тем как вызвать саму себя на левом дочернем узле. Далее она добавляет значение узла к self.answer. Затем повторно происходит операция самовызова уже на правом дочернем узле.

Подведем итоги. Данные примеры мы рассматривали в контексте обхода in-order. Для того чтобы изменить порядок следования на pre-order или post-order, в обоих случаях нужно поменять порядок обработки узла относительно его дочерних элементов. Остальная часть кода остается неизменной.

        # Изменение обхода
def iterative(root):
    ...
    stack.append((node.right, False))
    stack.append((node.left, False))
    stack.append((node, True))     # <- изменение
    ...

def _traverse(self, node):
    ...
    self.answer.append(node.val)   # <- изменение
    self._traverse(node.left)
    self._traverse(node.right)
    

Графы. Теория

Деревья расширяют область применения связанных списков, позволяя иметь более одного дочернего узла. При помощи графов можно расширить область применения и ослабить строгую «родительскую» связь в деревьях. Узлы графа не имеют явной иерархии. Каждый узел может быть соединен с любым другим узлом.


Как правило, графы представлены в виде матриц смежности (adjacency matrix). Так, у приведенного выше графа будет следующая матрица.


Каждая строка и столбец представляют собой узел. Единица в строке i и столбце j, или A_{ij}=1, означает связь между узлом i и узлом j.

A_{ij}=0 означает, что узлы i и j не связаны.

Ни один из узлов в этом графе не связан с самим собой. Следовательно, диагональ матрицы равна нулю. Аналогично, A_{ij} = A_{ji}, потому что связи ненаправленны. То есть если узел A связан с узлом B, то B связан с A. В результате матрица смежности симметрична по диагонали.

Рассмотрим пример, который поможет нам понять описанную выше теорию.


На представленных рисунках мы видим взвешенный граф с направленными ребрами. Обратите внимание, что связи больше не симметричны – вторая строка матрицы смежности пуста, потому что у B нет исходящих связей. Числа от 0 до 1 отражают силу связи. Например, граф C влияет на граф A сильнее, чем A на C.


Реализация

Реализуем невзвешенный и неориентированный граф. Основной структурой класса является список списков Python. Каждый из них – это строка. Индексы в списке представляют собой столбцы. При создании объекта Graph необходимо указать количество узлов n, чтобы создать список списков. Затем мы можем получить доступ к соединению между узлами a и b с помощью self.graph[a][b].

        from typing import List

class Graph:
    def __init__(self, n: int):
        self.graph = [[0]*n for _ in range(n)]

    def connect(self, a: int, b: int) -> List[List[int]]:
        """
        Обновляем self.graph для соединения узлов A и B.
        """
        self.graph[a][b] = 1
        self.graph[b][a] = 1
        return self.graph

    def disconnect(self, a: int, b: int) -> List[List[int]]:
        """
        Обновляем self.graph для разъединения узлов A и B.
        """
        self.graph[a][b] = 0
        self.graph[b][a] = 0
        return self.graph
    

Воссоздать график из первого примера можно следующим образом:

        g = Graph(4)

# соединения A
g.connect(0, 1)
g.connect(0, 2)

# соединения B (исключая A)
g.connect(1, 2)

# соединения C (исключая B)
g.connect(2, 3)
    

Пример

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


Чтобы ответить на вопрос LC 323: Количество связных компонентов, изучим каждый узел графа. Далее «посетим» соседние графы. Повторяем операцию до тех пор, пока не встретим только те узлы, которые уже были замечены программой. После этого проверим наличие в графе узлов, которые еще не были замечены. Если такие узлы присутствуют, то существует еще как минимум один кластер, поэтому нужно взять новый узел и повторить процесс.

        def get_n_components(self, mat: List[List[int]]) -> int:
    """
    Учитывая матрицу смежности, возвращает количество связанных компонентов
    """
    q = []
    unseen = [*range(len(mat))]

    answer = 0

    while q or unseen:

        # Если все соседние узлы прошли через цикл, переходим к новому кластеру
        if not q:
            q.append(unseen.pop(0))
            answer += 1

        # Выбираем узел из текущего кластера
        focal = q.pop(0)
        i = 0

        # Поиск связей во всех оставшихся узлах
        while i < len(unseen):
            node = unseen[i]

            # Если узел подключен к центру, добавляем его в очередь
            # чтобы перебрать его соседей
            # из невидимых узлов и избежать бесконечного цикла
            if mat[focal][node] == 1:
                q.append(node)
                unseen.remove(node)
            else:
                i += 1

    return answer
    

Алгоритм действий:

  1. Строки 5-8: Создаем очередь (q), список узлов (unseen) и количество компонентов (answer).
  2. Строка 10: Запускаем цикл while, который выполняем до тех пор, пока в очереди есть узлы, которые нужно обработать или узлы, которые не были замечены.
  3. Строки 13-15: Если очередь пуста, удаляем первый узел из непросмотренных и увеличиваем количество компонентов.
  4. Строки 18-19: Выбираем следующий доступный узел в очереди (focal).
  5. Строка 22: Запускаем цикл while, который выполняем до тех пор, пока не обработаем все оставшиеся узлы.
  6. Строка 23: Даем имя текущему узлу для оптимизации кода.
  7. Строки 28-30: Если текущий узел подключен к центру, добавляем его в очередь узлов текущего кластера. Удаляем его из списка тех узлов, которые могут находиться в невидимом кластере. Благодаря этому действию, мы избегаем бесконечного цикла.
  8. Строки 31-32: Если текущий узел не подключен к focal (центру), переходим к следующему узлу.

Заключение

Графы и деревья – основные структуры данных. Спектр их применения огромен. Например, графы используются там, где необходим алгоритм поиска решений. Реальный пример их использования – sea-of-nodes JIT-компилятора.

Деревья используются тогда, когда мы должны произвести быстрое добавление/удаление объекта с поиском по ключу. Например, в различных словарях и индексах БД (Баз данных). Кроме того, деревья являются неотъемлемой частью случайного леса – алгоритма машинного обучения.

В следующей части материала мы приступим к изучению хэш-таблиц.

***

Базовый и продвинутый курс «Алгоритмы и структуры данных» включает в себя:

  1. Живые вебинары 2 раза в неделю.
  2. 47 видеолекций и 150 практических заданий.
  3. Консультации с преподавателями курса.

Материалы по теме

08
Июн
2022

❓ Зачем разработчику знать алгоритмы и структуры данных?

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

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

Алгоритмы в реальной жизни


Знание алгоритмов и тесно связанной с ними организации структуры данных необходимо для серьезной работы в любой отрасли информатики:

  1. Протоколы маршрутизации в коммуникационных сетях используют классические алгоритмы поиска кратчайшего пути.
  2. Шифрование с открытым ключом опирается на эффективные теоретико-числовые алгоритмы.
  3. Компьютерная графика задействует вычислительные примитивы, которые предоставляют геометрические алгоритмы.
  4. Индексация в базах данных опирается на структуры данных сбалансированных деревьев поиска.
  5. Вычислительная биология использует алгоритмы динамического программирования для измерения сходства геномов.

И так можно продолжать бесконечно.

Что дает знание алгоритмов рядовому разработчику


Освоение алгоритмов требует времени и усилий, но при этом дает несколько серьезных преимуществ:

  • Повышение эффективности. Существуют максимально быстрые алгоритмы для обработки данных и эффективные структуры для их организации. Такие паттерны избавляют от необходимости изобретать велосипед при решении типовых задач, позволяют прогнозировать производительность ПО и служат основой для разработки новых нетривиальных решений.
  • Развитие аналитических способностей и алгоритмического мышления. Изучение и реализация алгоритмов улучшают не только навыки программирования: привычка разбивать сложные задачи на логически связанные шаги, необходимые для их эффективного решения, пригодится везде – от планирования отпуска до разработки инвестиционной стратегии.
  • Успехи в спортивном программировании. Знание алгоритмов необходимо для успешного решения задач в контестах: как правило, из любого олимпиадного задания торчат уши какого-нибудь алгоритма. Вот всего лишь один пример: известная задача «Поле чудес» (Periodic Strings в англоязычном варианте) элементарно решается с помощью алгоритма Кнута-Морриса-Пратта. Стоит заметить, что олимпиадные задачи часто предлагают кандидатам на техническом собеседовании.
  • Успешное прохождение собеседований. Чем сложнее задачи, которые предстоит решать разработчикам компании, тем выше вероятность, что значительная часть вопросов будет посвящена алгоритмам и структурам данных. Работодатели отдают предпочтение кандидатам, которые способны найти самое эффективное и эргономичное решение проблемы.
  • Знакомство с величайшими достижениями информатики. Изучение алгоритмов и структуры данных похоже на просмотр дайджеста, состоящего из суперхитов информатики за последние 70 лет. В следующий раз, когда коллега пришлет мем про Дейкстру и его путь к подруге, будешь знать, в каком месте надо смеяться.
***

Если хочешь подтянуть свои знания по алгоритмам, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

  • углубишься в теорию структур данных;
  • научишься решать сложные алгоритмические задачи;
  • научишься применять алгоритмы и структуры данных при разработке программ.

С чего начать изучение алгоритмов

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

  1. Асимптотический анализ сложности алгоритмов. Лучший, средний и худший случаи. «O» большое и «o» малое. Очень часто на собеседованиях предлагают оценить сложность алгоритма или обосновать выбор в пользу определенного решения.
  2. Линейные структуры данных – массивы, стеки, связанные списки, хэш-таблицы и очереди.
  3. Нелинейные структуры данных – деревья, графы, множества.
  4. Рекурсия. Значительная часть алгоритмов использует рекурсию; она неразрывно связана с рекурсивно определяемыми структурами данных – деревьями, – и восходящим / нисходящим динамическим программированием.
  5. Концепция «разделяй и властвуй» и алгоритмы, основанные на ней – бинарный поиск, сортировка слиянием, быстрая сортировка, сортировка подсчетом, умножение Карацубы, субкубический алгоритм Штрассена, задача о паре ближайших точек. Такие алгоритмы разбивают исходную задачу на более мелкие подзадачи, рекурсивно решают их, а затем объединяют решения подзадач в решение исходной задачи.

После знакомства с азами пора переходить к темам, которые всплывают на большинстве собеседований: поиск и сортировка, жадные алгоритмы, графы (поиск в ширину и в глубину), динамическое программирование. Абсолютный минимум, который необходим для подготовки к техническому собеседованию, доступно и интересно изложен в книге Томаса Х. Кормена «Алгоритмы. Вводный курс». Исчерпывающий вариант – четырехтомник Тима Рафгардена «Совершенный алгоритм»:

  • в первой книге рассматриваются азы и базовые концепции;
  • во второй – графовые алгоритмы и структуры данных;
  • в третьей – жадные алгоритмы и динамическое программирование;
  • в четвертой – алгоритмы для NP трудных задач.

Материалы четырехтомника основаны на лекциях, которые Рафгарден читал в Стэнфордском университете и на онлайн-курсах, которые он ведет сейчас. Книги написаны вполне доступным языком и содержат множество практических заданий и тестов с решениями.

Алгоритмическая секция

Особенности технического собеседования варьируются в различных компаниях, но общие моменты выделить можно:

  • Кандидатам предлагают решить 5-6 задач разной степени сложности. На задачу можно потратить 15-45 минут – это очень мало. Поэтому с первого дня изучения алгоритмов нужно привыкать решать задачи – не только правильно, но и максимально быстро.
  • Часто решение приходится писать от руки – на листе бумаги или на доске. Так интервьюеру проще оценить, насколько последовательно и структурированно складывается решение в голове кандидата – чем меньше зачеркиваний и стираний, тем лучше.
  • При решении задач в IDE действуют лимиты по времени и памяти, как и в контестах спортивного программирования. Чтобы уложиться в лимиты, нужно учитывать не только быстродействие выбранного алгоритма, но и мелочи вроде небрежного считывания всех данных из огромного файла целиком (вместо одной нужной строчки).

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

***

Базовый и продвинутый курс «Алгоритмы и структуры данных» включает в себя:

  • Живые вебинары 2 раза в неделю.
  • 47 видеолекций и 150 практических заданий.
  • Консультации с преподавателями курса.
20
Апр
2022

➕ ➕ 7 способов сортировки массивов на примере С++ с иллюстрациями

В этой статье продемонстрируем на иллюстрациях, как работают алгоритмы сортировки: от простейшей пузырьковой до сложной древовидной кучи. Также определим сложность худших и лучших случаев, а код напишем на С++.

01
Мар
2022

🏠 Маст-хэв для каждого программиста: структурные шаблоны проектирования. Зачем нужны и когда их стоит использовать

В этой части мы рассмотрим применение основных структурных шаблонов – Адаптера, Моста, Компоновщика, Декоратора, Фасада, Легковеса и Заместителя.

Первая ча…

22
Фев
2022

🏗️ Поведенческие шаблоны проектирования: назначение, структура, примеры использования

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

В трех частях статьи мы последовательно рассмотрим 23 шаблона проектирования, которые впервые были перечислены в книге «Шаблоны проектирования: элементы объектно-ориентированного программного обеспечения». Описание каждого шаблона включает структуру, объяснение, рекомендации по использованию и пример практического применения. Первая часть посвящена поведенческим шаблонам, вторая – структурным, а третья – порождающим.

Основные типы шаблонов делятся на:

Поведенческие – используются для управления алгоритмами, отношениями и обязанностями между объектами. Примеры поведенческих шаблонов:

  • Цепочка обязанностей
  • Команда
  • Интерпретатор
  • Посредник
  • Хранитель
  • Наблюдатель
  • Состояние
  • Шаблонный метод
  • Посетитель

Структурные – используются для формирования больших объектных структур между многочисленными разрозненными объектами. Основные структурные шаблоны:

  • Адаптер
  • Мост
  • Компоновщик
  • Декоратор
  • Фасад
  • Легковес
  • Заместитель

Порождающие – используются для построения объектов таким образом, чтобы они могли быть отделены от реализующей их системы. Главные порождающие шаблоны:

  • Абстрактная фабрика
  • Строитель
  • Фабричный метод
  • Прототип
  • Одиночка

Поведенческий шаблон «Цепочка обязанностей»

Назначение

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

Когда использовать

  • Если запрос может быть обработан несколькими объектами, и обработчик не обязательно должен быть конкретным объектом.
  • Набор объектов должен быть способен обработать запрос с обработчиком, определяемым во время выполнения.
  • Если приемлемый потенциальный результат – оставить запрос без обработки.

Описание

<i>Шаблон "Цепочка обязанностей"</i>
Шаблон “Цепочка обязанностей”

Все обработчики реализуют один абстрактный класс Handler, который содержит ссылку на самого себя (successor) для делегирования обязанностей по обработке следующему обработчику в цепочке. Реализация метода handleRequest() по умолчанию выполняет такую делегацию.

Пример

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

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека программиста»

Поведенческий шаблон «Команда»

Назначение

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

Когда использовать

  • Если нужна функциональность обратного вызова.
  • Запросы должны обрабатываться в разное время или в разном порядке.
  • Необходимо сохранять историю запросов.
  • Если вызывающая сторона должна быть отделена от объекта, обрабатывающего вызов.

Структура

<i>Шаблон "Команда"</i>
Шаблон “Команда”

Клиент (Client) создает объекты конкретных команд. Отправитель (Invoker) хранит ссылку на объект команды и обращается к нему, если нужно выполнить какое-то действие. Отправитель работает с командами только через их общий интерфейс.

Команда (Command) описывает общий для всех конкретных команд (Concrete Command) интерфейс. Отправитель не знает, какую конкретно команду использует, так как получает готовый объект команды от клиента. Получатель (Receiver) содержит бизнес-логику программы.

Пример

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

Поведенческий шаблон «Интерпретатор»

Назначение

Определяет представление для грамматики, а также механизм для понимания и действий с грамматикой.

Когда использовать

  • Есть грамматика, которую нужно интерпретировать и которая может быть представлена в виде больших синтаксических деревьев.
  • Грамматика проста.
  • Эффективность не важна.
  • Желательно отделить грамматику от основных выражений.

Структура

<i>Шаблон "Интерпретатор"</i>
Шаблон “Интерпретатор”

Абстрактное выражение (Abstract Expression) объявляет метод Interpret(). Для каждого символа грамматики создается свой объект Terminal Expression (терминальное выражение). Для каждого отдельного правила грамматики создается свой объект Nonterminal Expression (нетерминальное выражение)

Контекст (Context) содержит общую информацию, может использоваться для сохранения состояния операций и последующего доступа к сохраненному состоянию. Клиент (Client) строит предложения с данной грамматикой в виде абстрактного синтаксического дерева, узлами которого являются объекты Terminal Expression и Nonterminal Expression.

Пример

Игры с текстовыми командами, популярные в 1980-х годах. Во многих из них были простые команды, например, «шаг вниз» , которые позволяли перемещаться по игре. Эти команды могли быть вложены друг в друга так, чтобы можно было изменить их значение. Например, результат выполнения go in «войти» отличался от go up «подняться». Создавая иерархию команд на основе команды и классификатора (нетерминальных и терминальных выражений), приложение могло легко соотнести множество вариантов команд с нужными действиями.

Поведенческий шаблон «Итератор»

Назначение

Позволяет получить доступ к элементам составного объекта без доступа к его внутреннему представлению.

Когда использовать

  • Требуется доступ к элементам без открытия доступа ко всему представлению.
  • Необходимы множественные или параллельные обходы элементов.
  • Нужен единый интерфейс для обхода.
  • Существуют небольшие различия между деталями реализации различных итераторов.

Структура

<i>Шаблон "Итератор"</i>
Шаблон “Итератор”

Итератор (Iterator) описывает интерфейс для доступа и обхода элементов коллекции. Конкретный итератор (Concrete Iterator) реализует алгоритм обхода какой-то конкретной коллекции.

Коллекция (Aggregate) описывает интерфейс получения итератора из коллекции. Конкретная коллекция (Concrete Aggregate) возвращает новый экземпляр определенного конкретного итератора, связав его с текущим объектом коллекции. Клиент работает со всеми объектами через интерфейсы коллекции и итератора.

Пример

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

Поведенческий шаблон «Посредник»

Назначение

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

Когда использовать

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

Структура

<i>Шаблон "Посредник'</i>
Шаблон “Посредник’

Посредник (Mediator) определяет интерфейс для обмена информацией с объектами Коллеги (Colleague). Конкретный посредник координирует действия объектов Коллеги. Каждый класс Коллеги знает о своем объекте Посредник, все Коллеги обмениваются информацией только с Посредником, не напрямую.

Пример

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

Поведенческий шаблон «Хранитель»

Назначение

Позволяет захватывать и извлекать внутреннее состояние объекта, чтобы его можно было восстановить позже, не нарушая инкапсуляции.

Когда использовать

  • Если внутреннее состояние объекта должно быть сохранено и восстановлено позднее.
  • Внутреннее состояние не может быть раскрыто интерфейсами без раскрытия реализации.
  • Границы инкапсуляции должны быть сохранены.

Структура

<i>Шаблон "Хранитель"</i>
Шаблон “Хранитель”

Создатель (Originator) делает снимки своего состояния и может воспроизводить прошлое состояние, если передать в него готовый снимок. Хранитель (Memento) — простой объект данных, содержащий состояние создателя. Опекун (Caretaker) знает, когда делать снимок создателя и когда его нужно восстанавливать.

Пример

С помощью «Хранителя» можно реализовать функцию отмены действия. Сериализуя и десериализуя состояние объекта до того, как произойдет изменение, можно сохранить снимок для последующего восстановления, если пользователь решит отменить операцию.

Поведенческий шаблон «Наблюдатель»

Назначение

Позволяет одному или нескольким объектам получать уведомления об изменениях состояния других объектов в системе.

Когда использовать

  • Если изменение состояния одного или нескольких объектов должно вызывать реакцию других объектов.
  • Нужно управлять массовой рассылкой.
  • Подписчики не платят за получение уведомлений.

Структура

<i>Шаблон "Наблюдатель"</i>
Шаблон “Наблюдатель”

Наблюдатель (Observer) передает запрос одновременно всем заинтересованным получателям (Concrete Subject), но позволяет им динамически подписываться или отписываться от таких оповещений.

Пример

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

Поведенческий шаблон «Состояние»

Назначение

Связывает обстоятельства объекта с его поведением, позволяя объекту вести себя по-разному в зависимости от его внутреннего состояния.

Когда использовать

  • Если поведение объекта должно зависеть от его состояния.
  • Поведение объекта с его состоянием связывают сложные условия.
  • Переходы между состояниями должны быть явными.

Структура

<i>Шаблон "Состояние"</i>
Шаблон “Состояние”

Контекст (Context) хранит ссылку на объект состояния и передает ему часть работы, зависящей от состояний. Состояние (State) описывает общий интерфейс для всех конкретных состояний. Конкретные состояния (Concrete State) реализуют поведения, связанные с определенным состоянием контекста.

Пример

Электронное письмо может иметь различные состояния, каждое из которых влияет на то, как объект обрабатывает различные функции. Если состояние «не отправлено», то вызов send() отправит сообщение, а вызов recallMessage() либо выдаст ошибку, либо ничего не сделает. Однако если состояние «отправлено», то вызов send() либо выдаст ошибку, либо ничего не сделает, а вызов recallMessage() попытается отправить уведомление получателям. Чтобы избежать условных выражений в большинстве или во всех методах, существует несколько объектов состояния, которые обрабатывают реализацию в соответствии со своим конкретным состоянием. Вызовы внутри объекта Email будут передаваться соответствующему объекту состояния для обработки.

Поведенческий шаблон «Стратегия»

Назначение

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

Когда использовать

  • Если единственное различие между многочисленными родственными классами заключается в их поведении.
  • Требуется несколько версий или вариаций алгоритма.
  • Алгоритмы получают доступ или используют данные, которые не должны быть доступны вызывающему коду.
  • Поведение класса должно определяться во время выполнения.
  • Условные операторы сложны и их трудно поддерживать.

Структура

<i>Шаблон "Стратегия"</i>
Шаблон “Стратегия”

Контекст (Context) хранит ссылку на объект конкретной стратегии и работает с ним через общий интерфейс стратегий. Стратегия (Strategy) определяет интерфейс, общий для всех вариаций алгоритма. Конкретные стратегии (Concrete Strategy) реализуют различные вариации алгоритма.

Пример

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

Поведенческий шаблон «Шаблонный метод»

Назначение

Определяет структуру алгоритма, позволяя реализующим классам определять фактическое поведение.

Когда использовать

  • Если необходима единая абстрактная реализация алгоритма.
  • Общее поведение среди подклассов должно быть локализовано в общем классе.
  • Родительские классы должны иметь возможность единообразно вызывать поведение в своих подклассах.
  • Большинство или все подклассы должны реализовать поведение.

Структура

<i>Шаблон "Шаблонный метод"</i>
Шаблон “Шаблонный метод”

Абстрактный класс (Abstract Class) определяет шаги алгоритма и содержит шаблонный метод, состоящий из вызовов этих шагов. Конкретный класс (Concrete Class) переопределяет некоторые (или все) шаги алгоритма. Конкретные классы не переопределяют сам шаблонный метод.

Пример

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

Поведенческий шаблон «Посетитель»

Назначение

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

Когда использовать

  • Если над структурой объекта выполняется множество несвязанных операций.
  • Структура объекта не должна меняться, но операции, выполняемые над ней, могут.
  • Операции должны выполняться над конкретными классами структуры объекта.
  • Раскрытие внутреннего состояния или операций структуры объекта допустимо.
  • Операции должны быть способны работать с несколькими структурами, реализующими одни и те же интерфейсные наборы.

Структура

<i>Шаблон "Посетитель"</i>
Шаблон “Посетитель”

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

Конкретные посетители (Concrete Visitor) реализуют какое-то особенное поведение для всех типов элементов. Элемент (Element) описывает метод принятия посетителя. Конкретные элементы (Concrete Element)реализуют методы принятия посетителя. Клиентом (Client) обычно является коллекция или сложный составной объект.

Пример

Расчет налогов в разных системах налогообложения по наборам счетов-фактур потребует множества различных вариантов логики расчета. Реализация шаблона «Посетитель» позволяет отделить логику от счетов-фактур. Это позволяет «посетить» иерархию элементов с помощью кода вычисления, который затем может применить соответствующие налоговые ставки. Сменить систему налогообложения в этом случае просто, достаточно сменить «Посетителя».

***

Материалы по теме

08
Фев
2022

🚄 Сравнение 6 алгоритмов сортировки: пузырьком, выбором, кучей, вставками, слиянием и быстрая

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

Все любят, когда данные отсортированы. Сортировка позволяет упорядочивать данные в нужной нам последовательности. В порядке возрастания и убывания. Представьте, что вы работаете в крупной компании и вам нужно отсортировать имена работников в зависимости от их зарплаты. Для этого используются алгоритмы сортировки.

Сегодня мы рассмотрим основные виды алгоритмов сортировки. Но сперва проясним, что из себя представляет сортировочный алгоритм.

Что такое алгоритм сортировки?

Сортировка больших объемов данных отнимает много сил и времени. Алгоритмы сортировки, как упоминалось ранее, позволяют облегчить выполнение этой задачи.

Алгоритмы сортировки позволяют упорядочить заданные списки и массивы данных с помощью операторов сравнения. Эти операторы применяются к элементам массива и определяют их последовательность в структуре данных.

К примеру, символы ниже идут в порядке возрастания согласно кодировке ASCII. В процессе сортировки идет сравнение элементов между собой. Чем выше значение символа в таблице ASCII, тем дальше от начала списка он будет расположен.


Какие существуют алгоритмы сортировки?

Существует множество различных алгоритмов. Сегодня мы рассмотрим 6 из них.

Сортировка пузырьком Один из простейших методов сортировки. Заключается в постепенном смещении элементов с большим значением в конец массива. Элементы последовательно сравниваются попарно, и если порядок в паре нарушен – меняются местами.
Сортировка выбором Алгоритм ищет наименьший элемент в текущем списке и производит обмен его значения со значением первой неотсортированной позиции. То же самое происходит со вторым элементом с наименьшим значением. Цикл повторяется до тех пор, пока все элементы не займут нужную последовательность.
Быстрая сортировка Считается одним из самых быстрых алгоритмов сортировки. Как и сортировка слиянием, работает по принципу «разделяй и властвуй». Временная сложность алгоритма может достигать O(n log n).
Сортировка кучей (Пирамидальная сортировка) Алгоритм выстраивает данные в виде двоичного дерева (двоичной кучи). Существует два варианта расположения элементов – max-heap (значение родителя больше значений потомков) и min-heap (значение родителя меньше значений потомков). Наибольший / наименьший элемент (в зависимости от типа) располагается в корне дерева. Он меняется местами с последним элементом кучи и помещается в конец массива. Размер кучи уменьшается на 1, после чего она перестраивается. Цикл повторяется, пока размер кучи больше 1.
Сортировка вставками Применяется для вставки элементов массива на «свое место». Сортировка вставками представляет собой простой метод сортировки и используется для раскладки колоды во время игры в бридж.
Сортировка слиянием Следует принципу «разделяй и властвуй», согласно которому массив данных разделяется на равные части, которые сортируются по-отдельности. После они сливаются, в результате получается отсортированный массив.

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


При неустойчивой сортировке элементы в массиве меняются местами.


Какие алгоритмы сортировки обеспечивают стабильность?

В таблице ниже представлена стабильность рассмотренных алгоритмов сортировки

Алгоритм сортировки Стабильность
Сортировка пузырьком
Сортировка выбором
Быстрая сортировка
Сортировка кучей
Сортировка вставками
Сортировка слиянием

Можно ли оценить эффективность алгоритмов сортировки?

Да, это возможно.

Критериями оценки эффективности алгоритма сортировки является пространственная и временная сложность.

Пространственная сложность

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

Вспомогательная память – дополнительное место, занимаемое алгоритмом помимо входных данных. Она учитывается при расчете пространственной сложности алгоритмов.

Временная сложность

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

  1. Нотация «Омега» (Ω)
  2. Нотация «O» большое (O)
  3. Нотация «Тета» (Θ)

В таблице представлена оценка сложности алгоритмов, упомянутых ранее

Алгоритм сортировки Время работы в худшем случае Время работы в среднем случае Время работы в лучшем случае Пространственная сложность
Сортировка пузырьком n^2 n^2 n 1
Сортировка выбором n^2 n^2 n^2 1
Быстрая сортировка n^2 nlog n nlog n nlog n
Сортировка кучей nlog n nlog n nlog n 1
Сортировка вставками n^2 n^2 n 1
Сортировка слиянием nlog n nlog n nlog n n
***

У каждого алгоритма сортировки своя временная и пространственная сложность. Использовать можно любой из представленных алгоритмов в зависимости от поставленных задач. Но по моему субъективному мнению лучшим алгоритмом является быстрая сортировка. Она позволяет выбрать опорный элемент и разделяет массив на 3 части: меньше, равно и больше опорного элемента.

Больше полезной информации вы можете найти на нашем телеграм-канале «Библиотека программиста»

Материалы по теме

20
Янв
2022

🔑 Просто о сложном: применение простых чисел в криптографии

Объясняем, почему простые числа важны в криптографии. Для этого мы рассмотрим конкретную криптосистему, а именно алгоритм RSA и сосредоточимся на его основных аспектах.

Свойства простых чисел

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

С другой стороны, вычислить значение гораздо легче, когда простые числа нам заранее известны:

Легко вычислить <code class="inline-code">x</code> из простых чисел 1 и 2. Но сложно вычислить простые числа 1 и 2 из <code class="inline-code">x</code>.
Легко вычислить x из простых чисел 1 и 2. Но сложно вычислить простые числа 1 и 2 из x.

В идеальных условиях у нас имеются два больших числа, которые являются простыми. Затем мы вычисляем произведение этих двух чисел, чтобы зашифровать сообщение. Позже, чтобы расшифровать его, нам нужно одно из данных простых чисел, потому что нет простого способа вычислить «Число 1» и «Число 2» исключительно по x. Перед тем как углубиться в детали использования данных чисел, давайте рассмотрим различные криптографические системы.

Криптографические системы

В криптографии существует два основных метода шифрования сообщений: симметричное и асимметричное.

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

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

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

С другой стороны, существует закрытый ключ, который виден только одному человеку – получателю сообщений. Он может использовать его для расшифровки полученных сообщений:

Публичный ключ → Автор сообщения → Зашифрованное сообщение → Получатель → Приватный ключ
Публичный ключ → Автор сообщения → Зашифрованное сообщение → Получатель → Приватный ключ

Используем простые числа для шифрования

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

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

Затем мы соединяем каждое число, чтобы создать другое (назовем его m), которое мы потом зашифруем. Самым простым примером списка является присвоение каждой букве ее позиции в алфавите, например, A – 1, Б – 2 и т. д. Несмотря на то, что данный список позволяет использовать только крайне простые слова, его достаточно для понимания теории, лежащей в основе RSA.

Создаем ключ

Как было ранее сказано, некоторое большое число легко вычислить при условии, что простые числа уже известны. С другой стороны, очень трудно определить множители (факторы) известного нам большого числа. Чтобы создать два ключа – закрытый и открытый, – мы осуществляем следующий процесс:

  1. Выберите два случайных, стохастически независимых и простых числа, p и q.
  2. Вычислите их произведение: N = p * q
  3. Далее вычислите φ-функцию: φ(N) = (p – 1) * (q – 1)
  4. Выберите простое натуральное число e, которое меньше значения φ(N) и является кратным по отношению к нему.
  5. Вычислите мультипликативную обратную величину k от e по модулю φ(N), то есть: e * k + d * φ(N) = 1

N и e теперь являются нашими открытыми ключами, которые будут использоваться для шифрования сообщения. Наш обратный ключ для расшифровки зашифрованного сообщения, k, является закрытым ключом. Для наилучшего понимания процесса, который стоит за названиями переменных, давайте рассмотрим процесс шифрования и дешифрования.

Шифрование и дешифрование сообщения

Теперь мы зашифруем наше сообщение m с помощью открытого ключа:

s≅memodN

И расшифруем его:

m≅skmodN

Из выражений выше следует, что мы можем инвертировать наше шифрование только если нам известна мультипликативная обратная k от e по модулю φ(N). Эти данные возможно получить, если у нас есть:

  1. Приватный (закрытый) ключ
  2. Простые множители N

Поскольку вычислить простые множители большого N физически невыполнимая задача, без закрытого ключа расшифровать сообщение невозможно. Это делает систему исключительно безопасной.

Практический пример

  • Создаем ключ.

Пусть буква, которую мы хотим зашифровать – O. Преобразуем ее в число m=15, так как это пятнадцатая буква латинского алфавита. Теперь мы выбираем случайные простые числа. Чтобы упростить задачу, выберем простые числа p = 13 и q = 17.

Таким образом, функция: φ(N) = (p – 1) * (q – 1) = 192

Мы также выбираем число e, которое кратно φ(N). Пусть это будет 29.

Осталось вычислить обратное k от e. С помощью алгоритма Евклида мы узнаем, что оно равно 53.

Таким образом, у нас есть открытый ключ N = p * q = 221 и закрытый ключ k = 53.

  • Шифрование и дешифрование сообщения.

Далее мы зашифруем наше число:

15≅s29mod221

Это дает s = 19. Теперь у нас есть зашифрованное сообщение, и мы можем безопасно передать его получателю. Никто не узнает, что оно обозначает букву O.

Теперь нам нужно наше обратное k, которое равно 53:

15≅1953mod221

После этого мы снова смотрим на алфавит и видим, что его пятнадцатая буква – это O. Таким образом, мы успешно зашифровали и расшифровали наше сообщение.

***

Из данного материала вы узнали об алгоритме RSA (Rivest, Shamir и Aldeman – создатели алгоритма) и о том, как правильно его применять для шифрования данных.

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

Материалы по теме

15
Дек
2021

👨‍🎓️ Алгоритмы и структуры данных на C++ для новичков. Часть 1: Основы анализа алгоритмов

Осваиваем основы анализа алгоритмов, которые потребуются любому начинающему программисту на C++ (и не только). Адекватное представление о времени выполнения кода может оказаться решающим фактором там, где производительность имеет большое значение.

Цель цикла
Этот цикл статей представляет собой краткое введение в алгоритмы и структуры данных. Будучи кратким руководством, он не является исчерпывающим пособием, а охватывает только самые важные темы. Целевая аудитория – читатели, желающие узнать об алгоритмах, но не имеющие времени на чтение книг, глубоко освещающих этот предмет. Например, серия должна заинтересовать читателей, готовящихся к предстоящему собеседованию. Статьи не требуют от читателя предварительной подготовки, связанную с алгоритмами и структурами данных, но определенные знания в программировании на C++ необходимы.

Что такое алгоритм?

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

Важность алгоритмов в информатике трудно переоценить. Они позволяют программисту реализовать эффективные, надежные и быстрые решения за короткий промежуток времени. Почти любые сложные программы на современных компьютерах в значительной степени опираются на алгоритмы. Операционные системы пользуются алгоритмами планирования, которые организуют и распределяют процессорное время между процессами, создавая иллюзию, что они выполняются одновременно. Многие умные алгоритмы, такие как растеризация, отсечение, back-face culling и сглаживание, служат для создания потрясающих 3D-миров в реальном времени. Алгоритмы позволяют найти кратчайший маршрут к месту назначения в городе, содержащем тысячи улиц. Благодаря алгоритмам машинного обучения произошла революция в таких областях, как распознавание изображений и речи. Перечисленные алгоритмы – это только вершина айсберга, и изучение этого предмета откроет множество дверей в карьере программиста.

Больше полезной информации вы найдете на нашем телеграм-канале «Библиотека программиста».

Пример алгоритма

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








Здесь отсортированный подмассив выделен синим цветом. Данная диаграмма не показывает, как именно сортировка вставками перемещает элементы из несортированного подмассива в сортированный. Она вставляет элемент в отсортированный подмассив следующим образом:

  • Сохраняет значение элемента во временной переменной;
  • Перемещает все элементы, которые больше чем вставляемый элемент (расположенные перед этим элементом) на одно место вправо;
  • Помещает значение временной переменной в освободившееся место.

Давайте подробнее рассмотрим этот процесс на примере:


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


Мы сравниваем 4 с 7, и поскольку 7 больше, мы копируем его на позицию справа (значения, которые мы сравниваем с вставляемым элементом, обозначены фиолетовым).


Сравниваем 4 с 6, и поскольку 6 больше, копируем его на позицию справа.


Сравниваем 4 с 5, а поскольку 5 тоже больше чем 4, его тоже копируем его на позицию справа.


Наконец, мы сравниваем 4 с 3, и так как 3 меньше чем 4, мы присваиваем значение временной переменной на позицию рядом с ним. И теперь наша работа выполнена; мы расположили 4 в правильное положение.

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

PseudocodeInsertionSort
        n ← Array.size
For i=2 to n
    j ← i – 1
    temp ← Array[j]
    While Array[j-1]>temp and j>0
        Array[j] ← Array[j-1];
        j ← j-1
    Array[j] ← temp

    

Написание алгоритмов в псевдокоде порой бывает полезным, но поскольку эти статьи посвящены алгоритмам на C++, в дальнейшем мы сосредоточимся на реализации алгоритмов на C++. Пример программы на C++, которая реализует сортировку вставками:

InsertionSort.cpp
        void insertionSort(int *array, int n)
{
    for(int i=2;i<=n;++i)
    {
        int j=i-1;
        int temp = array[j];
        while(array[j-1]>temp)
        {
            array[j]=array[j-1];
            --j;
        }
        array[j]=temp;
    }
}

    

Основы анализа

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

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

Абстрактная модель машины

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

Асимптотический анализ

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

Те же вопросы можно задать и о производительности алгоритма в различных условиях. Для большинства алгоритмов размер входных данных не является единственным фактором, но особенности входных данных также влияют на время выполнения. В качестве примера можно привести линейный поиск. Это простой алгоритм для нахождения элемента в списке. Он последовательно проверяет каждый элемент списка до тех пор, пока не обнаружит совпадение или пока не просмотрит весь список. Очевидно, что время работы этого алгоритма может резко отличаться для списков с одинаковым размером n. В лучшем случае, если искомый элемент является первым в списке, алгоритму требуется только одно сравнение. С другой стороны, если в списке отсутствует нужный элемент или он оказался последним, алгоритм выполнит ровно n сравнений. В целом, при анализе используется один из следующих двух подходов: либо можно считать входные данные случайными и анализировать среднюю производительность, либо мы можно подобрать худшие входные данные и исследовать наихудшую производительность. В этой серии статей мы будем придерживаться анализа наихудшего случая, поскольку это гарантирует, что для любого примера входных данных размера n время работы не превысит полученного предела. Кроме того, как мы определяем “средние” данные, может повлиять на результат анализа.

«O» большое

АсимптотическийанализпозволяетоценитьпроизводительностьалгоритмасточкизрениятогокаквремяилипамятьзанимаемоеалгоритмомувеличиваетсясвозрастаниемколичествавходныхданныхВасимптотическихобозначенияхиспользуетсяфункциядляописанияотношениямеждупроизводительностьюалгоритмаиразмеромзадачикогдаонастановитсябольшойВсвязискороткимхарактеромстатьимыограничимсятолькобольшиминезатронеммногиенюансыасимптотическогоанализаГоворяпростымязыкомеслисложностьалгоритмаравнаэтоозначаетчтовремяработыувеличиваетсякакквадратразмеравходныхданныхТакимобразомеслиразмервходныхданныхравенвремявыполненияприблизительносоставляетДругимисловамиесливыудвоитеразмервходныхданныхтовремявыполнениявозрастетпримерновчетыреразаНижеприведеныосновныеправиладлявычислениябольшогоалгоритмаАсимптотический анализ позволяет оценить производительность алгоритмас точки зрения того, как время (или память), занимаемое алгоритмом,увеличивается с возрастанием количества входных данных. В асимптотическихобозначениях используется функция для описания отношения междупроизводительностью алгоритма и размером задачи, когда она становится большой.В связи с коротким характером статьи мы ограничимся только большим “O” и незатронем многие нюансы асимптотического анализа. Говоря простым языком, еслисложность алгоритма равна O(n2), это означает, что время работы увеличивается какквадрат размера входных данных n. Таким образом, если размер входных данныхравен n, время выполнения приблизительно составляет n2. Другими словами, есливы удвоите размер входных данных, то время выполнения возрастет примерно вчетыре раза. Ниже приведены основные правила для вычисления большого “O”алгоритма:
ЕслиалгоритмтребуетпримитивныхоперацийтоонимеетсложностьЕслиалгоритмвыполняетоперациюкотораязанимаетразтопроизводительностьалгоритмасоставляетЕслиалгоритмимеетсложностьгдеконстантатоегосложностьможноупроститьдоИначеговоряконстантыможноопускатьЕслиалгоритмвыполняетоперациюкотораязанимаетшаговазатемвыполняетдругуюпроцедурукотораязанимаетшаговтообщаяпроизводительностьалгоритмаравнаЕслиалгоритмимеетсложностьприэтомдлябольшихтоегосложностьможноупроститьдо1. Если алгоритм требует f(n) примитивных операций, то он имеетсложность O(f(n)).2. Если алгоритм выполняет операцию, которая занимает f(n), g(n) раз, топроизводительность алгоритма составляет O(f(n)∗g(n)).3. Если алгоритм имеет сложность cO(f(n)), где c – константа, то егосложность можно упростить до O(f(n)). Иначе говоря, константы можноопускать.4. Если алгоритм выполняет операцию, которая занимает O(f(n)) шагов, азатем выполняет другую процедуру, которая занимает O(g(n)) шагов, тообщая производительность алгоритма равна O(f(n)+g(n)).5. Если алгоритм имеет сложность O(f(n)+g(n)) при этом g(n)<f(n), длябольших n, то его сложность можно упростить до O(f(n)).

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

Пример правила 1: Взгляните на реализацию алгоритма, который вычисляет сумму всех элементов в массиве, на языке C++.

sum.cpp
        int sum(int* array, int n)
{
    int sum = 0;
    for(int i=0;i<n;++i)
    {
        sum+=array[i];
    }
    return sum;
}

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

Пример правил 2 и 3: Приведенная ниже программа складывает две квадратные матрицы.

matrixAddition.cpp
        void matrixAddition(int** m1, int** m2, int** dest, int n)
{
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            dest[i][j]=m1[i][j]+m2[i][j];
        }
    }
}

    
ЭтоталгоритмсостоитиздвухвложенныхцикловВнутреннийциклвыполняетитерацийпричемкаждыйшагсостоитиздвухпростыхдействийсложенияиприсваиванияПрименяяправиломожносделатьвыводчтосложностьвнутреннегоцикларавнаВнешнийциклтакжеделаетитерацийновместоиспользованияпростыхоперацийонзапускаетвнутреннийциклПовторноприменивправиломызаключаемчтовнешнийциклазначитиалгоритмимеетсложностьТакжепоправилуможноизбавитьсяотконстантыиполучитьКонстантныемножителиможноопуститьпосколькуониневлияютнаасимптотическоеповедениеалгоритмаОднакоониимеютбольшоепрактическоезначениепосколькуалгоритмстойжесложностьюновдвоебыстреевсегдапредпочтительнееЭтот алгоритм состоит из двух вложенных циклов. Внутренний цикл выполняет nитераций, причем каждый шаг состоит из двух простых действий: сложения иприсваивания. Применяя правило 2, можно сделать вывод, что сложностьвнутреннего цикла равна O(2n). Внешний цикл также делает n итераций, но вместоиспользования простых операций он запускает внутренний цикл. Повторноприменив правило 2, мы заключаем, что внешний цикл (а значит и алгоритм) имеетсложность O(n∗2∗n)=(2n2). Также по правилу 3 можно избавиться от константы,и получить O(n2). Константные множители можно опустить, поскольку они невлияют на асимптотическое поведение алгоритма. Однако они имеют большоепрактическое значение, поскольку алгоритм с той же сложностью, но вдвое быстрее,всегда предпочтительнее.

Пример правил 4 и 5: Обратите внимание на программу ниже

function.cpp
        void function(int** dest, int n)
{
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            dest[i][j]=1;
        }
    }

    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            for(int k = 0; k < n; ++k)
            {
                dest[i][j]=2;
            }
        }
    }
}
    
ЭтапроцедуравыполняетдваждывложенныйциклссуммарнойсложностьюазатемтриждывложенныйциклсосложностьюВсоответствиисправиломсложностьалгоритмасоставляетАпосколькубольшечеммыможемуменьшитьсложностьдоприменивправилоСматематическойточкизренияутверждениечтооднафункциябольшедругойнеимеетсмыслаВалгоритмическоманализеозначаетчтостановитсянезначительнойпосравнениюскогдастановитсяоченьбольшойПоэтомуговорятчтоиасимптотическиэквивалентныаможноудалятьНеобращаявниманиянаменьшиефункциимыможемизбежатьанализамелкихзадачпоподготовкеиочисткипрограммыисосредоточитьсянаасимптотическомповеденииприувеличениивходныхданныхТемнеменеепрактическоевремяработыалгоритмаиногдаможетзначительноотличатьсяотеготеоретическогоповеденияРассмотримдваалгоритмапервыйизкоторыхимеетсложностьивыполняетреальныхшаговСложностьвторогоалгоритмасоставляетанапрактикетребуетоперацийНесмотрянаточтоасимптотическаясложностьпервогоалгоритмадовольнонизкаяонбудетвыполнятьсянамногомедленнееесливходныеданныенеоченьбольшиеЭта процедура выполняет дважды вложенный цикл с суммарной сложностью O(n2),а затем трижды вложенный цикл со сложностью O(n3). В соответствии с правилом 4сложность алгоритма составляет O(n3+n2). А поскольку n3 больше, чем n2, мыможем уменьшить сложность до O(n3), применив правило 5. С математическойточки зрения, утверждение, что одна функция больше другой, не имеет смысла. Валгоритмическом анализе f(n)<g(n) означает, что g(n) становитсянезначительной по сравнению с f(n), когда n становится очень большой. Поэтомуговорят, что f(n)+g(n) и f(n) асимптотически эквивалентны, а g(n) можноудалять. Не обращая внимания на меньшие функции, мы можем избежать анализамелких задач по подготовке и очистки программы и сосредоточиться наасимптотическом поведении при увеличении входных данных. Тем не менее,практическое время работы алгоритма иногда может значительно отличаться от еготеоретического поведения. Рассмотрим два алгоритма, первый из которых имеетсложность O(log⁡n), и выполняет log⁡n+1000000000 реальных шагов.Сложность второго алгоритма составляет O(n2), а на практике требует n2+10операций. Несмотря на то, что асимптотическая сложность первого алгоритмадовольно низкая, он будет выполняться намного медленнее, если входные данныене очень большие.

Часто встречающиеся функции времени выполнения

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

ЕслиалгоритмвыполняетодинаковоеколичествооперацийвнезависимостиотразмеравходныхданныхонимеетсложностьКогдасложностьалгоритмалогарифмическаяпрограммастановитсялишьнемногомедленнеепомереростаПриумноженииразмеравходныхданныхнакоэффициентоснованиялогарифмавремявыполненияувеличиваетсятольконаконстантуЧтобыпонятьнасколькомедленнорастетвремявыполненияподумайтеотомсколькобиттребуетсядляхраненияПосколькуэтоколичестворавнологарифмическоевремяработыпропорциональночислубитовиспользуемыхдляхраненияПриумножениидиапазонанадвачислобитовувеличиваетсянаединицуАналогичноприувеличенииразмеравходныхданныхвдваразавремяработыувеличиваетсянаединицуНапримеркогдаразмервходныхданныхравенмиллиардувремявыполненияравноакогдаразмервходныхданныхравендвуммиллиардамонаравноПосколькугдеконстантаоснованиелогарифмавнотациибольшого«О»обычноопускаетсяЛогарифмическоевремяработыхарактернодляпрограммкоторыепреобразуютбольшуюзадачувсериюменьшихзадачкаждыйшагкоторыхделитразмерзадачинапостояннуювеличинуПримеромалгоритмаимеющеготакуюсложностьявляетсядвоичныйпоискДвоичныйпоискэтоэффективныйметоднахожденияэлементавотсортированномспискеОнработаетпутемсравненияцелевогозначениясэлементомвсерединеПосколькусписокотсортированискомыйэлементдолженнаходитьсясправаеслицелевоезначениебольшесреднегоэлементаЕслизначениеискомогоэлементаменьшетоондолженбытьслеваЭтознаниепозволяетисключитьполовинуискомойобластивкаждойитерацииЕсливремявыполненияпрограммыявляетсялинейнымтообычнокаждыйвходнойэлементподвергаетсяобработкеспостояннойсложностьюКогдаравномиллионувремяработытакжеравняетсямиллионуЕслиудваиваетсявремяработытакжеудваиваетсяДляалгоритмакоторыйдолженобработатьвсеисходныхданныхтакаяситуацияявляетсяоптимальнойНахождениенаибольшегоэлементавнесортированномспискеявляетсяпримеромтакойслучаяприкоторомкаждыйэлементрассматриваетсяисравниваетсястекущиммаксимумомрастетбыстреечемлинейнаяфункцияноненамногоТакаясложностьобычновозникаеткогдаалгоритмразбиваетпроблемунаподзадачирешаетихиобъединяетрешенияЭтотподходкразработкеалгоритмовназываетсяразделяйивластвуйявляетсяоптимальнымдляалгоритмовсортировкинаосновесравненияВдальнейшеммыболееподробнорассмотрималгоритмыразделяйивластвуйиалгоритмысортировкиO(1) – Если алгоритм выполняет одинаковое количество операций в независимости от размера входных данных, он имеет сложность O(1).O(log⁡n)−Когда сложность алгоритма логарифмическая, программа становится лишьнемного медленнее по мере роста n. При умножении размера входных данных накоэффициент основания логарифма время выполнения увеличивается только на константу.Чтобы понять, насколько медленно растет время выполнения, подумайте о том, сколькобит требуется для хранения n. Поскольку это количество равно ⌈log2⁡⁡(n+1)⌉, логарифмическое время работы пропорционально числу битов, используемыхдля хранения n. При умножении диапазона на два число битов увеличивается наединицу. Аналогично, при увеличении размера входных данных в два раза времяработы увеличивается на единицу. Например, когда размер входных данныхравен миллиарду, время выполнения равно 30, а когда размер входных данных равендвум миллиардам, она равно 31. Поскольку logb⁡⁡n=loga⁡⁡nloga⁡⁡b, где 1logb⁡⁡a -константа, основание логарифма в нотации большого «О» обычно опускается.Логарифмическое время работы характерно для программ, которые преобразуютбольшую задачу в серию меньших задач, каждый шаг которых делит размер задачина постоянную величину. Примером алгоритма, имеющего такую сложность,является двоичный поиск. Двоичный поиск – это эффективный метод нахожденияэлемента в отсортированном списке. Он работает путем сравнения целевогозначения с элементом в середине. Поскольку список отсортирован, искомый элементдолжен находиться справа, если целевое значение больше среднего элемента. Еслизначение искомого элемента меньше, то он должен быть слева. Это знание позволяетисключить половину искомой области в каждой итерации.O(n) – Если время выполнения программы является линейным, то обычно каждыйвходной элемент подвергается обработке с постоянной сложностью. Когда n равномиллиону, время работы также равняется миллиону. Если n удваивается, времяработы также удваивается. Для алгоритма, который должен обработать все nисходных данных, такая ситуация является оптимальной. Нахождение наибольшегоэлемента в несортированном списке является примером такой случая, при которомкаждый элемент рассматривается и сравнивается с текущим максимумом.O(nlog⁡n) – O(nlog⁡n) растет быстрее чем линейная функция, но ненамного. Такаясложность обычно возникает, когда алгоритм разбивает проблему на подзадачи,решает их и объединяет решения. Этот подход к разработке алгоритмов называется “разделяй и властвуй”. O(nlog⁡n) является оптимальным для алгоритмов сортировкина основе сравнения. В дальнейшем мы более подробно рассмотрим алгоритмы”разделяй и властвуй” и алгоритмы сортировки.
ВслучаекогдаалгоритмперебираетвсевходныеданныеинакаждойитерацииперебираетихсноваонимеетквадратичнуюсложностьВкачествепримерарассмотримпрограммукотораявыводитвсевозможныепарыизэлементовмассиваO(n2) – В случае, когда алгоритм перебирает все входные данные и на каждойитерации перебирает их снова, он имеет квадратичную сложность. В качествепримера рассмотрим программу, которая выводит все возможные пары из элементовмассива:
displayPairs
        void displayPairs(int* array, int n)
{
    int count = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            count++;
            cout<< "Pair #"<<count<<':'<< array[i] <<'-' << array[j] <<endl;
        }
    }
}

    
ЧтобыотобразитьвсепарыкаждыйэлементмассивадолженбытьсопряженскаждымдругимэлементомАлгоритмысквадратичнойсложностьюпрактичнытолькоприсреднихилималыхразмерахвходныхданныхКогдасложностьалгоритмаравнагдеконстантаговорятчтоонимеетполиномиальноевремявыполненияВэтукатегориювходятлинейныеквадратичныекубическиеидажесложностьНаделеполиномиальныевременавыполнениявысокогопорядкавстречаютсяредконоонибыстреечемэкспоненциальныеифакториальныевременавыполненияЧтобы отобразить все пары, каждый элемент массива должен быть сопряжен скаждым другим элементом. Алгоритмы с квадратичной сложностью практичнытолько при средних или малых размерах входных данных. Когда сложностьалгоритма равна O(nk), где k – константа, говорят, что он имеет полиномиальноевремя выполнения. В эту категорию входят линейные, квадратичные, кубические идаже сложность O(n100). На деле, полиномиальные времена выполнения высокогопорядка встречаются редко, но они быстрее, чем экспоненциальные ифакториальные времена выполнения.
НесмотрянаточтотакиеалгоритмывозникаютестественнымобразомприрешениимногихзадачметодомпереборалишьнемногиеалгоритмысэкспоненциальнымвременемработыпригодныдляпрактическогоиспользованияпосколькуонирастутчрезвычайнобыстроПридобавленииодноговходногоэлементавремявыполненияудваиваетсяСамособойразумеетсячтотакиеалгоритмыбесполезныеслитолькоразмервходныхданныхнеоченьмалПрограммырешающиезадачуоранцеявляютсяпримерамиалгоритмовсэкспоненциальнойпроизводительностьюВпростейшейвариацииэтойзадачидаютсяпредметовимеющихвесиценностьирюкзаксограниченнойвместимостьюВашацельуложитькакможнобольшоечислоценныхвещейврюкзакКаждыйпредметаимеетдвасостоянияпредметкладётсяврюкзаклибопредметнекладётсяТакимобразомсуществуеткомбинацийиалгоритмунужностолькожешаговчтобыперебратьихO(2n) – Несмотря на то, что такие алгоритмы возникают естественным образом при решении многих задач методом перебора, лишь немногие алгоритмы с экспоненциальным временем работы пригодны для практического использования, поскольку они растут чрезвычайно быстро. При добавлении одного входного элемента время выполнения удваивается! Само собой разумеется, что такие алгоритмы бесполезны, если только размер входных данных не очень мал. Программы, решающие задачу о ранце, являются примерами алгоритмов с экспоненциальной производительностью. В простейшей вариации этой задачи даются n предметов, имеющих вес и ценность и рюкзак, с ограниченной вместимостью. Ваша цель – уложить как можно большое число ценных вещей в рюкзак. Каждый предмета имеет два состояния: предмет кладётся в рюкзак, либо предмет не кладётся. Таким образом, существует 2n комбинаций, и алгоритму нужно столько же шагов, чтобы перебрать их.
ФакториалсамаябыстрорастущаясложностькоторуювстречаетсянапрактикеЭтафункциярастетгораздобыстреечемдажеэкспоненциальнаяфункцияДлясравнениякогдаразмервходныхданныхсоставляетвсеготоколичествовыполняемыхоперацийпревышаетколичествоатомоввобозримойВселеннойБольшинствоалгоритмовсфакториальнойсложностьюрасставляютвходныеданныевоптимальномпорядкеЕслиестьсвязанныхгородовзадачаПутешествиекоммивояжерапроситваспроложитьмеждунимикратчайшийзамкнутыймаршрутпроходящийчерезкаждыйгородтолькоодинразСамыйочевидныйспособперебратьвсевозможныевариантыЕсливсегородасвязанымеждусобойдвагородасвязаныеслиизодногоположенодорогавдругойтоувасестьвариантовдлявыборапервогогородавмаршрутедлявторогодлятретьегоитакдалееТакимобразомобщееколичествокомбинацияравноO(n!) – Факториал – самая быстрорастущая сложность, которую встречается напрактике. Эта функция растет гораздо быстрее, чем даже экспоненциальная функция.Для сравнения, когда размер входных данных составляет всего 62, то количествовыполняемых операций превышает количество атомов в обозримой Вселенной!Большинство алгоритмов с факториальной сложностью расставляют входныеданные в оптимальном порядке. Если есть n связанных городов, задача “Путешествиекоммивояжера”, просит вас проложить между ними кратчайший замкнутый маршрут,проходящий через каждый город только один раз. Самый очевидный способ -перебрать все возможные варианты. Если все города связаны между собой (двагорода связаны, если из одного положено дорога в другой), то у вас есть n вариантовдля выбора первого города в маршруте, n−1 для второго, n−2 для третьего и так далее.Таким образом, общее количество комбинация равно n!

Визуализация функций

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


На приведенном ниже изображении показаны графики
распространенных функций времени выполнения.


Заключение

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

25
Ноя
2021

🤖 Решаем задачи машинного обучения с помощью алгоритма градиентного бустинга

Градиентный бустинг (Gradient Boosting) – один из самых эффективных инструментов для решения задач машинного обучения, в особенности на соревнованиях Kaggle. Чтобы научиться правильно его применять, разберем подробнее лежащие в основе алгоритма процессы.

Градиентный бустинг – это продвинутый алгоритм машинного обучения для решения задач классификации и регрессии. Он строит предсказание в виде ансамбля слабых предсказывающих моделей, которыми в основном являются деревья решений. Из нескольких слабых моделей в итоге мы собираем одну, но уже эффективную. Общая идея алгоритма – последовательное применение предиктора (предсказателя) таким образом, что каждая последующая модель сводит ошибку предыдущей к минимуму.

Предположим, что вы играете в гольф. Чтобы загнать мяч в лунĸу, вам необходимо замахиваться клюшкой, каждый раз исходя из предыдущего удара. То есть перед новым ударом гольфист в первую очередь смотрит на расстояние между мячом и лунĸой после предыдущего удара, так как наша основная задача – при следующем ударе уменьшить это расстояние.

Бустинг строится таким же способом. Для начала, нам нужно ввести определение “лунĸи”, а именно цели, которая является конечным результатом наших усилий. Далее необходимо понимать, куда нужно “бить ĸлюшĸой”, для попадания ближе ĸ цели. С учётом всех этих правил нам необходимо составить правильную последовательность действий, чтобы ĸаждый последующий удар соĸращал расстояние между мячом и лунĸой.

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

Больше полезной информации вы найдете на нашем телеграм-канале «Библиотека data scientist’а».

Параметры алгоритма

  • criterion – критерий выбора расщепления, Mean Absolute Error (MAE) или Mean Squared Error (MSE). Используется только при построении деревьев.
  • init – какой алгоритм мы будем использовать в качестве главного (именно его и улучшает техника бустинга).
  • learning_rate – скорость обучения.
  • n_estimators – число итераций в бустинге. Чем больше, тем лучше качество, однако слишком большой увеличение данного параметра может привести к ухудшению производительности и переобучению.
  • min_samples_split – минимальное число объектов, при котором происходит расщепление. С данным параметром мы можем избежать переобучение.
  • min_samples_leaf – минимальное число объектов в листе (узле). При увеличении данного параметра качество модели на обучении падает, в то время как время построения модели сокращается. Меньшие значения стоит выбирать для менее сбалансированных выборок.
  • max_depth – максимальная глубина дерева. Используется для того, чтобы исключить возможность переобучения.
  • max_features – количество признаков, учитываемых алгоритмом для построения расщепления в дереве.
  • max_leaf_nodes : Максимальное число верхних точек в дереве. При наличии данного параметра max_depth будет игнорироваться.

Реализация на языке python (библиотека sklearn)

        ### Загружаем библиотеки и данные
import pandas as pd
import numpy as np
from sklearn.ensemble import GradientBoostingRegressor
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler,LabelEncoder
from sklearn.datasets import load_breast_cancer
from sklearn.metrics import mean_squared_error,r2_score 

import warnings
warnings.filterwarnings('ignore')
breast_cancer = load_breast_cancer()


### Обозначаем целевую переменную для нашей будущей модели
X = pd.DataFrame(breast_cancer['data'], columns=breast_cancer['feature_names'])
y = pd.Categorical.from_codes(breast_cancer['target'], breast_cancer['target_names'])

lbl = LabelEncoder() 
lbl.fit(y)

y_enc = lbl.transform(y)


### Разбираемся с признаками
scl = StandardScaler()
scl.fit(X)
X_scaled = scl.transform(X)

X_train, X_test, y_train, y_test = train_test_split(X, y_enc, test_size=0.20, random_state=42)


### Прописываем параметры для нашей модели 
params = {'n_estimators':200,
          'max_depth':12,
          'criterion':'mse',
          'learning_rate':0.03,
          'min_samples_leaf':16,
          'min_samples_split':16
          }


### Тренируем
gbr = GradientBoostingRegressor(**params)
gbr.fit(X_train,y_train)


### Вычисляем точность
train_accuracy_score=gbr.score(X_train,y_train)
print(train_accuracy_score)

test_accuracy_score=gbr.score(X_test,y_test)
print(test_accuracy_score)

### Предсказание
y_pred = gbr.predict(X_test)

### И среднеквадратичную ошибку
mse = mean_squared_error(y_test,y_pred)
print("MSE: %.2f" % mse)
print(r2_score(y_test,y_pred))
    

Результат работы кода:

        0.9854271477118486
0.8728770740774442
MSE: 0.03
0.8728770740774442
    

Базовая модель градиентного бустинга с несложной простой настройкой дает нам точность более чем в 95% на задаче регрессии.

Какие библиотеки использовать?

Помимо классической для машинного обучения sklearn, для алгоритма градиентного бустинга существуют три наиболее используемые библиотеки:

XGBoost – более регуляризованная форма градиентного бустинга. Основным преимуществом данной библиотеки является производительность и эффективная оптимизация вычислений (лучший результат с меньшей затратой ресурсов).

Вы можете установить XGBoost следующим образом:

        pip install xgboost
    

Библиотека XGBoost предоставляем нам разные классы для разных задач: XGBClassifier для классификации и XGBregressor для регрессии.

Примечание
Все приведенные ниже библиотеки имеют отдельные классы для задач как классификации, так и регрессии.

  • Пример использования XGBoost для классификации:
        # xgboost для классификации
from numpy import asarray
from numpy import mean
from numpy import std
from sklearn.datasets import make_classification
from xgboost import XGBClassifier
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import RepeatedStratifiedKFold
# определяем датасет
X, y = make_classification(n_samples=1000, n_features=10, n_informative=5, n_redundant=5, random_state=1)
# и нашу модель вместе с кросс-валидацией
model = XGBClassifier()
cv = RepeatedStratifiedKFold(n_splits=10, n_repeats=3, random_state=1)
n_scores = cross_val_score(model, X, y, scoring='accuracy', cv=cv, n_jobs=-1, error_score='raise')
print('Точность: %.3f (%.3f)' % (mean(n_scores), std(n_scores)))
# тренируем модель на всём наборе данных
model = XGBClassifier()
model.fit(X, y)
# предсказываем
row = [2.56999479, -0.13019997, 3.16075093, -4.35936352, -1.61271951, -1.39352057, -2.48924933, -1.93094078, 3.26130366, 2.05692145]
row = asarray(row).reshape((1, len(row)))
yhat = model.predict(row)
print('Предсказание (Предикт): %d' % yhat[0])
    
  • Пример использования XGBoost для регрессии:
        # xgboost для регрессии
from numpy import asarray
from numpy import mean
from numpy import std
from sklearn.datasets import make_regression
from xgboost import XGBRegressor
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import RepeatedKFold
# определяем датасет
X, y = make_regression(n_samples=1000, n_features=10, n_informative=5, random_state=1)
# и нашу модель (в данном примере мы меняем метрику на MAE)
model = XGBRegressor(objective='reg:squarederror')
cv = RepeatedKFold(n_splits=10, n_repeats=3, random_state=1)
n_scores = cross_val_score(model, X, y, scoring='neg_mean_absolute_error', cv=cv, n_jobs=-1, error_score='raise')
print('MAE (Средняя Абсолютная Ошибка): %.3f (%.3f)' % (mean(n_scores), std(n_scores)))
# тренируем модель на всём наборе данных
model = XGBRegressor(objective='reg:squarederror')
model.fit(X, y)
# предсказываем
row = [2.02220122, 0.31563495, 0.82797464, -0.30620401, 0.16003707, -1.44411381, 0.87616892, -0.50446586, 0.23009474, 0.76201118]
row = asarray(row).reshape((1, len(row)))
yhat = model.predict(row)
print('Предсказание (Предикт): %.3f' % yhat[0])

    
LightGBM – библиотека от Microsoft. В ней идет добавление авто выбора объектов и фокуса на тех частях бустинга, в которых мы имеем больший градиент. Это способствует значительному ускорению в обучении модели и улучшению показателей предсказания. Основная сфера применения – соревнования с использованием табличных данных на Kaggle.

Вы можете установить LightGBM также при помощи pip:

        pip install lightgbm
    
  • LightGBM для классификации:
        # lightgbm для классификации
from numpy import mean
from numpy import std
from sklearn.datasets import make_classification
from lightgbm import LGBMClassifier
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import RepeatedStratifiedKFold
# определяем датасет
X, y = make_classification(n_samples=1000, n_features=10, n_informative=5, n_redundant=5, random_state=1)
# и нашу модель
model = LGBMClassifier()
cv = RepeatedStratifiedKFold(n_splits=10, n_repeats=3, random_state=1)
n_scores = cross_val_score(model, X, y, scoring='accuracy', cv=cv, n_jobs=-1, error_score='raise')
print('Точность: %.3f (%.3f)' % (mean(n_scores), std(n_scores)))
# тренируем модель на всём наборе данных
model = LGBMClassifier()
model.fit(X, y)
# предсказываем
row = [[2.56999479, -0.13019997, 3.16075093, -4.35936352, -1.61271951, -1.39352057, -2.48924933, -1.93094078, 3.26130366, 2.05692145]]
yhat = model.predict(row)
print('Предсказание (Предикт): %d' % yhat[0])
    
  • LightGBM для регрессии:
        # lightgbm для регрессии
from numpy import mean
from numpy import std
from sklearn.datasets import make_regression
from lightgbm import LGBMRegressor
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import RepeatedKFold
# определяем датасет
X, y = make_regression(n_samples=1000, n_features=10, n_informative=5, random_state=1)
# и нашу модель (в данном примере мы меняем метрику на MAE)
model = LGBMRegressor()
cv = RepeatedKFold(n_splits=10, n_repeats=3, random_state=1)
n_scores = cross_val_score(model, X, y, scoring='neg_mean_absolute_error', cv=cv, n_jobs=-1, error_score='raise')
print('MAE (Средняя Абсолютная Ошибка): %.3f (%.3f)' % (mean(n_scores), std(n_scores)))
# тренируем модель на всём наборе данных
model = LGBMRegressor()
model.fit(X, y)
# предсказываем
row = [[2.02220122, 0.31563495, 0.82797464, -0.30620401, 0.16003707, -1.44411381, 0.87616892, -0.50446586, 0.23009474, 0.76201118]]
yhat = model.predict(row)
print('Предсказание (Предикт): %.3f' % yhat[0])
    
CatBoost – это библиотека градиентного бустинга, которую создали разработчики Яндекса. Здесь используются “забывчивые” (oblivious) деревья решений, при помощи которых мы растим сбалансированное дерево. Одни и те же функции используются для создания разделений (split) на каждом уровне дерева.

Более того, главным преимуществом CatBoost (помимо улучшения скорости вычислений) является поддержка категориальных входных переменных. Из-за этого библиотека получила свое название CatBoost, от “Category Gradient Boosting” (Категориальный Градиентный Бустинг).

Вы можете установить CatBoost проверенным ранее путем:

        pip install catboost
    
  • CatBoost в задаче классификации:
        # catboost для классификации
from numpy import mean
from numpy import std
from sklearn.datasets import make_classification
from catboost import CatBoostClassifier
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import RepeatedStratifiedKFold
from matplotlib import pyplot
# определяем датасет
X, y = make_classification(n_samples=1000, n_features=10, n_informative=5, n_redundant=5, random_state=1)
# evaluate the model
model = CatBoostClassifier(verbose=0, n_estimators=100)
cv = RepeatedStratifiedKFold(n_splits=10, n_repeats=3, random_state=1)
n_scores = cross_val_score(model, X, y, scoring='accuracy', cv=cv, n_jobs=-1, error_score='raise')
print('Точность: %.3f (%.3f)' % (mean(n_scores), std(n_scores)))
# тренируем модель на всём наборе данных
model = CatBoostClassifier(verbose=0, n_estimators=100)
model.fit(X, y)
# предсказываем
row = [[2.56999479, -0.13019997, 3.16075093, -4.35936352, -1.61271951, -1.39352057, -2.48924933, -1.93094078, 3.26130366, 2.05692145]]
yhat = model.predict(row)
print('Предсказание (Предикт): %d' % yhat[0])
    
  • CatBoost в задаче регрессии:
        # catboost для регрессии
from numpy import mean
from numpy import std
from sklearn.datasets import make_regression
from catboost import CatBoostRegressor
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import RepeatedKFold
from matplotlib import pyplot
# определяем датасет
X, y = make_regression(n_samples=1000, n_features=10, n_informative=5, random_state=1)
# и нашу модель (в данном примере мы меняем метрику на MAE)
model = CatBoostRegressor(verbose=0, n_estimators=100)
cv = RepeatedKFold(n_splits=10, n_repeats=3, random_state=1)
n_scores = cross_val_score(model, X, y, scoring='neg_mean_absolute_error', cv=cv, n_jobs=-1, error_score='raise')
print('MAE (Средняя Абсолютная Ошибка): %.3f (%.3f)' % (mean(n_scores), std(n_scores)))
# тренируем модель на всём наборе данных
model = CatBoostRegressor(verbose=0, n_estimators=100)
model.fit(X, y)
# предсказываем
row = [[2.02220122, 0.31563495, 0.82797464, -0.30620401, 0.16003707, -1.44411381, 0.87616892, -0.50446586, 0.23009474, 0.76201118]]
yhat = model.predict(row)
print('Предсказание (Предикт): %.3f' % yhat[0])
    

Когда использовать?

Вы можете использовать алгоритм градиентного бустинга при следующих условиях:

  • Наличие большого количества наблюдений (ближайшее сходство) в тренировочной выборке данных.
  • Количество признаков меньше количества наблюдений в обучающих данных. Бустинг хорошо работает, когда данные содержат смесь числовых и категориальных признаков или только числовые признаки.
  • Когда необходимо рассмотреть метрики производительности модели.

Когда НЕ следует использовать XGBoost:

  • В задачах распознавания изображений и компьютерного зрения (CV – Computer Vision).
  • В обработке и понимании естественного языка (NLP – Natural Language Processing).
  • Когда число обучающих выборок значительно меньше чем число признаков (фич).

Плюсы и минусы

Плюсы

  • Алгоритм работает с любыми функциями потерь.
  • Предсказания в среднем лучше, чем у других алгоритмов.
  • Самостоятельно справляется с пропущенными данными.

Минусы

  • Алгоритм крайне чувствителен к выбросам и при их наличии будет тратить огромное количество ресурсов на эти моменты. Однако, стоит отметить, что использование Mean Absolute Error (MAE) вместо Mean Squared Error (MSE) значительно снижает влияние выбросов на вашу модель (выбор функции в параметре criterion).
  • Ваша модель будет склонна к переобучению при слишком большом количестве деревьев. Данная проблема присутствует в любом алгоритме, связанном с деревьями и справляется правильной настройкой параметра n_estimators.
  • Вычисления могут занять много времени. Поэтому, если у вас большой набор данных, всегда составляйте правильный размер выборки и не забывайте правильно настроить параметр min_samples_leaf.
***

Хотя градиентный бустинг широко используется во всех областях науки о данных, от соревнований Kaggle до практических задач, многие специалисты все еще используют его как черный ящик. В этой статье мы разбили метод на более простые шаги, чтобы помочь читателям понять лежащие в основе работы алгоритма процессы. Удачи!

19
Ноя
2021

☕ Распространенные алгоритмы и структуры данных в JavaScript: полезные алгоритмы для веб-разработки

Завершаем цикл статей о реализации распространенных алгоритмов и структур данных на JavaScript разбором алгоритмических концепций, полезных для веб-разработки.

В предыдущих статьях серии мы разобрали все основные структуры данных и алгоритмы для работы с ними, а также их особенности в JavaScript.

Другие статьи цикла:

Больше полезной информации вы найдете на нашем телеграм-канале «Библиотека фронтендера».

Битовое представление чисел

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

Двоичная система счисления

Любое число может быть переведено в двоичную систему счисления и представлено как последовательность из 32 битов (единиц и нулей).

Десятичная Двоичная Двоичная, 32 бита
1 1 00000000000000000000000000000001
2 10 00000000000000000000000000000010
5 101 00000000000000000000000000000101
10 1010 00000000000000000000000000001010

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

        let number = 5;
number.toString(2); // '101'
    

Для обратного перевода двоичных чисел в десятичную систему можно использовать функцию parseInt с указанием основания системы:

        let bNumber = '101';
parseInt(bNumber, 2); // 5
    

Отрицательные числа

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

Итак, чтобы получить битовое представление числа -10, нужно:

1) Получить битовое представление модуля числа (10):

        00000000000000000000000000001010
    

2) Обратить каждый бит:

        11111111111111111111111111110101
    

3) Прибавить единицу:

        11111111111111111111111111110110
    

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

Побитовые операторы

Побитовые операторы работают именно с 32-битным представлением чисел – последовательно с каждым битом.

Они практически ничем не отличаются от логических операторов, даже символы у них похожие.

Бинарные операторы

Бинарные операторы побитового И (&), побитового ИЛИ (|) и исключающего ИЛИ (^) принимают два числовых операнда (в десятичной системе счисления), каждый из которых переводится в 32-битную последовательность. Затем соответствующая логическая операция производится поочередно с каждой парой бит. Полученный результат переводится обратно в десятичную систему счисления.

Например, побитовое сложение чисел 5 и 6 выглядит так:

        5 | 6
    

1) Привести оба операнда к битовому представлению:

        5 => 00000000000000000000000000000101
6 => 00000000000000000000000000000110

    

2) Произвести операцию логического ИЛИ для каждой пары битов:

        00000000000000000000000000000111
    

3) Перевести полученный результат в десятичную систему:

        00000000000000000000000000000111 => 7
    

Таким образом, 5 | 6 = 7.

Побитовое НЕ

В JavaScript также есть унарный оператор побитового НЕ (~), который просто заменяет каждый бит числа на противоположный. Ожидаемо, для положительных чисел результатом будет отрицательное число и наоборот.

        ~10 => -11
~(-11) => 10

    

Битовый сдвиг

Больше всего трудностей обычно вызывают операторы побитового сдвига:

  • левый сдвиг (<<),
  • правый сдвиг (>>)
  • правый сдвиг с заполнением нулями (>>>).
Это бинарные операторы. Левый операнд – это число, с которым производится операция, а правый операнд – это величина сдвига.

Рассмотрим для примера сдвиг числа 10 на 2 бита вправо (правый сдвиг числа 10 на два бита):

        10 >> 2
    

1) Вычисляем двоичное представление числа 10:

        00000000000000000000000000001010
    

2) Отбрасываем два правых бита:

        000000000000000000000000000010
    

3) Теперь необходимо дополнить полученный результат до 32 битов. При обычном правом сдвиге для этого копируется старший бит нужное количество раз. Это позволяет сохранить знак числа. Существует также оператор правого сдвига с заполнением нулями (>>>):

        00000000000000000000000000000010 => 2
    

В итоге получается, что 10 >> 2 => 2.

Использование

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

Проверка на четность

Число 1 в двоичном представлении выглядит так:

        00000000000000000000000000000001
    

У всех четных чисел последний (младший) бит равен 0. Если мы побитово умножим любое четное число на единицу, то получим 0. На этом может быть основана проверка числа на четность:

        function isEven(number) {
  return (number & 1) === 0;
}

    

Умножение и деление на степени двойки

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

        5 << 3 === 5 * Math.pow(2, 3)

    

Округление вниз

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

        // двойное побитовое НЕ
~~4.345 // 4
// побитовое ИЛИ с нулем
4.345 ^ 0 // 4

    
***

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

Множества

Множество – это неупорядоченная совокупность каких-либо объектов – элементов множества. Например, множество пользователей вашего сайта или множество товаров вашего интернет-магазина.

В JavaScript множество может быть представлено как в виде обычного массива, так и в виде специальной структуры – Set, которая обеспечивает уникальность своих элементов, то есть отсутствие дублей. С Set работать проще, так как эта структура уже реализует базовые операции has (проверка наличия элемента по значению) и delete (удаление элемента по значению).

Основные алгоритмы для работы с множествами:

  • объединение двух множеств в новое большое множество;
  • пересечение двух множеств – определение элементов, которые входят в оба множества;
  • разность двух множеств – определение элементов, которые входят только в одно из множеств.

Реализуем их для Set.

Объединение:

        function union(set1, set2) {
  let result = new Set(set1);
  for (let el of set2) {
    result.add(el);
  }
  return result;
}

// или

function union2(set1, set2) {
  return new Set([...set1, ...set2]);
}

    

Пересечение:

        function intersection(set1, set2) {
  let result = new Set();
  for (let el of set2) {
    if (set1.has(el)) result.add(el);
  }
  return result;
}

// или

function intersection2(set1, set2) {
  return new Set([...set1].filter(el => set2.has(el)));
}

    

Разность:

        function difference(set1, set2) {
  let result = new Set(set1);
  for (let el of set2) {
    result.delete(el);
  }
  return result;
}

// или 

function difference2(se1, set2) {
  return new Set([...set1].filter(el => !set2.has(el)));
}

    

Кэширование вычислений

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

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

Рассмотрим концепцию кэширования на простом примере – вычислении факториала числа n.

        function factorial(n) {
    console.log('Выполняется вычисление');
    let result = 1;
    while(n){
        result *= n--;
    }
    return result;
}


factorial(5); // 'Выполняется вычисление'
factorial(5); // 'Выполняется вычисление'
factorial(5); // 'Выполняется вычисление'

    

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

Было бы неплохо, чтобы функция factorial умела “запоминать” результаты предыдущих вычислений. Для этого мы добавим ей кэш:

        const cachedFactorial = (() => {
  const cache = {};
  return n => {
    if (n in cache) return cache[n];

    console.log('Выполняется вычисление');
    let result = 1;
    for (let i = n; i > 0; i--) {
      result *= i;
    }

    cache[n] = result; // "запоминание" результата
    return result;
  }
})();

    

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

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

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

        cachedFactorial(5); // 'Выполняется вычисление'
cachedFactorial(5); // ...
cachedFactorial(5); // ...

    

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

Чтобы не добавлять кэш функциям вручную, имеет смысл написать функцию-декоратор:

        function addCache(fn) {
  let cache = {};

  return function(param) {
    if (!(param in cache)) {
      cache[param] = fn.call(this, param);
    }
    return cache[param];
  };
}

const factorialWithCache = addCache(factorial);
    

Кэширование в динамическом программировании

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

Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с)
А. Кумок

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

Есть два подхода к заполнению кэша:

  • мемоизация – заполнение “сверху вниз”, обычно рекурсивное;
  • табуляция – заполнение “снизу вверх”, обычно итеративное.
Самый популярный и наглядный пример использования динамического программирования – вычисление математических последовательностей, в которых каждый следующий член зависит от предыдущих. При этом младшие члены последовательности обычно участвуют в формировании старших.

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

        0 1 1 2 3 5 8 13 21
    

При этом первые элементы (0 и 1) известны.

Предположим, что у нас есть задача найти n-ное число Фибоначчи, и рассмотрим для нее обе стратегии кэширования.

Табуляция

Стратегия табуляции предусматривает пошаговое заполнение кэша снизу вверх – от младших членов последовательности к старшим.

        function fibonacciTabulation(n) {
  let cache = [];
  cache[0] = 0;
  cache[1] = 1;
  for (let i = 2; i <= n; i++) {
    cache[i] = cache[i - 2] + cache[i - 1];
  }
  return cache[n];
}

    

Мемоизация

Стратегия мемоизации отталкивается от формального описания проблемы и нацелена прежде всего именно на поиск решения – она более декларативная и обычно использует рекурсию.

Формальное описание проблемы: n-ный член является суммой двух предыдущих членов, то есть fib(6) = fib(5) + fib(4). Таким образом, мы разбиваем одну задачу на две задачи поменьше.

Дерево вычисления шестого члена ряда Фибоначчи
Дерево вычисления шестого члена ряда Фибоначчи
        f(6) = f(5) + f(4)

f(5) = f(4) + f(3)
f(4) = f(3) + f(2)

// …

    

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

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

Схема вычисления шестого члена ряда Фибоначчи без перекрывающихся вычислений младших членов
Схема вычисления шестого члена ряда Фибоначчи без перекрывающихся вычислений младших членов
        function fibonacciMemoization(n) {
  let cache = {};

  let recursive = (n) => {
    // член последовательности уже был посчитан
    if (n in cache) return cache[n];
    // вычисление n-ного члена и сохранение его в кэше
    let result;
    if (n < 2) result = n;
    else result = recursive(n-2) + recursive(n-1);
    cache[n] = result;
    return cache[n];
  }

  return recursive(n);
}

    
***
Выбор стратегии кэширования зависит от задачи, которую необходимо решить. Если она предусматривает полное заполнение кэша (как вычисление n-ного члена последовательности), то табуляция обычно выгоднее, так как она не предусматривает дополнительных расходов на рекурсивные вызовы функций.

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

Трансформации

Большинство frontend-разработчиков так или иначе сталкиваются с трансформациями, хотя бы в CSS (translate, rotate, scale и т. д.) Не все представляют, что при этом происходит под капотом, – как именно определяется новая форма DOM-элемента.

Каждый трансформируемый фрагмент (HTML-элемент или часть изображения на canvas) – это всего лишь набор отдельных точек (пикселей). Можно выделить несколько базовых характеристик такого фрагмента:

  • e, f – координаты, положение фрагмента относительно целого холста (веб-страницы или элемента canvas).
  • a, d – размеры (ширина и высота) одного пикселя.

Изначально e и f равны 0 (фрагмент никуда не сдвинут с исходной точки), а размеры пикселя (a, d) равны 1 (то есть 100% от исходного).

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

Если мы установим e = 20, то каждый пиксель фрагмента будет отрисован на 20 пикселей по горизонтали правее – изображение сместится.

Смещение фрагмента по горизонтали и по вертикали (сдвиг)
Смещение фрагмента по горизонтали и по вертикали (сдвиг)

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

Масштабирование фрагмента по горизонтали и по вертикали
Масштабирование фрагмента по горизонтали и по вертикали

Сдвиг пикселей относительно друг друга

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

  • b – коэффициент сдвига по вертикали
  • c – коэффициент сдвига по горизонтали

По умолчанию пиксельный сдвиг равен нулю, но если изменить его, то можно получить эффект наклона фрагмента.

Деформация фрагмента за счет сдвига пикселей относительно друг друга
Деформация фрагмента за счет сдвига пикселей относительно друг друга
  • Сдвиг по горизонтали (c) умножается на y-координату пикселя, то есть каждый следующий ряд пикселей сдвигается по горизонтали относительно предыдущего.
  • Сдвиг по вертикали (b) соответственно умножается на x-координату пикселя, то есть каждая следующая колонка пикселей сдвигается по вертикали относительно предыдущей.

Предположим, что величина сдвига по горизонтали c = 5. Весь первый ряд пикселей останется на своем месте, так как их координата y равна нулю. Зато второй ряд (с координатой y=1) сползает вправо на 5 (1 * 5) пикселей. Третий ряд сдвинется уже на 10 пикселей, относительно исходной позиции.

Матрицы трансформаций

Все параметры трансформации фрагмента обычно представлены в виде матрицы. Для двумерного пространства она выглядит вот так:

Матрица трансформации
Матрица трансформации
  • a – горизонтальный размер пикселя (масштаб)
  • b – горизонтальный сдвиг пикселей (деформация по оси OX)
  • c – вертикальный сдвиг пикселей (деформация по оси OY)
  • d – вертикальный размер пикселя (масштаб)
  • e – горизонтальное смещение фрагмента (сдвиг)
  • f – вертикальное смещение фрагмента (сдвиг)

Координаты же каждого пикселя в 2d-пространстве можно представить как вектор:

Координаты одного пикселя в двумерном пространстве
Координаты одного пикселя в двумерном пространстве

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

Вычисление новых координат пикселя путем умножения исходных координат на матрицу трансформации
Вычисление новых координат пикселя путем умножения исходных координат на матрицу трансформации

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

Реализация

Умножение матриц осуществляется по правилу “строка на столбец”, реализуем это на JavaScript:

        function apply2dTransform(matrix, vector) {
   return matrix.map(row => {
        return row.reduce((sum, param, i) => {
            return sum + (param * vector[i])
        }, 0)
   });
}

    

Возьмем из фрагмента пиксель с координатами x = 10, y = 10 и опробуем на нем разные матрицы трансформации:

        let pixel = [ 10, 10, 1 ];
    

Дефолтная матрица (без трансформаций)

        let defaultMatrix = [
  [ 1, 0, 0 ],
  [ 0, 1, 0 ],
  [ 0, 0, 1]
]

// координаты пикселя не изменились
apply2dTransform(defaultMatrix, pixel); // [ 10, 10, 1] 
    

Матрица сдвига

        let shiftMatrix = [
  [ 1, 0, 20 ],
  [ 0, 1, 50 ],
  [ 0, 0, 1]
]

apply2dTransform(shiftMatrix, pixel); // [ 30, 60, 1]

    

Трансформация поворота

Можно изменять разные параметры одновременно, чтобы получать более сложные трансформации. Например, трансформация поворота – это сочетание сдвига пикселей и масштабирования. Для поворота на угол A (против часовой стрелки) требуется такая матрица:

        let rotateMatrix = [
  [ Math.cos(A), Math.sin(A), 0 ],
  [ -Math.sin(A), Math.cos(A), 0 ],
  [ 0, 0, 1]
]

    

Попробуем применить ее к нашему пикселю:

        function createRotateMatrix(deg) {
  let rad = deg * Math.PI / 180; // угол в радианах
  return [
    [ Math.cos(rad), Math.sin(rad), 0 ],
    [ -Math.sin(rad), Math.cos(rad), 0 ],
    [ 0, 0, 1]
  ]
}

apply2dTransform(createRotateMatrix(90), pixel); // [ 10, -10, 1 ]

    
***

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

Заключение

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

Теперь вы имеет представление о всех основных способах работы с данными в JavaScript. Выбирая структуры и алгоритмы для очередной задачи, помните:

Умные структуры данных и тупой код работают куда лучше, чем наоборот.

Другие статьи цикла:

Полезные ресурсы

10
Ноя
2021

Двоичное(бинарное) дерево: создание и обход

В этой статье рассмотрим двоичное или банарное дерево, как оно строится и варианты обходов. Материал подойдёт для новичков.
— Читать дальше «Двоичное(бинарное) дерево: создание и обход»

27
Окт
2021

☕ Распространенные алгоритмы и структуры данных в JavaScript: объекты и хеширование

Говоря о структурах данных в JavaScript, мы никак не можем пройти мимо самой важной структуры этого языка – объекта. Давайте посмотрим, что у него под капотом и зачем нужны алгоритмы хеширования.

Другие статьи цикла:

Ассоциативный массив

Объекты JavaScript – пример ассоциативного массива. В отличие от обычных массивов у ассоциативных не индексы, а ключи (обычно строковые). В остальном разницы почти нет – ключи уникальны и каждому соответствует какое-то значение. Ассоциативные массивы также называются словарями или мапами (от англ. map). Они позволяют удобно представлять сложные данных разных типов (например, информацию о пользователе) и очень популярны в программировании на JavaScript.

В плане эффективности ассоциативные массивы превосходят другие структуры данных: все основные операции в них выполняются за константное время O(1). Например, чтобы добавить новый элемент в середину простого массива, вам придется его переиндексировать (мы говорили об этом в первой части). Сложность этой операции – O(n). В ассоциативном массиве вы просто добавляете новый ключ, с которым связано значение.

Больше полезной информации вы можете получить на наших телеграм-каналах «Библиотека программиста» и «Библиотека фронтендера».

Хеш-таблицы

Однако у ассоциативных массивов есть своя слабость – их нельзя положить в память компьютера как есть, в отличие от обычного индексированного массива. Для хранения ассоциативных массивов используется специальная структура – хеш-таблица (hash map).

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

Ассоциативные массивы – это в некотором смысле синтаксический сахар, более удобная надстройка над хеш-таблицей.

Принципиальная схема работы хеш-таблицы
Принципиальная схема работы хеш-таблицы

Хеширование

Чтобы превратить ключ ассоциативного массива в индекс обычного, нужно проделать 2 операции:

  • Найти хеш (хешировать ключ);
  • Привести найденный хеш к индексу результирующего массива.

То есть конечная задача – преобразовать ключ в числовой индекс, но она обычно выполняется в два этапа.

Вычисление хеша

Хеш-функция получает входные данные и преобразует их в хеш – строку или число фиксированной длины. Вы точно слышали о некоторых алгоритмах хеширования: CRC32, MD5 и SHA. Ключ при этом может быть представлен любым типом данных, с которым умеет работать хеш-функция.

Пример хеша – идентификатор коммита в git. Когда вы сохраняете изменения, они хешируются и получается что-то вроде 0481e0692e2501192d67d7da506c6e70ba41e913. Это хеш, вычисленный для ваших изменений.

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

        const hash = key => key;
    

Если в качестве ключей выступают строки, можно вычислять сумму кодов всех символов:

        const hash = string => {
    let result = 0;
    for (let i = 0; i < string.length; i++) {
        result += string.charCodeAt(i);
    }
    return result;
};
    

Например, для ключа name хешем будет число 417, а для ключа age – число 301.

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

Важно: для одного и того же входного значения хеш-функция всегда возвращает одинаковый результат.

Приведение к индексу

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

Для вычисления индекса можно использовать остаток от деления хеша на размер массива:

        const index = Math.abs(hash) % 5;
    

Важно помнить, что чем больше длина массива, тем больше места он занимает в памяти.

Воспользуемся нашей хеш-функцией и преобразуем ассоциативный массив в обычный:

        // ассоциативный массив
const user = {
  name: 'John',
  age: 23
};

// обычный массив с длиной 5
[
	undefined,
	['age', 23],
	['name', 'John'],
	undefined,
	undefined
]

    

Ключу name соответствует индекс 2, а ключу age – 1.

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

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

Коллизии

Вы уже видите слабое место подобных преобразований?

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

Есть два распространенных варианта решения коллизий.

Открытая адресация

Предположим, что мы передали хеш-функции какой-то ключ ассоциативного массива (key1) и получили от нее 2 – индекс обычного массива, который соответствует этому ключу.

        [ undefined, undefined, [key1, value1], undefined, undefined, undefined, undefined ]
    

Затем мы передаем ей другой ключ – key2 – и вновь получаем 2 – произошла коллизия. Мы не можем записать новые данные под тем же индексом, поэтому мы просто начинаем искать первое свободное место в массиве. Это называется линейное пробирование. Следующий после 2 индекс – 3 – свободен, записываем новые данные в него:

        [ undefined, undefined, [key1, value1], [key2, value2], undefined, undefined, undefined ]

    

Для третьего ключа key3 хеш-функция возвращает индекс 3 – но он уже занят ключом key2, поэтому нам приходится снова искать свободное место.

        [ undefined, undefined,  [key1, value1], [key2, value2], [key3,value3], undefined, undefined ]

    

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

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

Метод цепочек

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


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

Такая реализация позволяет с легкостью удалять элементы из таблицы, ведь в связном списке операция удаления занимает константное время.

Реализация хеш-таблицы на JavaScript

Хеш-таблица должна реализовывать интерфейс ассоциативного массива, то есть предоставлять три основных метода:

  • добавление новой пары ключ-значение;
  • поиск значения по ключу;
  • удаление пары по ключу.

Чем меньше размер хеш-таблицы (длина массива), тем чаще будут происходить коллизии. Мы возьмем для примера небольшое число – 32. На практике для размера хеш-таблицы часто используются простые числа (которые делятся только на единицу и на себя). Считается, что при этом возникает меньше коллизий.

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

        const hashTableSize = 32;

class HashTable {
  constructor() {
    this.buckets = Array(hashTableSize).fill(null);
  }

  hash(key) {
    let hash = Array.from(key).reduce((sum, key) => {
      return sum + key.charCodeAt(0);
    }, 0);
    return hash % hashTableSize;
  }

  set(key, value) {
    // вычисляем хеш для ключа
    let index = this.hash(key);

    // если для данного хеша еще нет списка, создаем
    if (!this.buckets[index]) {
      this.buckets[index] = new LinkedList();
    }

    let list = this.buckets[index];
    // проверяем, не добавлен ли ключ ранее
    let node = list.find((nodeValue) => {
      nodeValue.key === key;
    });

    if (node) {
      node.value.value = value; // обновляем значение для ключа
    } else {
      list.append({ key, value }); // добавляем новый элемент в конец списка
    }
  }

  get(key) {
    // вычисляем хеш для ключа
    let index = this.hash(key);
    // находим в массиве соответствующий список
    let list = this.buckets[index];

    if (!list) return undefined;

    // ищем в списке элемент с нужным ключом
    let node = list.find((nodeValue) => {
      return nodeValue.key === key;
    });

    if (node) return node.value.value;
    return undefined;
  }

  delete(key) {
    let index = this.hash(key);
    let list = this.buckets[index];

    if (!list) return;

    let node = list.find((nodeValue) => nodeValue.key === key);
    if (!node) return;

    list.delete(node.value);
  }
}

    

Эффективность основных операций в хеш-таблице

Основные операции в хеш-таблице состоят из двух этапов:

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

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

Эффективность хеш-таблицы зависит от трех основных факторов:

  • Хеш-функция, которая вычисляет индексы для ключей. В идеале она должна распределять индексы равномерно по массиву;
  • Размер самой таблицы – чем он больше, тем меньше коллизий;
  • Метод разрешения коллизий. Например, метод цепочек позволяет свести операцию добавления нового элемента к константному времени.

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

Использование хеш-таблиц

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

В JavaScript хеш-таблицы в чистом виде используются довольно редко. Обычно всю их работу успешно выполняют обычные объекты (ассоциативные массивы) или более сложные Map. При этом на более низком уровне(интерпретация программы) для представления объектов как раз используются хеш-таблицы.

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

        function countSymbols(string) {
    const hash = {};
    [...string].forEach(s => {
    let symbol = s.toLowerCase();
    if (!(symbol in hash)) hash[symbol] = 0;
    hash[symbol]++;
  });
  return hash;
}

countSymbols('Hello, world!');
/*
{ " ": 1, "!": 1, ",": 1, d: 1, e: 1, h: 1, l: 3, o: 2, r: 1, w: 1 }
*/

    

Хеширование, кодирование и шифрование

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

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

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

Кроме шифрования есть еще кодирование. Оно близко к шифрованию по сути, но отличается по цели. Кодирование используется для упрощения передачи информации, например, по линиям электросвязи. Ваше сообщение преобразуется в последовательность битов, доставляется получателю по проводу, а на том конце снова восстанавливается. Никакие ключи при этом не используются. Подобные коды не только решают проблему коммуникации, но и часто пытаются бороться с возможными помехами при передаче, то есть обладают способностью восстанавливать повреждения. Один из самых известных кодов – азбука Морзе.

Заключение

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

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

21
Окт
2021

🤖 Состояние дел в области синтеза речи на конец мая 2021 года

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

13
Окт
2021

☕ Распространенные алгоритмы и структуры данных в JavaScript: стеки, очереди и связные списки

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

08
Окт
2021

Конференция HighLoad++ 2021

Крупнейшая в Европе IT-конференция для разработчиков высоконагруженных систем. В программе более 130 докладов, персональные консультации и полезные знакомства.
— Читать дальше «Конференция HighLoad++ 2021»

06
Окт
2021

☕ Распространенные алгоритмы и структуры данных в JavaScript: основные понятия и работа с массивами

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

27
Сен
2021

Идеи динамического программирования: одномерные задачи, часть 2

Основные задачи динамического программирования, которые можно решить, используя одномерный массив.
— Читать дальше «Идеи динамического программирования: одномерные задачи, часть 2»

27
Сен
2021

Идеи динамического программирования: одномерные задачи, часть 2

Основные задачи динамического программирования, которые можно решить, используя одномерный массив.
— Читать дальше «Идеи динамического программирования: одномерные задачи, часть 2»