TwiddleLab / Код / Структуры данных, которые видно

Выбираем правильную структуру

Урок 9 из 10 · 7 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Нет структуры, лучшей во всём. Каждая быстра в одних задачах и медленна в других: это компромисс.
• Найти по ключу: dict. Есть ли там: set. Сначала новое: стек. Сначала старое: очередь. Сначала срочное: куча. По порядку позиций: список.
• Выбирай по задаче, которую делаешь чаще всего, и считай цену на большом n, например на миллионе.
• Настоящие приложения сочетают несколько структур, и каждая делает ту работу, в которой лучше всех.

Начать урок

Как идёт урок

1. Одна структура на всё?

   Игровое приложение хранит 1 000 000 игроков: найти одного по имени, добавлять новые очки, показывать топ-10.

2. Меняй то, что приложение делает чаще всего.

   Двигай от «в основном поиск» до «в основном топ-10». Смотри, кто побеждает. Побывай на всех трёх отметках.

   dict находит ключ одним прыжком, но для топ-10 должен просмотреть всё. Куча держит верх под рукой, но для поиска имени должна просматривать. Настоящее приложение держит обе и обновляет обе.

3. Какая структура создана для каждой задачи?

   Всё из этого курса в одном месте.

4. Это компромисс.

   Компромисс: стать быстрее в одном, став медленнее в другом. Каждая структура на него идёт.

   При n = 1 000 000: один прыжок (dict, set) лучше примерно 20 шагов (куча, BST), а те лучше просмотра n (поиск в списке).

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

5. Спроектируй бэкенд чат-приложения.

   Дай каждой функции структуру. Сделай все измерители быстрыми, потом «Проверить».

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

6. Магазин структур.

   Приходят задачи. Выдай каждой нужную структуру. Быстро и серией.

7. Это приложение тормозит. Исправь.

   Кто-то хранил всё в списках. Найди медленные функции и подставь структуры получше.

8. Внутри чат-бота.

   ИИ-чат-боты собраны из тех же структур. Сопоставь каждую часть с её структурой.

9. Нагрузочный тест твоего бэкенда.

   Твой дизайн из прошлого шага против «всё в списке» с 1 000 000 пользователей.

Предыдущий урок: Кучи и очереди с приоритетом · Следующий урок: Кнопка «Отменить» и таблица рекордов · Часть курса: Структуры данных, которые видно

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.