TwiddleLab / Код / Структуры данных, которые видно
Множества: а оно там есть?
Что ты узнаешь
- Множество хранит каждый элемент один раз, без определённого порядка. Это хеш-таблица с ключами без значений.
- x in s это один прыжок в шкафчик, а не просмотр: одна скорость для 10 элементов и для 100 миллионов.
- Пересыпь список в множество, и повторы исчезнут: len(set(names)) считает разные имена.
- Множества комбинируются: a & b это то, что есть в обоих, a | b это всё, a - b это только в a.
Как идёт урок
Занято ли «shadow_wolf»?
В игре 100 миллионов имён пользователей. Если проверять по одному, сколько займёт один ответ?
Список или множество: увеличивай число имён.
Множество хранит имена в хеш-шкафчиках, как в прошлом уроке. Двигай до самого верха.
Список понятия не имеет, где имя, поэтому отсутствующее имя значит проверку всех. Множество считает хеш имени, открывает один шкафчик и смотрит только туда.
Пересыпь список гостей в множество.
Некоторые имена набрали дважды. Следи за длиной.
Это множество.
Множество хранит каждый элемент не больше одного раза, без определённого порядка. Внутри это хеш-таблица с ключами без значений.
s = set() создаёт его, s.add(x) кладёт x, x in s задаёт вопрос одним прыжком, len(s) считает элементы.
set(names) превращает список в множество, поэтому len(set(names)) считает разные имена.
Кто на кого подписан?
Разложи каждое имя по тому, в чьём списке оно есть. Это диаграмма Венна из математики, сделанная множествами.
Составь своё множество игр.
Выбери пять. Дальше сравнишь его с друзьями.
У кого с тобой больше всего общих игр?
Нажимай на каждого друга, чтобы увидеть mine & theirs. Оставь выбранным лучшее совпадение, потом «Проверить».
Пересечение a & b оставляет только элементы из обоих множеств. Для каждой игры в твоём множестве компьютер спрашивает «есть в их?», по прыжку на каждую, поэтому сравнение быстрое даже для огромных множеств.
Побудь охранником.
Приходят гости. Уже внутри или впустить? Быстро и без ошибок.
Ещё одна работа для множества: помнить, где уже побывали.
Робот исследует лабиринт. Запусти его без множества, потом с ним.
Предыдущий урок: Хеш-таблицы: как словари находят · Следующий урок: Деревья: папки в папках · Часть курса: Структуры данных, которые видно
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
