Как реализованы встроенные словари Python?
Вот краткий курс:
- Это хеш-таблицы.
- Новая процедура / алгоритм, начиная с Python 3.6, делает их
- заказывается путем вставки ключа и
- занимают меньше места,
- практически без затрат на производительность.
- Другая оптимизация экономит место, когда диктует общие ключи (в особых случаях).
Упорядоченный аспект неофициальный с Python 3.6, но официальный в Python 3.7 .
Словари Python - это хеш-таблицы
Долгое время это работало именно так. Python будет предварительно выделять 8 пустых строк и использовать хеш, чтобы определить, куда нужно вставить пару ключ-значение. Например, если хеш для ключа закончился на 001, он вставил бы его в индекс 1 (как в примере ниже.)
hash key value
null null null
...010001 ffeb678c 633241c4 # addresses of the keys and values
null null null
... ... ...
Каждая строка занимает 24 байта в 64-битной архитектуре, 12 - в 32-битной. (Обратите внимание, что заголовки столбцов - это просто метки - на самом деле они не существуют в памяти.)
Если хеш завершился так же, как хеш существовавшего ранее ключа, это коллизия, и тогда она поместит пару ключ-значение в другое место.
После сохранения 5 значений ключа при добавлении еще одной пары ключ-значение вероятность коллизий хеша слишком велика, поэтому словарь увеличивается в два раза. В 64-битном процессе до изменения размера у нас остается 72 байта пустыми, а после этого мы теряем 240 байтов из-за 10 пустых строк.
Это занимает много места, но время поиска довольно постоянное. Алгоритм сравнения ключей состоит в том, чтобы вычислить хеш, перейти в ожидаемое местоположение, сравнить идентификатор ключа - если это один и тот же объект, они равны. Если нет, то сравните значения хеш-функции, если они равны , а не , они не равны. Иначе, мы наконец сравниваем ключи на равенство и, если они равны, возвращаем значение. Окончательное сравнение на равенство может быть довольно медленным, но более ранние проверки обычно сокращают окончательное сравнение, делая поиск очень быстрым.
(Коллизии замедляют процесс, и злоумышленник теоретически может использовать хеш-коллизии для выполнения атаки типа «отказ в обслуживании», поэтому мы случайным образом сделали хеш-функцию такой, чтобы она вычисляла разные хеш-значения для каждого нового процесса Python.)
Описанное выше потраченное впустую пространство привело к изменению реализации словарей, добавив новую захватывающую (если неофициальную) функцию, которая теперь упорядочивает словари (путем вставки).
Новые компактные хеш-таблицы
Вместо этого мы начинаем с предварительного выделения массива для индекса вставки.
Поскольку наша первая пара ключ-значение идет во второй слот, мы индексируем так:
[null, 0, null, null, null, null, null, null]
А наша таблица просто заполняется порядком вставки:
hash key value
...010001 ffeb678c 633241c4
... ... ...
Поэтому, когда мы ищем ключ, мы используем хеш, чтобы проверить ожидаемую позицию (в этом случае мы идем прямо к индексу 1 массива), а затем идем к этому индексу в хеш-таблице ( например, индекс 0), проверьте, что ключи равны (используя тот же алгоритм, описанный ранее), и, если это так, верните значение.
Мы сохраняем постоянное время поиска, с незначительными потерями скорости в одних случаях и выигрышами в других, с другой стороны, мы экономим довольно много места по сравнению с уже существующей реализацией. Единственный потерянный пробел - нулевые байты в массиве индекса.
Рэймонд Хеттингер представил это python-dev в декабре 2012 года. Наконец-то он попал в CPython в Python 3.6 . Упорядочение путем вставки по-прежнему считается деталью реализации, чтобы другие реализации Python могли наверстать упущенное.
Общие ключи
Еще одна оптимизация для экономии места - это реализация, которая разделяет ключи. Таким образом, вместо наличия избыточных словарей, которые занимают все это пространство, у нас есть словари, которые повторно используют общие ключи и хеши ключей. Вы можете думать об этом так:
hash key dict_0 dict_1 dict_2...
...010001 ffeb678c 633241c4 fffad420 ...
... ... ... ... ...
Для 64-битной машины это может сэкономить до 16 байт на ключ в каждом дополнительном словаре.
Общие ключи для пользовательских объектов и альтернатив
Эти диктовки с общими ключами предназначены для использования с пользовательскими объектами __dict__. Чтобы получить такое поведение, я считаю, что вам нужно закончить заполнение __dict__, прежде чем создавать экземпляр вашего следующего объекта ( см. PEP 412 ). Это означает, что вы должны назначить все свои атрибуты в __init__ или __new__, иначе вы не сможете сэкономить место.
Однако, если вы знаете все свои атрибуты во время выполнения __init__, вы также можете предоставить __slots__ для вашего объекта и гарантировать, что __dict__ вообще не создается (если он недоступен у родителей ), или даже разрешите __dict__, но гарантируйте, что ваши предполагаемые атрибуты в любом случае будут храниться в слотах. Подробнее о __slots__, см. Мой ответ здесь .
Смотри также: