Алгоритмы и структуры данных

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

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

Что нужно понимать

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

Основные темы

Алгоритмы

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

• Поиск и фильтрация
• Сортировка и упорядочивание
• Группировка и агрегация
• Обход вложенных структур
• Удаление дубликатов

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

От того, как организованы данные, зависит, какие операции дёшевы, а какие дороги.

• List — упорядочен, добавление в конец дёшево, поиск дорог
• Map — почти мгновенный доступ по ключу
• Set — проверка принадлежности и уникальность
• Очередь и стек — порядок обработки
• Дерево и граф — вложенные и связанные данные

Сложность

Способ говорить о росте, ничего не измеряя.

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

Уровни

Уровень	Как это выглядит
Junior	Правильно пользуется List и Map. Может написать рабочий поиск или цикл группировки.
Middle	Замечает вложенный цикл по растущей коллекции и берёт вместо него Map или Set. Может объяснить, почему экран стал тормозить.
Senior	Выбирает структуру по тому, как к данным будут обращаться, ещё до того, как написан код. Понимает, когда медленное решение стоит оставить в покое, потому что объём данных ограничен.

Практика

Для начала

• Найти один элемент Найдите элемент по id, имени или статусу и аккуратно обработайте случай «не найдено».

• Сгруппировать список Сгруппируйте записи по категории, дате или владельцу и покажите группы на экране.

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

Дальше

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

• Поменять структуру Замените линейный поиск внутри цикла обращением к Map и измерьте оба варианта.

• Обойти дерево Обработайте вложенные данные — комментарии, категории, меню, таблицу маршрутов — так, чтобы рекурсия не вышла из-под контроля.

Проверьте себя

• Как вы решаете, что простого цикла достаточно?
• Когда список перестаёт быть удобным и лучше взять Map или Set?
• По каким признакам видно, что код делает одну и ту же работу несколько раз?
• Как проверить, что решение выдержит в сто раз больше данных?
• Когда более медленное, но простое решение — верный выбор?
• Как объяснить алгоритмический компромисс тому, кто не хочет об этом слышать?

Материалы

• Grokking Algorithms — единственная книга, которую стоит прочитать, если эта тема так и не уложилась в голове. С иллюстрациями, короткая и написанная для практикующих разработчиков, а не для тех, кто готовится к экзамену.
• Big-O Cheat Sheet — сложность всех распространённых структур и алгоритмов сортировки на одной странице. Стоит держать открытой, пока выбираете.
• dart:collection — что Dart на самом деле даёт помимо List и Map: связные списки, очереди, splay-деревья, неизменяемые представления.
• Iterable collections codelab — официальный разбор операций над коллекциями в Dart, включая ленивые, которые незаметно избавляют от лишнего прохода. Запускается прямо в браузере.
• Data Structure Visualizations — пошаговые анимации от Университета Сан-Франциско. Самый быстрый способ прочувствовать, как ведут себя дерево или хеш-таблица.