Решение реальной проблемы с хорошо известной структурой данных

Это первая статья из новой серии: «Развлечения со структурами данных».

В этой статье мы собираемся решить реальную проблему, используя хорошо известную структуру данных - словари (или хеш-таблицу).

Задача

У нас есть многопользовательская игра на выживание в космосе. Есть игроки, космические корабли, галактики, планеты… И этот список можно продолжить.

Однажды мы решили представить новую функцию:

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

Для простоты предположим, что у каждого космического корабля есть уникальные целые числа 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"

  1. Добавить новое значение для космических кораблей: spaceships[4] = "Starfighter"
  2. Добавить 4 в список ключей: key_list.append(4)
  3. Добавьте индекс нового ключа в сопоставления: 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).

  1. Снять предмет с космических кораблей: del spaceships[40]
  2. Найдите индекс ключа в key_list: index = key_mappings[40]
  3. Замените его последним ключом: 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

Последующая задача

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