Category: Алгоритмы

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»

22
Сен
2021

Идеи динамического программирования: одномерные задачи, часть 1

Разбираем несколько классических задач динамического программирования с использованием одномерного массива и без него.
— Читать дальше «Идеи динамического программирования: одномерные задачи, часть 1»

08
Сен
2021

«Кому-то больше понравится сцена со взрывом, кому-то — с поцелуем»: что такое хайлайты в онлайн-кинотеатрах и какие алгоритмы их создают

Директор по технологии IVI рассказывает, что такое хайлайты в онлайн-кинотеатрах, зачем их показывают и как создают.
— Читать дальше ««Кому-то больше понравится сцена со взрывом, кому-то — с поцелуем»: что такое хайлайты в онлайн-кинотеатрах и какие ал…

12
Авг
2021

Онлайн-хакатон «Цифровой форсаж атомных городов»

Командам предстоит решать задачи и предлагать идеи по улучшению цифрового сервиса в «атомных» городах. Призовой фонд — 1 млн рублей.
— Читать дальше «Онлайн-хакатон «Цифровой форсаж атомных городов»»

12
Авг
2021

🤖 Машинное обучение для начинающих: алгоритм случайного леса (Random Forest)

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

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

В каких задачах используется?

Благодаря своей гибкости Random Forest применяется для решения практически любых проблем в области машинного обучения. Сюда относятся классификации (RandomForestClassifier) и регрессии (RandomForestRegressor), а также более сложные задачи, вроде отбора признаков, поиска выбросов/аномалий и кластеризации.

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

        import pandas as pd 
from sklearn.ensemble  import RandomForestClassfier 
from sklearn.feature_selection import SelectFromModel 
X_train,y_train,X_test,y_test = train_test_split(data,test_size=0.3)
 sel = SelectFromModel(RandomForestClassifier(n_estimators = 100)) 
sel.fit(X_train, y_train)
    

Здесь мы на основе классификации просто добавляем метод для отбора признаков.

Порядок действий в алгоритме

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

Теоретическая составляющая алгоритма случайного дерева

По сравнению с другими методами машинного обучения, теоретическая часть алгоритма Random Forest проста. У нас нет большого объема теории, необходима только формула итогового классификатора a(x):


Где

  • N – количество деревьев;
  • i – счетчик для деревьев;
  • b – решающее дерево;
  • x – сгенерированная нами на основе данных выборка.

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

Реализация алгоритма Random Forest

Реализуем алгоритм на простом примере для задачи классификации, используя библиотеку scikit-learn:

        class sklearn.ensemble.RandomForestClassifier(n_estimators=10, criterion='gini', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features='auto', max_leaf_nodes=None, min_impurity_split=1e-07, bootstrap=True, oob_score=False, n_jobs=1, random_state=None, verbose=0, warm_start=False, class_weight=None)
    

Работаем с алгоритмом по стандартному порядку действий, принятому в scikit-learn. Вычисляем AUC-ROC (площадь под кривой ошибок) для тренировочной и тестовой частей модели, чтобы определить ее качество:

        from sklearn.ensemble import RandomForestRegressor 
from sklearn.metrics import roc_auc_score 
# далее - (X, y) - для обучения, (X2, y2) - для контроля
# модель - регрессор 
model =  RandomForestRegressor(n_estimators=10,                              
                               oob_score=True,
                               random_state=1) 
model.fit(X, y) # обучение 
a = model.predict(X2) # предсказание  
print ("AUC-ROC (oob) = ", roc_auc_score(y, model.oob_prediction_)) 
print ("AUC-ROC (test) = ", roc_auc_score(y2, a))
    

Необходимые параметры алгоритма

Число деревьев – n_estimators

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

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

Критерий расщепления – criterion

Также один из самых важных параметров для построения, но без значительной возможности выбора. В библиотеке sklearn для задач классификации реализованы критерии gini и entropy. Они соответствуют классическим критериям расщепления: джини и энтропии.

В свою очередь, для задач регрессии реализованы два критерия (mse и mae), которые являются функциями ошибок Mean Square Error и Mean Absolute Error соответственно. Практически во всех задачах используется критерий mse.

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

Число признаков для выбора расщепления – max_features

При увеличении max_features увеличивается время построения леса, а деревья становятся похожими друг на друга. В задачах классификации он по умолчанию равен sqrt(n), в задачах регрессии – n/3.

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

Минимальное число объектов для расщепления – min_samples_split

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

Ограничение числа объектов в листьях – min_samples_leaf

Аналогично с min_samples_split, но при увеличении данного параметра качество модели на обучении падает, в то время как время построения модели сокращается.

Максимальная глубина деревьев – max_depth

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

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

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

Преимущества алгоритма


  • Имеет высокую точность предсказания, которая сравнима с результатами градиентного бустинга.
  • Не требует тщательной настройки параметров, хорошо работает из коробки.
  • Практически не чувствителен к выбросам в данных из-за случайного семплирования (random sample).
  • Не чувствителен к масштабированию и к другим монотонным преобразованиям значений признаков.
  • Редко переобучается. На практике добавление деревьев только улучшает композицию.
  • В случае наличия проблемы переобучения, она преодолевается путем усреднения или объединения результатов различных деревьев решений.
  • Способен эффективно обрабатывать данные с большим числом признаков и классов.
  • Хорошо работает с пропущенными данными – сохраняет хорошую точность даже при их наличии.
  • Одинаково хорошо обрабатывает как непрерывные, так и дискретные признаки
  • Высокая параллелизуемость и масштабируемость.

Недостатки алгоритма


  • Для реализации алгоритма случайного дерева требуется значительный объем вычислительных ресурсов.
  • Большой размер моделей.
  • Построение случайного леса отнимает больше времени, чем деревья решений или линейные алгоритмы.
  • Алгоритм склонен к переобучению на зашумленных данных.
  • Нет формальных выводов, таких как p-values, которые используются для оценки важности переменных.
  • В отличие от более простых алгоритмов, результаты случайного леса сложнее интерпретировать.
  • Когда в выборке очень много разреженных признаков, таких как тексты или наборы слов (bag of words), алгоритм работает хуже чем линейные методы.
  • В отличие от линейной регрессии, Random Forest не обладает возможностью экстраполяции. Это можно считать и плюсом, так как в случае выбросов не будет экстремальных значений.
  • Если данные содержат группы признаков с корреляцией, которые имеют схожую значимость для меток, то предпочтение отдается небольшим группам перед большими, что ведет к недообучению.
  • Процесс прогнозирования с использованием случайных лесов очень трудоемкий по сравнению с другими алгоритмами.

Заключение

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

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

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

Дополнительные материалы:

09
Авг
2021

Teleperformance заставляет удалённых сотрудников устанавливать дома камеры для контроля эффективности

Компания Teleperformance внедряет систему видеоконтроля за сотрудниками для мониторинга их эффективности. Камеры будут записывать видео и звук.
— Читать дальше «Teleperformance заставляет удалённых сотрудников устанавливать дома камеры для контроля эфф…

09
Авг
2021

👨‍🎓️ Нужны ли программисту математика, английский язык, теория алгоритмов и паттерны проектирования?

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

Разумеется, ответить на такие вопросы может только программист с большим опытом работы. Поэтому писать эту статью доверили именно мне – разработчику со стажем в 28 лет (C++, Delphi, C#), чьи первые продаваемые программы работали еще под MS-DOS. И математику, и английский, и алгоритмы, и проектирование я знаю очень хорошо – но это не сделало меня не только тимлидом, но даже “сеньором”. Так что я не собираюсь вас убеждать, что без всего этого ваша карьера обречена. Способность быстро написать работающий код, который потребовало начальство, было и остается самой важной способностью программиста. Конечно, оценить качество этого кода сумеют немногие, и ваше начальство едва ли входит в их число, зато оно наверняка оценит вашу исполнительность.

Иногда возникают нюансы. Вам приходится не только писать код, но и формализовать задачу, поставленную заказчиком на манер знаменитого “копать от забора и до обеда”. Или ваш код, написанный “на коленке” за пару минут, работает слишком медленно. Или ваша программа выдает исключение, давно описанное на stackoverflow.com, но вы не умеете читать по-английски. Или возникает необходимость сделать рефакторинг кода, а для вас это звучит как “харакири”. Как правило, начальству наплевать на то, как вы справитесь с этими проблемами, но справиться вы обязаны – “вы же программист”! За что же вам платят эдакие деньжищи?

Математика

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


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

Это мы опубликуем. Это никому не стыдно опубликовать.

Аркадий и Борис Стругацкие, «Понедельник начинается в субботу»

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

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

  1. То, что вы будете использовать каждый день: дискретная математика. О ней мы сейчас поговорим подробнее.
  2. То, что вам нужно для решения возникающих математических задач: дифференциальное и интегральное исчисление, линейная алгебра, статистика. Эти разделы математики используются не каждый день, а у многих программистов – даже не каждый год, но знать их все равно очень полезно, а во многих компаниях – даже необходимо. Почему? Если вам хоть изредка приходится ставить математическую постановку задачи – вы просто не сможете этого сделать без соответствующей математической базы. Имея базу, вы сможете найти информацию о своей задаче в Интернете и использовать ее, а без базы вы эту информацию просто не поймете!
  3. Специфические знания. Нужны только для решения задач из определенной прикладной области. Если вы пишете программы именно в этой области – знание необходимых разделов математики будет огромным плюсом, а если не пишете – эти разделы вам не нужны.

Дискретная математика

Этот раздел математики изучает конечные структуры и содержит множество различных подразделов. Самый важный подраздел для программистов – это математическая логика, в которую входит обработка привычных каждому программисту логических операций вроде and, or, и not. Например, следующий оператор срабатывает, если верно a, но не b, или, наоборот, верно b, но не a:

        if ((a && !b) || (!a && b))
{
   // Сделаем что-нибудь
}
    

Если вы изучали дискретную математику, то сразу поймете, что то же самое можно написать гораздо проще, используя операцию “исключающее ИЛИ”, причем код будет не только намного короче, но и станет работать быстрее:

        if (a ^ b)
{
   // Сделаем что-нибудь
}
    

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

        // Сложное логическое выражение
if ((a || b) && (c || !b))
{
}
// Инвертированное логическое выражение
if ((!a && !b) || (!c && b))
{
}
    

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

С чем должно ассоциироваться слово "граф" для программиста
С чем должно ассоциироваться слово “граф” для программиста

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

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

Для освоения всей дискретной математики вам будет достаточно всего одной книги: “Дискретной математики для программистов” Рона Хаггарти. Было бы очень здорово, если бы все пробелы в нашем образовании можно было закрыть, изучив всего одну книгу, правда? Пробелы в школьных знаниях поможет закрыть наш онлайн-марафон, а если вам нужны и другие области математики, например, чтобы изучить науку о данных, можно начать с курса «Библиотеки программиста».

Английский язык


Ду ю спик инглиш? Говорите, “академиев не кончали”? Не страшно! Из четырех основных навыков, проверяемых на серьезных экзаменах по языку (чтение, сочинение, разговор и аудирование) программисту достаточно только первого – чтения, но при этом читать придется не Агату Кристи, а техническую литературу по специальности, что намного труднее.

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

Иногда вам придется и написать абзац-другой – например, задать вопрос на форуме или в отдел технической поддержки. Поскольку писать сочинения вроде “London is the capital of Great Britain” вам едва ли понадобится, это не должно вызвать особых трудностей, если вы уже хорошо умеете читать. Даже если вы сделаете пару ошибок, не страшно – лишь бы вас правильно поняли.

Многие фирмы работают на Запад, и там регулярно проводятся совещания на английском языке. Вот там вам уже понадобятся и разговорные навыки, и аудирование, и даже хорошее произношение. Такие фирмы прямо пишут в своих вакансиях что-то вроде “English – Upper-Intermediate”. Высококлассному специалисту с большим опытом должно быть очень обидно упускать такие вакансии только из-за незнания языка.


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

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

Теория алгоритмов


Как вы думаете, чем тимлид отличается от джуниора? Нет, не выслугой лет, и не заслугами перед компанией. Настоящий тимлид обязан отлично знать теорию алгоритмов и хорошо разбираться в проектировании. Почему? Да потому, что в большинстве компаний нет выделенных проектировщиков (в Штатах их обычно называют “архитекторами программ”, software architect), и никто выше тимлида не способен принять правильное решение о том, каким должен быть продукт, и как его следует писать. Впрочем, о проектировании мы поговорим чуть ниже, а сейчас речь о теории алгоритмов.
Алгоритм – это метод решения задачи. Он может быть правильным (если программа во всех случаях работает правильно) или неправильным – если она работает правильно не всегда. Он также может быть эффективным (если программа затрачивает минимально возможное количество ресурсов, особенно времени и оперативной памяти) или неэффективным, если намного больше.

Теория алгоритмов оценивает не точное количество ресурсов (которое на практике редко можно рассчитать), а характер его зависимости от размеров исходных данных, называемой сложностью. Например, цикл по всем элементам массива имеет вычислительную сложность O(N), где N – количество элементов массива. Это значит, что количество вычислительных операций пропорционально N. Общеизвестно, что сложность быстрой сортировки (в среднем) равна O(N * logN), а сложность бинарного поиска – O(log N). Поиск в хеш-таблице происходит еще быстрее: при правильно подобранных ключах и достаточном размере таблицы его сложность O(1), то есть вообще не зависит от размера входных данных! Этим и обусловлена широкая популярность хеш-таблиц, а также базирующихся на них словарей (dictionary) и множеств (set).

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

Теоретически, вы можете писать код, и не зная об алгоритмах, но это будет код школьника-троечника. Причем страшнее всего то, что вы этого даже не почувствуете! Если вам не хватает английского языка – это всегда очевидно: вы не можете понять текст, постоянно лезете в словарь, или, что еще хуже, пользуетесь автоматическим переводчиком. Если вам не хватает математической подготовки – вы, конечно, не сможете обнаружить нехватку самостоятельно, но хотя бы почувствуете, что чего-то не понимаете. А вот люди, ничего не знающие об алгоритмах, не получают никаких “звоночков”. Они успешно пишут код, который прекрасно проходит все тесты (поскольку размер данных в тестах обычно невелик), но у пользователя работать не будет.

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

Хороших книг по теории алгоритмов очень много. Начать стоит с учебника С.М. Окулова “Программирование в алгоритмах“, доступного даже для школьников. Если вы по-настоящему любите математику, возьмитесь за классическую книгу Дональда Кнута “Искусство программирования” – там вы найдете не только описания алгоритмов, но и доказательства сложности многих из них. Ну, а если вы умеете читать по-английски и уже знаете основы теории – беритесь за “Продвинутые алгоритмы и структуры данных” Марчелло Ла Рокка.

Паттерны проектирования


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

Пожалуй, впервые важность проектирования была продемонстрирована в книге Ф.Брукса “Мифический человеко-месяц”, вышедшей в далеком 1975-м, но она была ориентирована на менеджеров, а не на программистов. В 1994-м Э. Гамма, Р. Хелм, Р. Джонсон и Д. Влиссидес (называемые “бандой четырех”, “Gang of Four”) опубликовали книгу “Паттерны объектно-ориентированного проектирования“, заложившую основы современного подхода к проектированию ПО. В книге описано множество типовых приемов (которые авторы назвали “паттернами”), помогающих улучшить проекты проекты программ, и это стало основным фактором ее популярности. Стало модно задавать вопросы по паттернам проектирования на собеседованиях, и юные соискатели начали заучивать их наизусть. (Я не рассматриваю SOLID, появившийся позднее, поскольку он слабо помогает проектировать – но заучить его для собеседований вам тоже придется).

К сожалению, навыки кодирования и проектирования очень сильно отличаются друг от друга, так что гениальный проектировщик вряд ли окажется еще и супер-кодировщиком (а когда такое все же случается, в мире появляется очередной Линус Торвальдс). Типичный кодировщик – это юноша, очень быстро набирающий код, то есть обдумывающий его еще быстрее. Типичный проектировщик – это человек с большим опытом, который может не набрать ни одной строки кода на протяжении нескольких дней или даже недель. Его задача – придумать наилучшую архитектуру продукта, вот он и думает. Разумеется, кодировщики, ничего не знающие о проектировании, считают проектировщика просто бездельником! Именно поэтому крупные компании не ставят проектировщика в подчинение руководителю команды кодировщиков, а придумывают для него особую должность “архитектора” (software architect).

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

Отличный пример широко распространенного, но неправильного понимания паттерна проектирования дает паттерн Bridge (Мост). Начнем с правильного примера использования этого паттерна на C# (код взят из документации Microsoft):

        using System;
using System.Data;

namespace IDbConnectionSample {
   class Program {
      static void Main(string[] args) {
         IDbConnection connection;

         // First use a SqlClient connection
         connection = new System.Data.SqlClient.SqlConnection(@"Server=(localdb)\V11.0");
         Console.WriteLine("SqlClient\r\n{0}", GetServerVersion(connection));
         connection = new System.Data.SqlClient.SqlConnection(@"Server=(local);Integrated Security=true");
         Console.WriteLine("SqlClient\r\n{0}", GetServerVersion(connection));

         // Call the same method using ODBC
         // NOTE: LocalDB requires the SQL Server 2012 Native Client ODBC driver
         connection = new System.Data.Odbc.OdbcConnection(@"Driver={SQL Server Native Client 11.0};Server=(localdb)\v11.0");
         Console.WriteLine("ODBC\r\n{0}", GetServerVersion(connection));
         connection = new System.Data.Odbc.OdbcConnection(@"Driver={SQL Server Native Client 11.0};Server=(local);Trusted_Connection=yes");
         Console.WriteLine("ODBC\r\n{0}", GetServerVersion(connection));

         // Call the same method using OLE DB
         connection = new System.Data.OleDb.OleDbConnection(@"Provider=SQLNCLI11;Server=(localdb)\v11.0;Trusted_Connection=yes;");
         Console.WriteLine("OLE DB\r\n{0}", GetServerVersion(connection));
         connection = new System.Data.OleDb.OleDbConnection(@"Provider=SQLNCLI11;Server=(local);Trusted_Connection=yes;");
         Console.WriteLine("OLE DB\r\n{0}", GetServerVersion(connection));
         }

      public static string GetServerVersion(IDbConnection connection) {
         // Ensure that the connection is opened (otherwise executing the command will fail)
         ConnectionState originalState = connection.State;
         if (originalState != ConnectionState.Open)
            connection.Open();
         try {
            // Create a command to get the server version
            // NOTE: The query's syntax is SQL Server specific
            IDbCommand command = connection.CreateCommand();
            command.CommandText = "SELECT @@version";
            return (string)command.ExecuteScalar();
         }
         finally {
            // Close the connection if that's how we got it
            if (originalState == ConnectionState.Closed)
               connection.Close();
         }
      }
   }
}
    

Интерфейс IDBConnection реализует Мост между клиентским приложением и базой данных (БД). Цель паттерна – полная изоляция клиента от деталей реализации каждой конкретной БД. Конкретным объектом, реализующим этот интерфейс, может быть любой экземпляр класса, унаследованного от DBConnection (код создает экземпляры SqlConnection, OdbcConnection и OleDbConnection), но клиент никогда не должен узнать, какого именно. Это позволяет разработчикам клиентского приложения сделать его по-настоящему мультиплатформным, а разработчикам Моста – постепенно добавлять поддержку новых БД, которая не заставит разработчиков клиента ничего менять. Важная парадигма: для клиентского приложения оба “берега”, соединяемых Мостом, всегда представляют одно и то же (в нашем примере – БД), только на “его” берегу находится абстрактное представление о БД, а на “чужом” – ее конкретная реализация.

Теперь взгляните, какой “пример Моста” приведен на сайте Метанит. Там объект программиста обращается к объекту языка программирования через “мост”. Непонятно, зачем изолировать объекты языков программирования от объектов программистов, но проблема даже не в этом. Во-первых, вы не можете заранее предсказать все, что вам потребуется от языков программирования – а это значит, что ваш “мост”, скорее всего, через некоторое время придется изменять, тогда как одна из целей настоящего Моста заключается именно в защите клиента от изменений (как вы думаете, будет ли когда-нибудь изменен IDBConnection?). Во-вторых, вы не можете раз и навсегда определить даже вид соотношения между языками и программистами! Кто сказал, что каждый программист знает только один язык? Такие “мосты” только напрасно усложняют проект и не приносят никакой реальной пользы.

А вот пример того же паттерна с сайта Refactoring Guru. Здесь строится “мост” между пультами и управляемыми с их помощью устройствами. Этот пример уже имеет смысл, поскольку управлять с пульта проще, чем кнопками на устройстве (клиенту всегда проще работать с абстрактным интерфейсом Моста, избавляющим его от ненужных деталей реализации), но все-таки он неудачен. Не все команды управления телевизором и радио будут совпадать. Но самое главное – пульт не скрывает от клиента конкретную реализацию: клиент по-прежнему смотрит телевизор, а не пульт, и слушает радио, а не пульт. А мы уже знаем, что основная цель Моста – именно изоляция клиента от конкретной реализации.

Настоящий проектировщик не только использует паттерны правильно, но и придумывает свои. Вы же не считаете, что “банда четырех” описала все возможные паттерны? Например, прекрасная книга Мартина Фаулера “Шаблоны корпоративных приложений” содержит паттерны проектирования приложений, предоставляющих пользователям удаленный доступ к базам данных.

Удачи вам в определении того, чего вам не хватает, и успешного устранения этих пробелов!

***
Если вы хотите наработать необходимую для изучения Data Science математическую базу и подготовиться к углубленным занятиям в «Школе обработки данных» или Computer Science Center, обратите внимание на онлайн-курс «Библиотеки программиста». С помощью опытных преподавателей из ведущих вузов страны сделать это будет намного проще, чем самостоятельно по книгам.

Дополнительные материалы:

09
Авг
2021

Google выпустила Translatotron 2 — улучшенный ИИ для синхронного перевода устной речи. Теперь его нельзя использовать для дипфейка

Исследователи исправили главный недостаток алгоритма для перевода речи Translatotron. Теперь технологию нельзя использовать для создания дипфейков.
— Читать дальше «Google выпустила Translatotron 2 — улучшенный ИИ для синхронного перевода устной речи. …

02
Авг
2021

Twitter запустила соревнование по поиску предубеждений модели машинного обучения. За первое место платят 3,5$ тыс.

Twitter объявила программу по поиску «предупреждений алгоритмов». Это поможет снизить предвзятость моделей машинного обучения к разным социальным группам.
— Читать дальше «Twitter запустила соревнование по поиску предубеждений модели машинного обучения…

06
Июл
2021

В Бельгии искусственный интеллект стыдит политиков, которые используют телефон на заседаниях. И это пугает

Бельгийский художник Дрис Депортер изобрел искусственный интеллект, который автоматически помечает политиков, которые используют телефоны на работе.
— Читать дальше «В Бельгии искусственный интеллект стыдит политиков, которые используют телефон на засе…

05
Июл
2021

🤖 Вариационные автоэнкодеры (VAE) для чайников – пошаговое руководство

Практическое руководство в стиле “сделай сам” с работающим кодом создания и обучения VAE для лиц знаменитостей на Keras.

Текст публикуется в переводе, автор статьи – Мишель Кана.

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

Мотивация

Зачем нужно генерировать новые данные, если в мире и так огромное количество данных? Согласно IDC, в мире более 18 зеттабайтов данных.

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

Как сгенерировать изображения, которых никто не видел?

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

Пример изображения и его реконструкции с помощью нашего кода VAE
Пример изображения и его реконструкции с помощью нашего кода VAE

Данные

Мы используем подмножество широко известного набора данных Знаменитостей, который поможет нам создать модель генерации лиц. Этот набор можно скачать с сайта CelebFacesA. Он предоставляет большой набор атрибутов лиц, содержащий более 200 тысяч изображений знаменитостей, для каждого из которых указано значение 40 атрибутов.

  • 10.177 личностей;
  • 202.599 изображений;
  • 5 важнейших локаций;
  • 40 бинарных атрибутов для каждого изображения.
        import pandas as pd

df_celeb = pd.read_csv('list_attr_celeba.csv')
df_celeb.head()
    

Ниже мы выбираем случайные лица и выводим их метаданные (атрибуты). Изображения имеют высоту 218 пикселей, ширину 178 пикселей и 3 цветовых канала.

        import matplotlib.pyplot as plt
import random
from skimage.io import imread

def show_sample_image(nb=3, df=df_celeb, verbose=True):
    f, ax = plt.subplots(1, nb, figsize=(10,5))
    for i in range(nb):
        idx = random.randint(0, df.shape[0]-1)
        img_id = df.loc[idx].image_id
        img_uri = 'img_align_celeba/' + img_id
        img = skimage.io.imread(img_uri)  
        if verbose:
            label = img_id
            for col in df.columns:
                if df.loc[idx][col]==1:
                    label = label + '\n' + col  
            if nb > 1:
                ax[i].imshow(img)
                ax[i].set_title(label)
            else:
                ax.imshow(img) 
                ax.set_title(label)
        
    return img, list(df.loc[idx][1:df.shape[1]])
  
sample_img, sample_img_meta = show_sample_image()
    

Что такое автоэнкодер (AE)?

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

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

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

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

Как работают компоненты автоэнкодера
Как работают компоненты автоэнкодера
  • Модель энкодера переводит входное значение X в маленькое плотное представление Z, примерно так же, как работает сверточная нейронная сеть, используя фильтры для усвоения представлений.
  • Модель декодера можно считать генеративной моделью, способной генерировать специфические признаки X’.
  • Энкодер и декодер обычно обучаются вместе. Функция потерь штрафует объединенную сеть за создание выходных лиц, отличающихся от входных лиц.

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

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

Что такое вариационный автоэнкодер (VAE)?

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

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

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

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

Переход от AE к VAE, используя случайные переменные
Переход от AE к VAE, используя случайные переменные

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

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

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

Генератор данных изображений

Давайте создадим (условный) VAE, который сможет обучаться на лицах знаменитостей. Мы используем пользовательский эффективный по памяти генератор Keras, чтобы справиться с нашим большим набором данных (202599 изображений, примерно по 10Кб каждое). Его цель – получать пакеты изображений на лету в процессе обучения.

        import numpy as np

class CustomCelebrityFaceGenerator(Sequence):
    # инициализируем пользовательский генератор
    def __init__(self, df, batch_size, target_height, target_width, conditioning_dim=0):
        self.df = df
        self.batch_size = batch_size
        self.target_height = target_height
        self.target_width = target_width
        self.conditioning_dim = conditioning_dim
        
    # перетасуем данные после каждой эпохи 
    def on_epoch_end(self):
        self.df = self.df.sample(frac=1)
    
    # выберем пакет в виде тензора
    def __getitem__(self, index):
        cur_files = self.df.iloc[index*self.batch_size:(index+1)*self.batch_size]
        X, y = self.__data_generation(cur_files)
        return X, y
    
    # 
    def __data_generation(self, cur_files):
        # инициализируем пустые тензоры для хранения изображений  
        X = np.empty(shape=(self.batch_size, self.target_height, self.target_width, 3))
        Y = np.empty(shape=(self.batch_size, self.target_height, self.target_width, 3))
        # инициализируем пустой тензор для хранения условных переменных
        if self.conditioning_dim > 0:
            C = np.empty(shape=(self.batch_size, self.conditioning_dim))
        
        # проходим циклом по текущему пакету и создаем тензоры 
        for i in range(0, self.batch_size):
            # читаем изображение
            file = cur_files.iloc[i]
            img_uri = 'img_align_celeba/' + file.image_id
            img = skimage.io.imread(img_uri)
            # изменяем размеры изображения
            if img.shape[0] != self.target_height or img.shape[1] != self.target_width:
                img = skimage.transform.resize(img, (self.target_height, self.target_width)) 
            # сохраняем изображение в тензорах 
            img = img.astype(np.float32) / 255.
            X[i] = img
            Y[i] = img
            # сохраняем условные параметры в тензорах
            if self.conditioning_dim > 0:
                C[i] = list(file[1:file.shape[0]])
            
        if self.conditioning_dim > 0:
            return [X, C], Y
        else:
            return X, Y
    
    # получить количество пакетов
    def __len__(self):
        return int(np.floor(self.df.shape[0] / self.batch_size))
    

Нейронная сеть VAE

Мы хотим, чтобы наш энкодер был сверточной нейронной сетью, принимающей изображение и выдающей параметры распределения Q(z | [x,c]), где x – входное изображение лица, c – условная переменная (атрибуты лица), а z – скрытая переменная. В этой статье мы используем простую архитектуру, состоящую из двух сверточных слоев и слоя группировки (pooling).

Декодер – это сверточная нейронная сеть, построенная по-другому. Это генеративная нейронная сеть, выдающая параметры распределения похожести P([x,z] | c).

        from keras.layers import Conv2D, MaxPooling2D, UpSampling2D

def get_encoder_network(x, num_filters):  
    x = Conv2D(num_filters, 3, activation='relu', padding='same', kernel_initializer='he_normal')(x)
    x = Conv2D(num_filters, 3, activation='relu', padding='same', kernel_initializer='he_normal')(x)
    x = MaxPooling2D()(x)
    return x

def get_decoder_network(x, num_filters):
    x = UpSampling2D()(x)
    x = Conv2D(num_filters, 3, activation='relu', padding = 'same', kernel_initializer = 'he_normal')(x)
    x = Conv2D(num_filters, 3, activation='relu', padding = 'same', kernel_initializer = 'he_normal')(x)
    return x
    

Вот так выглядит архитектура всей сети VAE:

        from keras.layers import Input, Dense, Reshape, Concatenate, Flatten, Lambda, Reshape
from keras.models import Model
from keras import backend as K
from keras.optimizers import Adam

# функция для создания нейронной сети автоэнкодера 
def get_vae(height, width, batch_size, latent_dim, 
            is_variational=True, conditioning_dim=0,
            start_filters=8, nb_capacity=3, 
            optimizer=Adam(lr=0.001)):
    
    # ВХОД ##
    
    # создаем слой для входного изображения 
    # объединяем метаданные изображений 
    inputs = Input((height, width, 3))
    if conditioning_dim > 0:
        condition = Input([conditioning_dim])
        condition_up = Dense(height * width)(condition)
        condition_up = Reshape([height, width, 1])(condition_up)
        inputs_new = Concatenate(axis=3)([inputs, condition_up])
    else:
        inputs_new = inputs
    
    
    # ЭНКОДЕР ##
    
    # создаем кодирующие слои 
    # дублируем кодирующие слои, увеличивая фильтры 
    eblock = get_encoder_network(inputs_new, start_filters)
    for i in range(1, nb_capacity+1):
        eblock = get_encoder_network(eblock, start_filters*(2**i))
        
    # создаем слой скрытого пространства
    _, *shape_spatial = eblock.get_shape().as_list()
    eblock_flat = Flatten()(eblock)    
    if not is_variational:
        z = Dense(latent_dim)(eblock_flat)
    else:
        # выборка скрытых значений из нормального распределения
        def sampling(args):
            z_mean, z_log_sigma = args
            epsilon = K.random_normal(shape=(batch_size, latent_dim), mean=0., stddev=1.)
            return z_mean + K.exp(z_log_sigma) * epsilon
        
        z_mean = Dense(latent_dim)(eblock_flat)
        z_log_sigma = Dense(latent_dim)(eblock_flat)
        z = Lambda(sampling, output_shape=(latent_dim,))([z_mean, z_log_sigma])
    
    if conditioning_dim > 0:
        z_ext = Concatenate()([z, condition])

        
    ## ДЕКОДЕР ##
    
    # создаем декодирующие статьи
    inputs_embedding = Input([latent_dim + conditioning_dim])
    embedding = Dense(np.prod(shape_spatial), activation='relu')(inputs_embedding)
    embedding = Reshape(eblock.shape.as_list()[1:])(embedding)
    
    # дублируем кодирующие слои, увеличивая фильтры 
    dblock = get_decoder_network(embedding, start_filters*(2**nb_capacity))
    for i in range(nb_capacity-1, -1, -1):
        dblock = get_decoder_network(dblock, start_filters*(2**i))
        
    output = Conv2D(3, 1, activation = 'tanh')(dblock)
    
    ## VAE ##
    
    # объединяем энкодер с декодером 
    decoder = Model(input = inputs_embedding, output = output)
    if conditioning_dim > 0:
        encoder_with_sampling = Model(input = [inputs, condition], output = z)
        encoder_with_sampling_ext = Model(input = [inputs, condition], output = z_ext)
        vae_out = decoder(encoder_with_sampling_ext([inputs, condition]))
        vae = Model(input = [inputs, condition], output = vae_out)
    else:
        encoder_with_sampling = Model(input = inputs, output = z)
        vae_out = decoder(encoder_with_sampling(inputs))
        vae = Model(input = inputs, output = vae_out)
    
    # определяем потери VAE как сумму MSE and потерь расстояния Кульбака-Лейблера
    def vae_loss(x, x_decoded_mean):
        mse_loss = K.mean(mse(x, x_decoded_mean), axis=(1,2)) * height * width
        kl_loss = - 0.5 * K.mean(1 + z_log_sigma - K.square(z_mean) - K.exp(z_log_sigma), axis=-1)
        return mse_loss + kl_loss
        
    if is_variational:
        vae.compile(loss=vae_loss, optimizer=optimizer)
    else:
        vae.compile(loss='mse', optimizer=optimizer)    
        
    return vae, encoder_with_sampling, decoder

# гиперпараметры
VARIATIONAL = True
HEIGHT = 128 
WIDTH = 128 
BATCH_SIZE = 16 
LATENT_DIM = 16
START_FILTERS = 32 
CAPACITY = 3 
CONDITIONING = True 
OPTIMIZER = Adam(lr=0.01)

vae, encoder, decoder = get_vae(is_variational=VARIATIONAL,
                                   height=HEIGHT, 
                                   width=WIDTH, 
                                   batch_size=BATCH_SIZE, 
                                   latent_dim=LATENT_DIM,
                                   conditioning_dim=df_celeb.shape[1]-1, 
                                   start_filters=START_FILTERS,
                                   nb_capacity=CAPACITY,
                                   optimizer=OPTIMIZER)
    

Обучение

Ниже представлен процесс обучения моделей VAE на наборе данных celebA. Этот код выполнялся около 8 часов на инстансе AWS с использованием 1 GPU.

        # делим изображения на тренировочный набор и набор валидации
msk = np.random.rand(len(df_celeb)) < 0.5
df_celeb_train = df_celeb[msk]
df_celeb_val = df_celeb[~msk]

# создаем генераторы изображений для обучения
gen = CustomCelebrityFaceGenerator(df_celeb_train, 
                          batch_size=BATCH_SIZE, 
                          target_height=HEIGHT, 
                          target_width=WIDTH, 
                          conditioning_dim=df_celeb.shape[1]-1)

# создаем генераторы изображений для валидации
gen_val = CustomCelebrityFaceGenerator(df_celeb_val, 
                          batch_size=BATCH_SIZE, 
                          target_height=HEIGHT, 
                          target_width=WIDTH, 
                          conditioning_dim=df_celeb.shape[1]-1)

# обучаем вариационный автоэнкодер
vae.fit_generator(gen, verbose=1, epochs=20, validation_data=gen_val)
    

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

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

        # выбираем случайное изображение
sample_img, sample_img_meta = show_sample_image(nb=1)

# функция для кодирования одного изображения, возвращающая его скрытое представление
def encode_image(img, conditioning, encoder, height, width, batch_size):
    # изменяем размеры изображения
    if img.shape[0] != height or img.shape[1] != width:
        img = skimage.transform.resize(img, (height, width))
    # заполняем изображение, чтобы оно соответствовало размеру пакета
    img_single = np.expand_dims(img, axis=0)
    img_single = img_single.astype(np.float32)
    img_single = np.repeat(img_single, batch_size, axis=0)
    # используем энкодер для вычисления представления в скрытом пространстве
    if conditioning is None:
        z = encoder.predict(img_single)
    else:
        z = encoder.predict([img_single, np.repeat(np.expand_dims(conditioning, axis=0), batch_size, axis=0)])
    return z

# выводим представление в скрытом пространстве, созданное энкодером
z = encode_image(sample_img.astype(np.float32) / 255., 
                 np.array(sample_img_meta), 
                 encoder, HEIGHT, WIDTH, BATCH_SIZE)
print('latent sample:\n', z[0])
    


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

        def decode_embedding(z, conditioning, decoder):
    if z.ndim < 2:
        z = np.expand_dims(z, axis=0)
    if conditioning is not None:
        z = np.concatenate((z, np.repeat(np.expand_dims(conditioning, axis=0), z.shape[0], axis=0)), axis=1)
    return decoder.predict(z)

# восстановим исходное изображение, используя представление скрытого пространства 
ret = decode_embedding(z, sample_img_meta, decoder)
plt.imshow(ret[0])
plt.show()
    

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

Генерируем новые лица

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

        def generate_new_images_vae(nb=16, smiling=None, male=None, no_beard=None, attractive=None, 
                        bald=None, chubby=None, eyeglasses=None, young = None):
    sample_training_img, sample_training_img_meta = show_sample_image(nb=1, verbose=False)
    plt.clf();
    f, ax = plt.subplots(2, nb//2, figsize=(20,7));
    for i in range(nb):
        meta=2*np.random.rand(meta_cols.shape[0])-1
        meta[2] = attractive if attractive else meta[2]
        meta[4] = bald if bald else meta[4]
        meta[13] = chubby if chubby else meta[13]
        meta[15] = eyeglasses if eyeglasses else meta[15]
        meta[20] = male if male else meta[20]
        meta[24] = no_beard if no_beard else meta[24]
        meta[31] = smiling if smiling else meta[31]
        meta[39] = young if young else meta[39]
        z1 = np.random.rand(LATENT_DIM, LATENT_DIM)
        ret = decode_embedding(z1, meta, decoder)
        ax[i%2][i//2].imshow(ret[0])
        ax[i%2][i//2].set_title('generated img {}'.format(i))
    ax[0][0].imshow(sample_training_img)
    ax[0][0].set_title('training img')
    
 generate_new_images_vae()
    

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

От улыбки станет мир светлей

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

        # интерполяция скрытого пространства, чтобы изменить исходное изображение
def display_manifold(decoder, height, width, base_vec, 
                     bound_x=15, bound_y=15, 
                     axis_x=0, axis_y=1, n=15,
                     desc_x = 'x', desc_y = 'y', 
                     file_out=None):
 
    figure = np.zeros((height * (n if bound_y > 0 else 1), width * (n if bound_x > 0 else 1), 3))
    grid_x = np.linspace(-bound_x, bound_x, n) if bound_x > 0 else [0]
    grid_y = np.linspace(-bound_y, bound_y, n) if bound_y > 0 else [0]
    individual_outputs = []

    for i, yi in enumerate(grid_y):
        for j, xi in enumerate(grid_x):
            z_sample = base_vec.copy()
            z_sample[axis_x] = xi 
            z_sample[axis_y] = yi 

            x_decoded = decoder.predict(np.expand_dims(z_sample, axis=0))
            sample = np.clip(x_decoded[0], 0, 1)
            figure[i * height: (i + 1) * height, j * width: (j + 1) * width] = sample
            individual_outputs.append(sample)

    plt.figure(figsize=(10, 10))
    plt.imshow(figure)
    plt.xlabel(desc_x)
    plt.ylabel(desc_y)
    if file_out is not None:
        plt.savefig(file_out, dpi=200, bbox_inches='tight')
    return figure, individual_outputs

# доступные атрибуты
meta_cols = df_celeb.columns[1:].values

# изменяемые атрибуты
dim1 = 'Male'
dim2 = 'Smiling'

# используемое скрытое пространство 
base_vec = np.array(list(z[0]) + sample_img_meta)

# создаем изменения
rendering, _ = display_manifold(
                                decoder, 
                                HEIGHT, 
                                WIDTH, 
                                base_vec, 
                                bound_x=15, 
                                bound_y=15, 
                                axis_x=LATENT_DIM + np.where(meta_cols==dim1)[0][0], 
                                axis_y=LATENT_DIM + np.where(meta_cols==dim2)[0][0], 
                                n=10,
                                desc_x = dim1,
                                desc_y = dim2,
                                file_out = 'rendering_celeba_' + dim1.lower() + '_' + dim2.lower() + '.png'
                                )
    

Заключение

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

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

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

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

Если вы хотите узнать больше об автоэнкодерах, читайте статью Джозефа Рокка «Разбираемся с вариационными автоэнкодерами (VAE)».