Решение реальной проблемы с хорошо известной структурой данных
Это первая статья из новой серии: «Развлечения со структурами данных».
В этой статье мы собираемся решить реальную проблему, используя хорошо известную структуру данных - словари (или хеш-таблицу).
Задача
У нас есть многопользовательская игра на выживание в космосе. Есть игроки, космические корабли, галактики, планеты… И этот список можно продолжить.
Однажды мы решили представить новую функцию:
Каждую секунду игра случайным образом выбирает космический корабль из всех кораблей в игре и телепортирует его в другую галактику. Просто для развлечения.
Для простоты предположим, что у каждого космического корабля есть уникальные целые числа id
и name
. Они хранятся в словаре; id
как ключ и name
как значение.
В игре миллионы космических кораблей. Игроки постоянно создают, уничтожают и обновляют космические корабли.
Наша задача - реализовать алгоритм выбора случайного космического корабля из этого словаря (вернуть случайный элемент из словаря).
Предположения временной сложности:
- Генерация случайного числа: O (1) раз
- Поиск / вставка / удаление в словаре: O (1) раз
- Удаление элемента из списка, O (n) раз
- Добавление элемента в список, раз O (1)
Пример ввода словаря для spaceships
:
spaceships = { 5: "Ghost", 40: "Death Star", 16: "B-wing", ... }
Пример вывода: Death Star
(выбран случайным образом)
Прежде чем читать дальше, я настоятельно рекомендую вам попробовать решить эту задачу самостоятельно.
Первая попытка: сгенерировать случайное int в качестве ключа
Это кажется довольно простым, правда? Просто создайте случайное число и используйте его как ключ для выбора элемента из словаря. Предположим, что у каждого космического корабля есть id
между 0
и 100000000
. В этом интервале легко сгенерировать случайное число:
Разберем этот алгоритм.
Сложность времени: O (1)
Сложность дополнительного места: O (1)
Вот это да. Это настолько хорошо, насколько возможно. Но действительно ли этот алгоритм работает?
No.
Это сработало бы только в том случае, если бы мы были уверены, что в словаре ровно 100000001 элемент и их идентификаторы являются последовательными, начиная с 0. Но помните, игроки могут создавать или уничтожать космические корабли в любое время, когда захотят. Одновременно может быть всего одиннадцать космических кораблей, а в другой - три миллиона. У них есть уникальные идентификаторы, и между ними могут быть пробелы.
Вторая попытка: переместить ключи в список
Хорошо, не так-то просто случайно выбрать элемент из словаря. Как насчет списков? У них есть определенный порядок и длина. Мы легко можем выбрать случайный элемент из списка.
Давайте поместим все ключи из spaceships
словаря в список и выберем случайный элемент из этого списка:
Это определенно работает. (Как насчет гонки за данные?)
Сложность по времени: O (n) для копирования ключей словаря в список.
Сложность лишнего места: O (n) , чтобы ключи оставались в списке.
Что ж, не так уж и плохо. Мы можем позволить себе O (n) памяти.
Но помните, мы будем вызывать эту функцию каждую секунду. Это означает, что это будет стоить O (n) раз каждую секунду. Это будет очень медленно, если будут миллионы космических кораблей.
Неужели нам действительно нужно воссоздавать key_list
каждый раз, когда вызывается get_random_ship
? Можем ли мы сделать лучше?
Третья попытка: словарь картографа
Вместо того, чтобы каждый раз создавать новый список ключей, мы можем создать его один раз и использовать для каждого вызова.
Чтобы сделать это правильно, нам нужно синхронизировать key_list
и spaceships
:
- Каждый раз, когда ключ удаляется из
spaceships
, удаляйте этот ключ изkey_list
- Каждый раз, когда в
spaceships
добавляется новый элемент, добавляйте его ключ вkey_list
Мы можем добавить новые ключи в key_list
за O (1) раз, но как насчет удаления? Нам нужно найти ключ в списке, что займет O (n) времени. Нам также нужно удалить его, что займет еще O (n) раз.
Если бы мы знали положение ключа в списке, мы могли бы просто найти его за O (1) раз, а с помощью хитрого трюка мы могли бы удалить его за O (1) раз.
Если мы хотим получить доступ к чему-либо за время O (1), словари - наш лучший шанс. Пришло время ввести словарь сопоставителя key_mappings
, который сохраняет позиции каждого ключа в key_list
.
Вот снимок трех используемых нами структур данных:
spaceships = { 5: "Ghost", 40: "Death Star", 16: "B-wing", } key_list = [5, 40, 16] key_mappings = { 5: 0, # Key 5 is at position 0 in `key_list` 40: 1, # Key 40 is at position 1 in `key_list` 16: 2, # Key 16 is at position 2 in `key_list` }
Изучая key_mappings
, мы знаем, что ключ 5
находится в позиции 0
в массиве key_list
, ключ 16
находится в позиции 2
и так далее ... Теперь мы можем обновить key_list
за время O (1) за счет дополнительного пространства O (n) key_mappings
.
Давайте рассмотрим пример и добавим новый космический корабль, 4: "Starfighter"
- Добавить новое значение для космических кораблей:
spaceships[4] = "Starfighter"
- Добавить
4
в список ключей:key_list.append(4)
- Добавьте индекс нового ключа в сопоставления:
key_mappings[4] = len(key_list)
spaceships = { 5: "Ghost", 40: "Death Star", 16: "B-wing", 4: "Starfighter", } key_list = [5, 40, 16, 4] key_mappings = { 5: 0, 40: 1, 16: 2, 4: 3, }
Снимем ключ 40
с космических кораблей. Мы знаем, что 40
находится на позиции 1
в key_list
. Хитрость в том, что вместо удаления 40
непосредственно из key_list
мы можем поместить последний элемент в эту позицию за время O (1).
- Снять предмет с космических кораблей:
del spaceships[40]
- Найдите индекс ключа в key_list:
index = key_mappings[40]
- Замените его последним ключом:
key_list[index] = key_list.pop()
spaceships = { 5: "Ghost", 16: "B-wing", 4: "Starfighter", } # Notice that how we moved last element into position 1 key_list = [5, 4, 16] # Notice that we set the value of `4` to 1 and removed key `40`. # Although we can keep key 40 there instead of removing. key_mappings = { 5: 0, 16: 2, 4: 1, }
Временная сложность:
- Один раз O (n) для создания
key_list
- O (1) каждый раз, когда мы обновляем
spaceships
словарь. - O (1), чтобы получить случайный космический корабль.
Космическая сложность:
- O (n) для
key_list
и O (n) дляkey_mappings
Последующая задача
Попробуйте реализовать ту же логику в реляционной базе данных, где космические корабли хранятся в таблице.