Реализация словаря в Python 2.7

[@Flip89]

Отличная работа!

[@savados]

Занятно, что удаление элементов из словаря не приводит к уменьшению таблицы:

In [1]: d = dict.fromkeys(range(9999))

In [2]: d.__sizeof__()
Out[2]: 786680

In [3]: for k in xrange(9999):
   ...:       del d[k]
   ...:     

In [4]: d.__sizeof__()
Out[4]: 786680

[@Trept]

Так элемент только помечается, как удаленный. Нужна еще физическая чистка словаря, фактически перезагрузка.

[@savados]

Занятно то, что чтобы она произошла, нужно добавить в словарь больше элементов, чем в нем было. Иначе никак.

[@Trept]

Подробный и наглядный обзор часто применяемой структуры.
Что еще планируете разобрать?

[@Delimitry]

Спасибо. Теперь планирую разобраться как устроен словарь в Python 3. Судя по исходникам он претерпел кое-какие изменения.

[@Rembish]

Вот вам задачка на знание, как работает dict в Python'е:

print sum({
    1: 1,
    2: 2,
    1.0: 3,
}.values())

Что выпишет этот код и почему?

[@AlexBin]

Выведет 5

Потому что hash(1)==hash(1.0), что даст один индекс, заменив значение 1 на 3, вместо добавления 3, оставив в результате 2 и 3, которые попадут в sum?

Знак вопроса в конце — это не опечатка.

[@proshev]

В статье этот момент рассмотрен.

[@Tutufa]

5, хеш 1 и 1.0 одинаковый, элементы добавляются последовательно, 1.0 добавляется позже и он перезапишет 1 на 3.

[@overmes]

странно, что все пишут про одинаковый хеш
думаю здесь более значимо то, что 1 == 1.0(True)

разные строки с одинаковым хешем хранились бы обе, так как они не эквивалентны

[@Delimitry]

Совершенно верно. Если хэши значений оказались одинаковыми, сравниваются сами значения. А так как 1 == 1.0, считается что элемент уже есть в словаре и его значение обновляется.

[@AlexBin]

Не претендую на правильность версии, но вы случаем не путаете причину и следствие? Может это 1==1.0 потому что hash(1)==hash(1.0)?

[@Delimitry]

Нет, не путаю. Ведь если бы значения считались равны в случае равенства их хэшей, то два разных значения с одинаковыми хэшами (то есть в случае коллизии) были бы равны, а это неправильно.
В данном случае для сравнения 1 и 1.0 (типы разные — int и float), в соответствии с методом float_richcompare (так как у объекта int не реализован метод tp_richcompare), значения 1 и 1.0 будут приведены к double и сравнены.

[@Tutufa]

Спасибо за пост, надеюсь продолжите про структуры данных и поднаготную питона!

[@Mingun]

Что-то я не очень понял, как такое может быть в пункте 2):

Это единственное состояние, когда me_value != NULL.

А как же тут же рассматриваемые примеры, в которых сплошь и рядом значение me_value не пустое?

[@Delimitry]

При добавлении элемента в ячейку, me_value становится != NULL, то есть она переходит в состояние «активная». Это единственное состояние (имеется ввиду единственное из трёх возможных), когда me_value != NULL. В примерах, в основном, происходит как раз добавление элементов.

[@sheknitrtch]

Спасибо за подробный разбор внутренностей словаря в Python. В очередной раз убеждаюсь, что Python писали инженеры: принимаемые решения обоснованы, перед выбором из нескольких альтернатив всегда проводится тестирование производительности, есть простые правила работы, которые объясняют поведение словаря в любой ситуации. Разработчики даже реализовали свой гибридный алгоритм сортировки Timsort.

[@arusakov]

Насчет устройства словаря в Python очень было приятно послушать доклад с одного из Python Meetup. Может, кому-нибудь пригодится.

[@Delimitry]

Да хороший доклад. Эта ссылка уже есть в статье.

[@leventov]

Двойные стандарты. При хешировании они целые числа никак не перемешивают, и «подряд идущие» строки тоже (кстати, как такое возможно? какая хеш-функция у строки?) типа коллизии на «специально подобранных» случаях их не волнуют, зато потом очень заморачиваются с последовательностью проб, потому что коллизии их, внезапно, заволновали.

Не нравится полная нелокальность последовательности проб.

Нету объяснения, зачем на относительно маленьких таблицах увеличение в 4 раза. Они добиваются тем самым очень маленького среднего коэфф. заполнения, коллизии практически не возникают, и эффект нелокальности последовательности проб не бросается в глаза. Зато потом все жалуются, что Питон жрет много памяти.

По моему опыту, ничего лучше самого простейшего линейного хеширования все равно нет.

[@iroln]

Если кому интересна тема, то вот в этой полезной книге есть целая глава, посвящённая устройству словарей в Python. «Глава 18. Реализация словарей Python: стремление быть всем во всём полезным.» (стр. 331 на google books)

[@splav_asv]

Возможно следует добавить, что начиная с версии 4.4 в качестве hash-функции по умолчанию (для платформ с поддержкой 64 битных чисел) используется SipHash. Она же используется в Ruby, Rust, Perl и Haskel. Вероятно где-то еще.

[@splav_asv]

3.4 конечно же.

[@boov]

Спасибо за статью!

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

[@Delimitry]

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

[@boov]

Спасибо.
Я похоже разобрался, поправьте, если не так.
При разрешении коллизий методом открытой адресации (в отличие от цепочек, где все элементы с одним хэшем расположены в связанном списке) пришлось ввести понятия неиспользованной и пустой ячеек.
Это необходимо для корректной остановки процедуры поиска элемента — останавливаться только, когда элемент найден или попалась неиспользованная ячейка в процессе пробирования (пустая ячейка никак не влияет на процесс)…
В то же время процедура вставки элемента в словарь должна останавливаться, когда найдется либо неиспользованная либо пустая ячейка.

[@Delimitry]

пришлось ввести понятия неиспользованной и пустой ячеек.

Насколько я понимаю, использование флага для определения удалён ли элемент в ячейке или нет, это общепринятая практика в методе открытой адресации. В данном случае флагом служит состояние ячейки.

Это необходимо для корректной остановки процедуры поиска элемента — останавливаться только, когда элемент найден или попалась неиспользованная ячейка в процессе пробирования (пустая ячейка никак не влияет на процесс)…

Это действительно необходимо для корректной работы поиска. «Пустая» ячейка всё-таки влияет на процесс, так как позволяет продолжить пробирование. Если бы при пробировании мы бы попали в удалённую ячейку, но её состояние не было бы помечено как «пустая», то поиск бы закончился, хотя на следующих шагах пробирования могла быть найдена искомая ячейка.

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

Процедура поиска ячейки для вставки элемента в словарь остановится только когда будет найдена «неиспользованная» ячейка.

[@boov]

«Пустая» ячейка всё-таки влияет на процесс, так как позволяет продолжить пробирование. Если бы при пробировании мы бы попали в удалённую ячейку, но её состояние не было бы помечено как «пустая», то поиск бы закончился, хотя на следующих шагах пробирования могла быть найдена искомая ячейка.

именно так, под «не влияет» я имел в виду не приводит к остановке пробирования.

Процедура поиска ячейки для вставки элемента в словарь остановится только когда будет найдена «неиспользованная» ячейка.

А чем в этом случае не подходит «пустая» ячейка? Почему только «неиспользованная»?

[@Delimitry]

В процедуре поиска выполняется проверка и если найденная ячейка окажется «пустая» она сохранится и начнётся или продолжится пробирование. Когда будет найдена «неиспользованная» ячейка, то сохранённая найденная «пустая» ячейка будет использована заново.
Получается фактически, что при добавлении нового элемента (отсутствующего в словаре) поиск остановится только когда будет найдена «неиспользованная» ячейка.

[@boov]

Понятно.
Т.о. однажды переведя (2/3)N — 1 ячеек словаря в состояние пустая, мы получим линейное время вставки до перестройки хэш-таблицы.

[@Delimitry]

Это могло бы быть верно, если бы «пустые» ячейки не использовались заново, но из-за того, что они используются заново, а в хэш-таблице точно будет найдена «неиспользованная» ячейка, этого не произойдёт.

[@boov]

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

[@Delimitry]

Есть один нюанс, связанный с тем, что после того как хэш-таблица будет заполнена на 2/3 произойдёт изменение её размера.

однажды переведя (2/3)N — 1 ячеек словаря в состояние пустая

После того как 2/3*N-1, то есть 5 элементов (для начального размера таблицы) будут добавлены и затем удалены, следующий добавляемый элемент определит что произойдёт: либо размер таблицы изменится, либо «пустая» ячейка, то есть одна из удалённых, будет использована заново. Перед добавлением элемента имеем ma_used = 0, ma_filled = 5.
В первом случае, после того как будет добавлен новый 6 элемент, будем иметь ma_used = 1, ma_filled = 6. Таблица заполнилась больше чем на 2/3, соответственно произойдёт изменение размера. Новый размер таблицы будет рассчитан так:

minused = ma_used * 4 = 1 * 4 = 4
newsize = PyDict_MINSIZE = 8
while newsize <= minused and newsize > 0:
    newsize = newsize * 2

Коэффициент увеличения размера равен 4, так как размер таблицы меньше 50000 элементов.
Получим newsize = 8, то есть размер таблицы не изменился. В функции изменения размера произойдёт полная перестройка хэш-таблицы с учётом нового размера – все «активные» ячейки будут перераспределены, а «пустые» и «неиспользованные» ячейки будут проигнорированы. Операция перестройки хэш-таблицы выполняется за линейное время.
Таким образом, после добавления 6 элемента, получим новую хэш-таблицу с единственной «активной» ячейкой, содержащей 6 элемент (ma_used = 1, ma_filled = 1).
Во втором случае одна из удалённых, будет использована заново и изменения размера не произойдёт, так как в хэш-таблице всё ещё 5 элементов (ma_used = 1, ma_filled = 5). Но если добавить новый 6 элемент, будем иметь ma_used = 2, ma_filled = 6. Таблица заполнилась больше чем на 2/3, произойдёт изменение размера. Новый размер таблицы рассчитывается следующим образом:

minused = ma_used * 4 = 2 * 4 = 8
newsize = PyDict_MINSIZE = 8
while newsize <= minused and newsize > 0:
    newsize = newsize * 2

Получим newsize = 16, то есть новый размер таблицы равен 16. После перераспределения получим новую хэш-таблицу с двумя «активными» ячейками, содержащими 5 и 6 элементы (ma_used = 2, ma_filled = 2).
Рассмотрим пример первого случая:

>>> d = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
>>> d.__sizeof__()
248
>>> for i in xrange(5): del d[i]
...
>>> d.__sizeof__()
248
>>> d[5] = 5
>>> d.__sizeof__()
248

Как видно из результатов, размер после добавления 6 элемента остался прежний.
Теперь рассмотрим пример второго случая:

>>> d = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
>>> d.__sizeof__()
248
>>> for i in xrange(5): del d[i]
...
>>> d.__sizeof__()
248
>>> d[4] = 4
>>> d[5] = 5
>>> d.__sizeof__()
632

Здесь видно, что размер хэш-таблицы изменился.

[@boov]

Огромное спасибо за детальное разъяснение!
В принципе вы все это описали в самой статье, но я при первом прочтении упустил ряд деталей, а дьявол кроется в мелочах :)

[@pesh1983]

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