Оглавление:
1. Сравнение скорости поиска в разных типах контейнеров
2. Хэш функция
3. Множества
4. Словари
Сравнение скорости поиска в разных типах контейнеров
В данной статье мы разберемся в устройстве работы структуры данных "хэш таблица". А также посмотрим на dict и set в python, которые являются ее реализациями.
Давайте разберем простой пример. Будем искать иголки в стоге сена. Давайте используем для поиска разные типы контейнеров, такие как list, array, set, и сравним результаты по скорости работы и памяти.
1. Список
2. Множество
3. Словарь
from random import shuffle
import time
# 1. список
def list_test(длина_стога: int):
иголки = [f"иголка{i}" for i in range(1, длина_стога // 2 + 1)]
стог_сена = [f"сено{i}" for i in range(1, длина_стога // 2 + 1)]
стог_сена_с_иголками = стог_сена + иголки
shuffle(стог_сена_с_иголками) # перемешиваем
найденно_иголок = 0
время_старта = time.process_time()
# поиск иголок в стоге сена
for иголка in иголки:
if иголка in стог_сена_с_иголками:
найденно_иголок += 1
время_финиша = time.process_time()
print(f"Время поиска: {время_финиша - время_старта}")
# 2. множество
def set_test_and(длина_стога: int):
иголки = {f"иголка{i}" for i in range(1, длина_стога // 2 + 1)}
стог_сена = {f"сено{i}" for i in range(1, длина_стога // 2 + 1)}
стог_сена_с_иголками = стог_сена.union(иголки)
# множество не упорядочено, поэтому не нужно перемешивать
время_старта = time.process_time()
найденно_иголок = len(стог_сена_с_иголками & иголки)
время_финиша = time.process_time()
print(f"Время поиска: {время_финиша - время_старта}")
def set_test(длина_стога: int):
иголки = {f"иголка{i}" for i in range(1, длина_стога // 2 + 1)}
стог_сена = {f"сено{i}" for i in range(1, длина_стога // 2 + 1)}
стог_сена_с_иголками = стог_сена.union(иголки)
# множество не упорядочено, поэтому не нужно перемешивать
найденно_иголок = 0
время_старта = time.process_time()
for иголка in иголки:
if иголка in стог_сена_с_иголками:
найденно_иголок += 1
время_финиша = time.process_time()
print(f"Время поиска: {время_финиша - время_старта}")
# 3. словарь
def dict_test(длина_стога: int):
иголки = {f"иголка{i}": f"иголка{i}" for i in range(1, длина_стога // 2 + 1)}
стог_сена = {f"сено{i}": f"сено{i}" for i in range(1, длина_стога // 2 + 1)}
стог_сена_с_иголками = {**стог_сена, **иголки}
найденно_иголок = 0
время_старта = time.process_time()
for иголка in иголки:
if иголка in стог_сена_с_иголками:
найденно_иголок += 1
время_финиша = time.process_time()
print(f"Время поиска: {время_финиша - время_старта}")
if __name__ == "__main__":
for i in (1_000, 10_000, 100_000):
print(f"\nДлина стога: {i}")
print("list_test")
list_test(i)
print("set_test")
set_test(i)
print("set_test_&")
set_test_and(i)
print("dict_test")
dict_test(i)
Результаты:
Длина стога: 1000
list_test
Время поиска: 0.002118000000000002
set_test
Время поиска: 2.9999999999998778e-05
set_test_&
Время поиска: 3.099999999999978e-05
dict_test
Время поиска: 2.6000000000001716e-05
Длина стога: 10000
list_test
Время поиска: 0.230395
set_test
Время поиска: 0.00020999999999998797
set_test_&
Время поиска: 0.0002449999999999952
dict_test
Время поиска: 0.00023300000000003873
Длина стога: 100000
list_test
Время поиска: 30.181850999999998
set_test
Время поиска: 0.0023879999999998347
set_test_&
Время поиска: 0.002214999999999634
dict_test
Время поиска: 0.0043899999999972295
Из результатов мы видим: время поиска в множестве и словаре всегда меньше, чем в списке.
Интересно отметить, что для маленьких объемов поиск в словаре может занимать меньше времени, чем в множестве. Но по мере увеличения объема данных, скорость поиска в множестве начинает превосходить скорость поиска в словаре.
Хэш функция
Секрет скорости множества кроется в работе хэш функции. Хэш функция вычисляет хэш код объектов.
Хэш код - вычисляемое хэш функцией число, которое не должно изменятся за время жизни объекта. Хэш код уникален для объектов с одинаковым значением (для равных объектов).
В Python хэш объекта можно получить при помощи вызова функции hash(obj).
>>>hash("пример")
879022618586346326
>>> hash(123)
123
>>> hash(None)
-9223372036583950046
В Python при каждом запуске программы хэш объектов может отличаться, т.к. к нему всегда добавляется разная соль. Это сделано в целях безопасности. Подробнее https://mail.python.org/pipermail/python-dev/2011-December/115116.html
Хэш функция работает напрямую со встроенными типами данных, такими как int, float, str, tuple, frozenset.
Для пользовательских типов данных хэш функция вычисляет значение вызовом метода __hash__. Если метод не определен, объект считается нехэшируемым.
Если два объекта равны, их хэши тоже равны. Например:
10 == 10.0
>>>True
hash(10) == hash(10.0)
Также, для эффективной работы в роли индекса хэш таблицы, хэш коды должны как можно сильнее быть разбросаны по всему диапазону значений хэша. В идеальных условиях, одинаковые, но не равные объекты должны иметь сильно отличающиеся хэш.
В 64 битном CPython - это число имеет 2^62 возможных значения. Но объектов может быть гораздо больше. Поэтому хэш код обычно несет в себе меньше информации, чем значение объекта. Это значит, что хэш коды разных объектов могут совпадать.
Множества
Множество - это структура данных, которая хранит уникальные элементы. Множество в Python реализовано на основе хэш таблицы.
Множество хранит только хэш коды и ссылки на объекты.
"Строчка" в множестве называется бакетом (Bucket).
Множества используют хэш функцию для вычисления позиции (Offset) объекта внутри себя. Эту позицию можно назвать индексом с оговоркой, что эти "индексы" множество не хранит, а вычисляет каждый раз как
хэш объекта % длина множества.
Например, у нас есть строка "иголка2" и мы хотим вставить ее в пустое множество.
Множество сначала вычислит хэш, затем определит позицию для нового элемента и запишет в эту позицию хэш объекта и ссылку на него.
Если мы вставляем новый объект в множество и на вычисленной для объекта позиции уже находится элемент, множество проверяет, совпадают ли хэши этих объектов. Такая ситуация называется коллизией индексов. Если хэши не совпадают, множество решает коллизию, например: увеличивая позицию элемента на 1, пока не найдет пустое место. Это не самый эффективный алгоритм разрешения коллизий, в Python для этого используется linear probing с генерацией псевдослучайных чисел.
Если же хэш код нового и записанного объекта совпадает, множество сравнивает значения объектов. Ситуацию с совпадением хэшей объектов называют коллизией хэша. Если значение объектов совпадают - новый элемент не будет добавлен, так как множество считает, что такой элемент уже находится в нем.
Алгоритм вставки в множество представлен на рисунке:
Поиск элементов происходит аналогично вставке. Сначала вычисляется хэш код объекта, а затем позиция. Если бакет на этой позиции пуст - объекта нет в множестве. Если бакет не пуст, то множество сравнивает значения объекта в бакете с искомым объектом. Если они равны - объект есть в множестве. Если объекты не равны, то нужно проверить следующие позиции, так как при вставке могла быть коллизия хэш кода. Если на следующих позициях объект не найден - его нет в множестве.
Для эффективной работы множеству необходимо не менее 1/3 свободного места. Это связано с тем, что при увеличении количества элементов в множестве, увеличивается вероятность коллизий. Поэтому, когда свободного места становится мало, множество увеличивает свою длину в 2 раза.
При увеличении длины множество заново перезаполняет все свои элементы так, чтобы они находились на позиции хэш объекта % новая длина множества.
В среднем, сложность вставки, поиска и удаления для множества равны O(1). Но в наихудшем случае (при коллизии хэш кодов всех элементов) сложность может достигать O(n).
Словари
Словарь - множество пар ключ, значение. Ключи в словаре уникальны. Ключом могут быть только иммутабельные объекты (объекты, значение которых не изменяется за все время их жизни)
Словари также реализованы при помощи хэш таблицы. Но их структура немного сложнее множества. В множестве мы хранили один объект и искали его при помощи его хэш кода. Ключ (Key) словаря используется для вставки и поиска в словаре. По хэш коду ключа определяется индекс бакета (позиция) в словаре. Значение (Value) словаря может быть любым объектом. Они могут быть не уникальными и повторяться в словаре для разных ключей.
Для эффективной работы словаря, после заполнения 1/3 места его длина увеличивается вдвое. Но в исходном коде есть комментарий о том, что и при 2/3 максимального свободного места проблем быть не должно (https://github.com/python/cpython/blob/main/Objects/dictobject.c#L547).
Если сделать словарь множеством с дополнительным полем - ссылкой на объект-значение, то по мере роста длины словаря пустые бакеты начнут занимать слишком много памяти. В 64-битном CPython под каждое поле словаря (хэш код ключа, ссылка на ключ, ссылка на значение) занимает 64 бита, даже если оно пустое. Это значит, что каждая строчка в словаре будет занимать 192 бита, при том что минимум 2/3 из всех строк словаря пустые.
Чтобы сэкономить память, словари сделали компактными в Python 3.3. Словарь разбили на индексы (Indices) и записи (Entries). Индексы представляют массив байт. Такого массива достаточно для индексации до 128 записей. По мере роста словаря может потребоваться индексировать больше записей, поэтому массив индексов может измениться на 2-х байтовый, 3-х байтовый и т.д. В индексах числа -1 и -2 являются специальными значениями. -1 обозначает пустой бакет, а -2 - удаленный.
Позиция индексов, которая вычисляется по хэш коду, указывают на индекс записи. Записи хранят в себе хэш код, ссылку на ключ и ссылку на значение.
При вставке пары ключа, значение в словарь мы сначала вычисляем позицию индекса по формуле хэш ключа % длина словаря. Если бакет на данной позиции пуст (т.е. в массиве индексов на данной позиции находится число -1 или -2), то мы добавляем новое значение в записи и записываем в массив индексов индекс нового элемента из записей.
Благодаря тому, что в записи мы вставляем элементы последовательно по мере заполнения словаря, у компактного словаря появилась упорядоченность по добавлению ключей. Мы можем итерироваться по записям в том же порядке, в котором ключи вставляли в словарь.
Так же как и в множестве: сложность вставки, поиска и удаления для словаря равны O(1). Но в наихудшем случае (при коллизии хэш кодов всех элементов) сложность может достигать O(n).
Чтобы лучше разобраться в теме, попробуйте ответить на вопрос:
Какая длина у данного словаря?
dict({True: 1, 1: 11, 1.0: 111})
Помните, что равенство хэш кодов проверяется как:
hash(a) == hash(b)
А равенство объектов как:
a == b
Знания о том, что скрывают внутри себя Set и Dict, помогут вам правильно выбирать тип данных в Python, а также блеснуть эрудицией на собеседовании или во время работы.
Больше статей в https://t.me/firstexpedu.
