Прямая адресация: когда ключ сам и есть номер ячейки

Если ты знаешь, когда прямая адресация выгоднее словаря, сколько памяти стоит битовая шкала и как обойти инициализацию огромного массива, листай до «Теперь сам».

Как думаешь, что быстрее массива

Самая быстрая структура для поиска по ключу, которую ты знаешь, - массив: a[k] за один шаг, без сравнений. Всё, что будет дальше в этом разделе, - попытки получить такую же скорость для ключей, которые индексами не являются.

Прежде чем читать дальше, ответь себе: в офисе выдано десять тысяч пропусков, номер пропуска - от 0 до 999999. Что займёт меньше памяти - массив на миллион флажков «выдан или нет» или множество set из десяти тысяч номеров? Интуиция говорит «множество, ведь 99% массива пусто». Проверим.

На что это похоже

Почтовые ящики в подъезде. У каждой квартиры свой ящик с её номером, и почтальону не нужно ничего искать: письмо в квартиру 57 идёт в ящик 57. Ящик пустой у квартир, где никто не живёт, но он всё равно висит - стена ящиков рассчитана на ВСЕ квартиры дома, а не на нынешних жильцов. Для дома на сотню квартир это удобно. Для «дома» на 2⁶⁴ квартир, где живёт тысяча человек, такую стену не построить - и тут нужен другой способ получить номер ящика.

Механизм: таблица, шкала и ленивая инициализация

ПРЯМАЯ АДРЕСАЦИЯ, ключи 0..U−1
    положить(k, v):  T[k] = v          O(1) в худшем случае
    взять(k):        вернуть T[k]      (пусто - «нет такого ключа»)
    удалить(k):      T[k] = пусто
    память:          U ячеек, сколько бы ключей ни было

БИТОВАЯ ШКАЛА - то же для множества
    бит k хранится в байте k // 8, позиция k % 8
    есть ли k:   (B[k >> 3] >> (k & 7)) & 1
    память:      U / 8 байт

k >> 3 - сдвиг вправо на три разряда, то же, что деление на 8 нацело; k & 7 - три младших бита, то же, что остаток от деления на 8. Это те же операции, просто записанные так, как их делает процессор.

Скрытая цена прямой адресации - заведение массива: обнулить U ячеек стоит Θ(U) времени, даже если потом понадобятся три ключа. Есть приём, который избавляет и от этого, - ленивая инициализация:

два массива без обнуления (там мусор) и счётчик top = 0
T[k]   - номер записи для ключа k (мусор, если ключа нет)
S[i]   - какой ключ записан под номером i, i < top

ключ k есть  ⇔  T[k] < top  и  S[T[k]] == k
положить k:     S[top] = k;  T[k] = top;  top += 1

Мусор в T[k] не обманет проверку: даже если он случайно меньше top, в S под этим номером записан другой ключ. Каждая операция - O(1), а обнуления нет совсем. В Python массивы всегда заполнены значениями, поэтому приём там не нужен; он живёт в C и в ядрах ОС, где выделенная память приходит с чем попало.

Правило

Если ключи - целые из диапазона 0..U−1 и U не намного больше числа ключей, словарь - это массив из U ячеек с ключом в роли индекса: все операции O(1) в худшем случае, коллизий нет. Для множества хватает битовой шкалы в U/8 байт. Память - Θ(U) вне зависимости от числа ключей, поэтому прямая адресация годится, пока U - миллионы, а не 2⁶⁴. Обнуление массива стоит Θ(U); его обходит ленивая инициализация двумя массивами со взаимной проверкой.

Разбор: миллион номеров, десять тысяч пропусков

import random
import sys

U = 1_000_000                       # номера пропусков 0..999999
rng = random.Random(3)
vydany = rng.sample(range(U), 10_000)

tablica = [None] * U                # прямая адресация: ячейка = ключ
for k in vydany:
    tablica[k] = f"сотрудник {k}"

bity = bytearray(U // 8)            # только «есть / нет»: бит на ключ
for k in vydany:
    bity[k >> 3] |= 1 << (k & 7)

mnozh = set(vydany)

print("ячеек занято:", sum(x is not None for x in tablica), "из", U)
print("таблица, байт:", sys.getsizeof(tablica))
print("биты, байт:   ", sys.getsizeof(bity))
print("set, байт:    ", sys.getsizeof(mnozh))
k = vydany[0]
print(tablica[k], bool(bity[k >> 3] >> (k & 7) & 1), k in mnozh)
print("ключ 2**64 в таблицу - ячеек нужно", 2**64)

ячеек занято: 10000 из 1000000
таблица, байт: 8000056
биты, байт:    125057
set, байт:     524504
сотрудник 249523 True True
ключ 2**64 в таблицу - ячеек нужно 18446744073709551616

Три структуры отвечают одинаково, а платят по-разному. Таблица ссылок - восемь мегабайт: миллион ячеек по восемь байт, из них занят один процент. Битовая шкала - 125 КБ, в четыре раза МЕНЬШЕ множества, хотя в ней 99% нулей: один бит на возможный ключ дешевле, чем десятки байт на реальный (и getsizeof ещё не считает сами числа внутри set - это примерно по 28 байт на каждое). Интуиция «пустой массив расточителен» верна для массива ССЫЛОК и неверна для битов.

Где граница? Множество тратит порядка 80 байт на элемент вместе с числом, шкала - U/8 байт на всё. Шкала выгоднее, пока n · 80 > U / 8, то есть пока ключей больше, чем примерно U/640. На миллионе номеров это полторы тысячи ключей - у нас их десять тысяч.

Разбор: ленивая инициализация по шагам

U = 10, T и S полны мусора, top = 0
T = [7, 3, 0, 9, 2, 5, 1, 8, 4, 6]      (мусор)

есть ли 4?   T[4] = 2,  2 < top = 0?  нет  → ключа нет
положить 4:  S[0] = 4, T[4] = 0, top = 1
положить 7:  S[1] = 7, T[7] = 1, top = 2

есть ли 4?   T[4] = 0 < 2,  S[0] = 4  → есть
есть ли 2?   T[2] = 0 < 2,  но S[0] = 4 ≠ 2  → нет (мусор в T[2] случайно
             оказался «правдоподобным», но S его разоблачил)

Ключ 2 - ровно тот случай, ради которого нужна вторая проверка: мусорное значение T[2] = 0 указывает на настоящую запись, но запись принадлежит другому ключу.

Что ломается без этого

Первая ошибка - заводить словарь там, где хватило бы массива: идентификаторы от 1 до 10 000, а вместо списка на 10 001 ячейку - dict, который вычисляет хеш на каждой операции, медленнее и занимает больше памяти. Вторая - наоборот, массив под «маленький» диапазон, который на деле не маленький: номер телефона, отметка времени в миллисекундах, 32-битный адрес. [None] * 2**32 - это 32 ГБ ссылок, программа падает с MemoryError на первой строке. Третья - забыть, что прямую адресацию нельзя применить к ключам, которые не являются небольшими целыми: строку нельзя превратить в индекс без отображения, а отображение - это уже хеширование со всеми его коллизиями.

Зачем это в работе

Битовые шкалы повсюду, где ключи плотные: свободные блоки в файловой системе (бит на блок диска), свободные страницы памяти в ядре, занятые порты, «эти пользователи видели уведомление» в базах данных (сжатые битовые карты по идентификаторам). Таблица прямой адресации - это таблица переходов по коду символа в лексерах и автоматах, массив count в сортировке подсчётом из раздела про сортировки и таблица дескрипторов открытых файлов в ОС: дескриптор - это просто индекс. Каждый раз, когда ключ - небольшое целое, сначала спроси, нужен ли тут словарь вообще.

Теперь сам

Ключи - номера дней года (0..365), значения - температура. Сколько ячеек нужно таблице прямой адресации? А если ключи - даты за последние сто лет, записанные как число ГГГГММДД (например, 20261028)? Что сделать, чтобы прямая адресация снова стала выгодной?