Экспресс-курс · No. 23
Структура данных — это просто способ организовать данные так, чтобы то, что ты делаешь чаще всего, было быстрым. Выбери правильную — и операция мгновенна; выбери неверную — и та же задача ползёт. Big-O — это язык для этой разницы: как стоимость операции растёт по мере роста данных. Выучи пару структур и нотацию, и «почему это медленно?» обычно отвечает само на себя.
Только суть · Один образ на идею · Выучи слова
До конкретных структур — идея за всеми ними. Структура данных не академична: это та единственная выбор, что чаще всего решает, быстр твой код или мучительно медлен.
Структура данных организует данные под операции, что делаешь чаще
Опрятный ящик инструментов с помеченными гнёздами против кучи инструментов в мешке — те же инструменты, но один даёт схватить нужный мгновенно, а другой значит копаться каждый раз.
Структура данных (data structure) — это способ расположить данные в памяти. Разные расположения делают быстрыми разные операции: одно отлично ищет вещи по имени, другое держит порядок, третье всегда хватает самый свежий элемент. Вся игра — подобрать структуру под то, что ты будешь делать чаще всего, потому что расположение, что делает одну операцию мгновенной, часто делает другую медленной. Выбирай под свой частый случай.
Правильная структура превращает сложное в простое
Найти слово в отсортированном словаре занимает секунды; найти его в тех же словах, сваленных в случайном порядке, может занять весь день. Те же данные, расположение — это всё.
Та же задача может быть тривиальной или почти невозможной в зависимости от того, как держатся данные. Найти пользователя по ID мгновенно в одной структуре и тягомотина через всё в другой. Так что удивительно много «сделай это быстрым» — на деле «храни это в правильной форме». Хороший выбор заранее часто бьёт любую хитрую оптимизацию потом — структура и есть решение.
Каждая структура — это размен
Спорткар и грузовик для переезда — оба транспорт; ты не спрашиваешь, какой лучше, ты спрашиваешь — лучше для чего. Скорость в одном оплачена ценой в другом.
Ни одна структура не лучшая во всём. Одна даёт мгновенный поиск, но без порядка; другая держит порядок, но медленна в поиске; третья быстра на добавление, но медленна в нахождении внутри. Выбирать — значит знать, что ты оптимизируешь и чем готов поступиться. Бесплатного обеда нет — каждая структура меняет силу в одной операции на слабость в другой, и твоя работа — выбрать размен, что подходит твоему использованию.
Структура данных организует данные так, чтобы твои частые операции были быстрыми. Правильная форма превращает сложную задачу в лёгкую — и каждая структура меняет скорость в одной операции на слабость в другой.
Чтобы сравнивать структуры, нужен способ говорить о скорости, что не зависит от машины. Big-O — это тот язык: он меряет, как растёт работа по мере роста данных.
Big-O меряет рост, а не секунды
Спрашивать не сколько занимает одна доставка, а как меняется общее время, когда маршрут идёт от десяти остановок к десяти тысячам, — форма роста, а не показание секундомера.
Нотация Big-O описывает, как растёт стоимость операции по мере роста объёма данных, называемого n. Она игнорирует точные миллисекунды и конкретный компьютер и схватывает форму: удвоение данных удваивает работу, учетверяет её или едва меняет? Эта форма и решает, останется ли что-то быстрым в масштабе, так что Big-O — это как инженеры сравнивают подходы, ни разу их не запустив.
Частые формы, от отличной до ужасной
Четыре способа, как дело масштабируется: одно остаётся одним шагом независимо от кучи, одно растёт с кучей, одно взрывается как куча в квадрате, а одно едва растёт, даже когда куча да.
Несколько форм покрывают большинство кода. O(1) — константа — занимает то же время независимо от размера (взять элемент по индексу). O(n) — линейная — растёт в ногу с данными (просмотр списка). O(n²) — квадратичная — взрывается с ростом данных (сравнить каждый элемент с каждым) и это классическое «нормально в тестах, умирает в проде». O(log n) — логарифмическая — едва растёт, даже когда данные раздуваются (деление поиска пополам каждый шаг). Знать, какой формы твоя операция, говорит, переживёт ли она масштаб.
Форма важна только в масштабе
Два маршрута, что идентичны для короткой поездки, дико расходятся на длинной, — разница невидима, пока дистанция не станет достаточно большой, чтобы её вскрыть.
Для десяти элементов любая структура кажется мгновенной — различия не проявляются. Big-O — про то, что происходит, когда n становится большим: на миллионе элементов подход O(n²), что был нормален в твоём тесте, теперь молотит минутами, пока O(n) заканчивает мгновенно. Поэтому вещи «вдруг» становятся медленными в проде: плохая форма была там всегда, просто скрыта, пока данные не выросли. Думай о форме, прежде чем масштаб её вскроет.
Big-O меряет, как растёт работа с данными, а не сырые секунды. O(1) и O(log n) переживают масштаб; O(n) честна; O(n²) нормальна в тестах и умирает в проде.
Самая базовая структура — массив, или список: упорядоченная последовательность элементов. Знать ровно, в чём он быстр и медлен, задаёт базовую линию для всего остального.
Массив — это упорядоченная, нумерованная последовательность
Ряд нумерованных шкафчиков: элементы сидят по порядку, и у каждого есть позиция — шкафчик 0, шкафчик 1, шкафчик 2 — так что можно пойти прямо к любому по его номеру.
Массив (array, или список, list) хранит элементы по порядку, каждый на нумерованной позиции, называемой индекс (index), начиная с 0. Поскольку элементы сидят в известной, непрерывной раскладке, прыжок к любой позиции по её индексу мгновенен — O(1). Массивы — дефолт для «кучи вещей по порядку», и этот прямой доступ-по-позиции — их суперсила. Когда знаешь, где что-то, оно у тебя немедленно.
Быстр по позиции, медлен в поиске по значению
Ты можешь открыть шкафчик 500 мгновенно — но если знаешь лишь, что внутри, а не какой шкафчик, придётся открывать их один за одним, пока не найдёшь.
Загвоздка: массив быстр, только когда знаешь индекс. Чтобы найти элемент по его содержимому — «есть ли этот email в списке?» — надо проверить каждый по очереди, что O(n), медленно для больших списков. Так что массив идеален, когда обращаешься по позиции, и плох, когда ищешь по значению. Этот разрыв — ровно та проблема, что решает следующая структура.
Вставка в середину дорога
Чтобы вставить новую книгу в середину набитой, нумерованной полки, каждая книга после неё должна сдвинуться на одно место, освобождая его, — маленькая вставка, много сдвигания.
Добавлять или удалять в конце массива дёшево, но вставка или удаление в середине означает сдвиг всего после неё, чтобы сохранить порядок и нумерацию, — O(n). Так что массивы идеальны, когда ты в основном читаешь по позиции и добавляешь в конец, и плохо подходят, когда постоянно вставляешь и удаляешь в середине. Подбирай их под доступ-по-индексу, тяжёлую-добавлением работу.
Массив — это упорядоченная, индексированная последовательность: мгновенный доступ по позиции, но O(n) на поиск по значению или вставку в середину. Отлично для чтения-по-индексу, тяжёлой-добавлением работы.
Если одна структура заслуживает быть твоей рабочей лошадкой по умолчанию — это хеш-таблица. Она решает крупнейшую слабость массива — нахождение вещей по значению — и делает это почти мгновенно.
Хеш-таблица хранит пары ключ-значение
Телефонная книга: ты ищешь человека по имени и мгновенно получаешь его номер. Ты не сканируешь каждую запись — имя ведёт тебя прямо к ответу.
Хеш-таблица (hash map, также словарь, hash table или просто map) хранит данные как пары ключ-значение (key-value): ты даёшь ей ключ, она даёт совпадающее значение. Найди пользователя по его ID, настройку по её имени, счётчик по слову — напрямую, по ключу. Где массив вынуждает знать позицию, хеш-таблица даёт находить по осмысленному имени. Это структура для «найди это по его идентификатору».
Поиск фактически мгновенен
Волшебный шкаф с документами, что по метке открывается прямо на нужном ящике, не проверяя другие, — число ящиков его не замедляет.
Магия хеш-таблицы в том, что поиск по ключу фактически O(1) — постоянное время, независимо от того, сколько элементов она держит. Она использует ключ, чтобы вычислить ровно, где живёт значение, так что прыгает прямо туда, а не ищет. Миллион записей или десять — найти одну так же быстро. Поэтому хеш-таблица — рабочая лошадка: она делает «найди по имени» мгновенным, а это то, что программы делают постоянно.
Множество: членство без значений
Список гостей у двери — тебе не нужны детали, только «да или нет»: есть ли это имя в списке? Мгновенно проверено, без сканирования.
Близкий родственник — множество (set): хеш-таблица, что хранит только ключи, без значений, чтобы быстро отвечать на один вопрос — «присутствует ли эта вещь?». Проверка членства и избегание дубликатов оба O(1). Каждый раз, как ловишь себя на сканировании списка, чтобы спросить «видел ли я это уже?», множество превращает эту медленную O(n)-проверку в мгновенную. Тянись к нему ради уникальности и быстрых проверок членства.
Хеш-таблица находит значение по его ключу фактически за O(1) — рабочая лошадка для поиска по идентификатору. Её родственник множество отвечает на «присутствует ли это?» так же мгновенно.
Иногда порядок, в котором ты вынимаешь вещи, важен так же, как и то, что ты хранишь. Две структуры формализуют два естественных порядка — и разница между ними это одно интуитивное правило.
Стек — это последним вошёл, первым вышел
Стопка тарелок: ты добавляешь сверху и берёшь сверху, так что последняя тарелка, что ты положил, — первая, что ты берёшь.
Стек (stack) следует LIFO — last in, first out (последним вошёл, первым вышел). Ты добавляешь («push») и удаляешь («pop») с одного конца, так что самый свежий элемент выходит первым. Это подходит всему, что вкладывается или разматывается в обратном порядке: история отмены, кнопка «назад», стек вызовов программы. Обе операции O(1). Когда естественный порядок — «свежее первым» или «отмени последнее», тебе нужен стек.
Очередь — это первым вошёл, первым вышел
Линия у билетной кассы: людей обслуживают в порядке прихода, новички встают в хвост, а перед обслуживается следующим.
Очередь (queue) следует FIFO — first in, first out (первым вошёл, первым вышел). Ты добавляешь в хвост и удаляешь с переда, так что элементы обрабатываются в порядке прихода. Это структура для честности и порядка: задачи на обработку, ждущие работы, запросы на обработку по очереди — ровно идея очереди сообщений из курса об очередях. Как и у стека, её операции O(1). Когда порядок прихода должен быть порядком обработки, тебе нужна очередь.
Правило определяет поведение
Та же куча работы, две двери: одна возвращает самый свежий элемент, другая — самый старый. Единственный выбор, с какого конца, меняет всё ниже по течению.
Стеки и очереди держат один и тот же вид данных; единственная разница — с какого конца ты удаляешь, и это одно правило формирует всё поведение. Выбирать между ними — значит выбирать порядок, в котором твоя работа возвращается: обратный и вложенный (стек) или честный и последовательный (очередь). Это маленькое решение с большим эффектом — возьми порядок верно, и остальная логика встанет на место.
Стек — это последним-вошёл-первым-вышел: отмена, вложенность, разворот. Очередь — это первым-вошёл-первым-вышел: честная, по-порядку обработка. Те же данные; конец, с которого удаляешь, — это вся разница.
Последние две структуры работают с данными, что не плоская линия, а имеют форму, — с вещами, что ветвятся в иерархии или соединяются в сети. Это как ты моделируешь отношения.
Дерево — это иерархия
Генеалогическое древо или оргструктура компании: одна вещь наверху, ветвящаяся вниз в детей, каждый из которых может ветвиться дальше, — структура, что расходится веером, никогда не зацикливается назад.
Дерево (tree) организует данные как иерархию: корень наверху, ветвящийся в узлы (nodes), у которых есть дети, и так вниз. Оно моделирует всё вложенное — папки внутри папок, комментарии и их ответы, меню категорий. Ветвящаяся форма зеркалит реальную вложенность, что делает деревья естественным выбором, когда твои данные — «вещи внутри вещей». Большинство иерархий, что встречаешь в софте, — деревья под низом.
Сбалансированное дерево ищет за O(log n)
Найти имя в телефонной книге, открыв середину, потом середину правой половины, снова и снова, — каждый шаг выбрасывает половину того, что осталось.
Хорошо организованное (сбалансированное, balanced) дерево даёт мощное свойство: его можно искать за O(log n), многократно деля пространство пополам, как ты находишь слово в словаре, не читая каждую страницу. Эта логарифмическая форма едва растёт, даже когда данные взрываются, — миллиард элементов это всего около тридцати шагов. Так базы держат поиск быстрым в огромном масштабе: упорядоченные данные в форме дерева, искомые делением пополам.
Граф — это сеть связей
Карта городов, соединённых дорогами, или людей, соединённых дружбами, — вещи, связанные друг с другом в любом узоре, без верха и без низа.
Граф (graph) — самая общая форма: узлы (nodes), соединённые рёбрами (edges), в любом узоре, включая петли. Он моделирует сети — социальные связи, дороги между городами, ссылки между страницами, зависимости между задачами. Каждый раз, как данные фундаментально «вещи, связанные с другими вещами», а не иерархия или линия, — это граф. Многие сложные, интересные задачи — кратчайший маршрут, кто с кем связан — это в основе графовые задачи.
Дерево моделирует иерархию и, будучи сбалансированным, ищет за O(log n) делением пополам. Граф моделирует сеть связей. Используй их, когда у данных есть форма — вложенная или связанная.
Ты редко строишь их с нуля — твой язык их предоставляет. Навык — выбрать правильную под задачу и знать достаточно Big-O, чтобы почуять плохой выбор до того, как он укусит.
Выбирай по операции, что делаешь чаще
Ты заполняешь кухню по тому, что готовишь каждый вечер, а не по тому, что выглядит впечатляюще, — правильные инструменты те, что под твою реальную, повторяющуюся работу.
Практическое решение почти всегда: какую операцию я буду делать чаще всего, и какая структура делает её быстрой? Поиск по ключу, постоянно? Хеш-таблица. Нужны вещи в порядке прихода? Очередь. В основном чтение по позиции? Массив. Дай доминирующей операции выбрать структуру и прими, что она будет медленнее в том, что ты делаешь редко. Оптимизируй частый случай; структура — это как.
Тянись к таблице, прежде чем тянуться к циклу
Прежде чем искать кого-то в толпе лицо за лицом, ты проверяешь, нет ли списка гостей, — список отвечает мгновенно на то, что поиск делает медленно.
Чрезвычайно частый, чрезвычайно эффективный ход: когда ловишь себя на сканировании списка, чтобы найти или сопоставить вещи — O(n)-цикл или хуже O(n²)-цикл внутри цикла, — спроси, не могла бы хеш-таблица или множество сделать это мгновенным. Замена вложенного поиска на поиск по таблице — один из самых частых реальных ускорений из всех. Структура, а не более быстрый цикл, обычно и есть починка.
- Какая операция доминирует — поиск, упорядочивание, добавление/удаление — для этих данных? - Поиск по ключу? Хеш-таблица (или множество, для присутствия) это O(1). - Доступ по позиции, тяжёлый добавлением? Массив подходит. - Порядок удаления важен — самый свежий (стек) или самый старый (очередь)? - Вложенные или сетевые данные — дерево или граф? - В масштабе, какой Big-O — и нет ли чего-то тайно O(n²)?
- структура данных — способ организовать данные так, чтобы частые операции были быстрыми. - Big-O / n — как стоимость растёт с размером данных. - O(1) / O(n) / O(n²) / O(log n) — постоянный, линейный, квадратичный, логарифмический рост. - array / list / индекс — упорядоченная, нумерованная последовательность; O(1) по позиции. - hash map / словарь / set — поиск ключ-значение и проверки присутствия за O(1). - stack / queue / LIFO / FIFO — последним-вошёл-первым-вышел и первым-вошёл-первым-вышел. - дерево / граф / node / edge — иерархия и сеть; сбалансированные деревья ищут за O(log n).
- Ты выбираешь структуру по операции, что делаешь чаще, а не по привычке. - Ты тянешься к хеш-таблице или множеству вместо сканирования списка, чтобы найти или дедуплицировать. - Можешь назвать Big-O своего горячего пути, и у тебя нет скрытого O(n²). - Ты используешь стек или очередь, когда важен порядок удаления, и дерево или граф, когда у данных есть форма. - Вещи остаются быстрыми по мере роста данных, потому что ты выбрал форму до того, как масштаб её вскрыл.
Ты не строишь их с нуля — ты их выбираешь. Подбирай структуру под операцию, что делаешь чаще, тянись к таблице прежде цикла, и дай Big-O предупредить тебя раньше, чем масштаб.