How to become an author
Search
Write a publication
Pull to refresh

Comments 37

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

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
Total votes 2: ↑1 and ↓10
Так элемент только помечается, как удаленный. Нужна еще физическая чистка словаря, фактически перезагрузка.
Total votes 1: ↑1 and ↓0+1
Занятно то, что чтобы она произошла, нужно добавить в словарь больше элементов, чем в нем было. Иначе никак.
Total votes 2: ↑1 and ↓10
Подробный и наглядный обзор часто применяемой структуры.
Что еще планируете разобрать?
Total votes 4: ↑4 and ↓0+4
Спасибо. Теперь планирую разобраться как устроен словарь в Python 3. Судя по исходникам он претерпел кое-какие изменения.
Total votes 3: ↑3 and ↓0+3
Вот вам задачка на знание, как работает dict в Python'е:

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

Что выпишет этот код и почему?
This comment wasn’t rated yet0
Выведет 5

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

Знак вопроса в конце — это не опечатка.
Total votes 2: ↑1 and ↓10
В статье этот момент рассмотрен.
Total votes 3: ↑3 and ↓0+3
5, хеш 1 и 1.0 одинаковый, элементы добавляются последовательно, 1.0 добавляется позже и он перезапишет 1 на 3.
Total votes 1: ↑0 and ↓1-1
странно, что все пишут про одинаковый хеш
думаю здесь более значимо то, что 1 == 1.0(True)

разные строки с одинаковым хешем хранились бы обе, так как они не эквивалентны
Total votes 8: ↑8 and ↓0+8
Совершенно верно. Если хэши значений оказались одинаковыми, сравниваются сами значения. А так как 1 == 1.0, считается что элемент уже есть в словаре и его значение обновляется.
Total votes 2: ↑1 and ↓10
Не претендую на правильность версии, но вы случаем не путаете причину и следствие? Может это 1==1.0 потому что hash(1)==hash(1.0)?
This comment wasn’t rated yet0
Нет, не путаю. Ведь если бы значения считались равны в случае равенства их хэшей, то два разных значения с одинаковыми хэшами (то есть в случае коллизии) были бы равны, а это неправильно.
В данном случае для сравнения 1 и 1.0 (типы разные — int и float), в соответствии с методом float_richcompare (так как у объекта int не реализован метод tp_richcompare), значения 1 и 1.0 будут приведены к double и сравнены.
Total votes 4: ↑4 and ↓0+4
Спасибо за пост, надеюсь продолжите про структуры данных и поднаготную питона!
Total votes 1: ↑1 and ↓0+1
Что-то я не очень понял, как такое может быть в пункте 2):
Это единственное состояние, когда me_value != NULL.

А как же тут же рассматриваемые примеры, в которых сплошь и рядом значение me_value не пустое?
This comment wasn’t rated yet0
При добавлении элемента в ячейку, me_value становится != NULL, то есть она переходит в состояние «активная». Это единственное состояние (имеется ввиду единственное из трёх возможных), когда me_value != NULL. В примерах, в основном, происходит как раз добавление элементов.
This comment wasn’t rated yet0
Спасибо за подробный разбор внутренностей словаря в Python. В очередной раз убеждаюсь, что Python писали инженеры: принимаемые решения обоснованы, перед выбором из нескольких альтернатив всегда проводится тестирование производительности, есть простые правила работы, которые объясняют поведение словаря в любой ситуации. Разработчики даже реализовали свой гибридный алгоритм сортировки Timsort.
Total votes 2: ↑2 and ↓0+2
Насчет устройства словаря в Python очень было приятно послушать доклад с одного из Python Meetup. Может, кому-нибудь пригодится.
Total votes 1: ↑1 and ↓0+1
Да хороший доклад. Эта ссылка уже есть в статье.
This comment wasn’t rated yet0
Двойные стандарты. При хешировании они целые числа никак не перемешивают, и «подряд идущие» строки тоже (кстати, как такое возможно? какая хеш-функция у строки?) типа коллизии на «специально подобранных» случаях их не волнуют, зато потом очень заморачиваются с последовательностью проб, потому что коллизии их, внезапно, заволновали.

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

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

По моему опыту, ничего лучше самого простейшего линейного хеширования все равно нет.
Total votes 1: ↑1 and ↓0+1
Если кому интересна тема, то вот в этой полезной книге есть целая глава, посвящённая устройству словарей в Python. «Глава 18. Реализация словарей Python: стремление быть всем во всём полезным.» (стр. 331 на google books)
Total votes 1: ↑1 and ↓0+1
Возможно следует добавить, что начиная с версии 4.4 в качестве hash-функции по умолчанию (для платформ с поддержкой 64 битных чисел) используется SipHash. Она же используется в Ruby, Rust, Perl и Haskel. Вероятно где-то еще.
This comment wasn’t rated yet0
UFO just landed and posted this here
Спасибо за статью!

По ходу прочтения возник такой вопрос.
Правильно ли я понял, что сложность поиска элемента, который заведомо отсутствует в словаре (никогда не добавлялся или был удален), всегда будет линейна от размера таблицы?
Total votes 1: ↑1 and ↓0+1
В общем случае сложность поиска, добавления и удаления выполняется за константное время. Сложность поиска и добавления будет линейна от размера таблицы только в худшем случае (когда при пробировании будут последовательно происходить коллизии). Например если добавлять элементы, хэши ключей которых будут одинаковые, но сами ключи при этом разные.
This comment wasn’t rated yet0
Спасибо.
Я похоже разобрался, поправьте, если не так.
При разрешении коллизий методом открытой адресации (в отличие от цепочек, где все элементы с одним хэшем расположены в связанном списке) пришлось ввести понятия неиспользованной и пустой ячеек.
Это необходимо для корректной остановки процедуры поиска элемента — останавливаться только, когда элемент найден или попалась неиспользованная ячейка в процессе пробирования (пустая ячейка никак не влияет на процесс)…
В то же время процедура вставки элемента в словарь должна останавливаться, когда найдется либо неиспользованная либо пустая ячейка.
Total votes 1: ↑1 and ↓0+1
пришлось ввести понятия неиспользованной и пустой ячеек.
Насколько я понимаю, использование флага для определения удалён ли элемент в ячейке или нет, это общепринятая практика в методе открытой адресации. В данном случае флагом служит состояние ячейки.
Это необходимо для корректной остановки процедуры поиска элемента — останавливаться только, когда элемент найден или попалась неиспользованная ячейка в процессе пробирования (пустая ячейка никак не влияет на процесс)…
Это действительно необходимо для корректной работы поиска. «Пустая» ячейка всё-таки влияет на процесс, так как позволяет продолжить пробирование. Если бы при пробировании мы бы попали в удалённую ячейку, но её состояние не было бы помечено как «пустая», то поиск бы закончился, хотя на следующих шагах пробирования могла быть найдена искомая ячейка.
В то же время процедура вставки элемента в словарь должна останавливаться, когда найдется либо неиспользованная либо пустая ячейка.
Процедура поиска ячейки для вставки элемента в словарь остановится только когда будет найдена «неиспользованная» ячейка.
Total votes 2: ↑2 and ↓0+2
«Пустая» ячейка всё-таки влияет на процесс, так как позволяет продолжить пробирование. Если бы при пробировании мы бы попали в удалённую ячейку, но её состояние не было бы помечено как «пустая», то поиск бы закончился, хотя на следующих шагах пробирования могла быть найдена искомая ячейка.

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

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

А чем в этом случае не подходит «пустая» ячейка? Почему только «неиспользованная»?
This comment wasn’t rated yet0
В процедуре поиска выполняется проверка и если найденная ячейка окажется «пустая» она сохранится и начнётся или продолжится пробирование. Когда будет найдена «неиспользованная» ячейка, то сохранённая найденная «пустая» ячейка будет использована заново.
Получается фактически, что при добавлении нового элемента (отсутствующего в словаре) поиск остановится только когда будет найдена «неиспользованная» ячейка.
Total votes 1: ↑1 and ↓0+1
Понятно.
Т.о. однажды переведя (2/3)N — 1 ячеек словаря в состояние пустая, мы получим линейное время вставки до перестройки хэш-таблицы.
Total votes 1: ↑1 and ↓0+1
Это могло бы быть верно, если бы «пустые» ячейки не использовались заново, но из-за того, что они используются заново, а в хэш-таблице точно будет найдена «неиспользованная» ячейка, этого не произойдёт.
This comment wasn’t rated yet0
а каким образом пустые ячейки здесь помогут? Здесь скорее все будет зависеть от алгоритма пробирования и от конкоетных данных. В любом случае повторное заполнение словаря теми же данными в том же порядке должно выполняться дольше.
This comment wasn’t rated yet0
Есть один нюанс, связанный с тем, что после того как хэш-таблица будет заполнена на 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
Здесь видно, что размер хэш-таблицы изменился.
Total votes 1: ↑1 and ↓0+1
Огромное спасибо за детальное разъяснение!
В принципе вы все это описали в самой статье, но я при первом прочтении упустил ряд деталей, а дьявол кроется в мелочах :)
Total votes 1: ↑1 and ↓0+1
Подскажите источник, где можно получить такое же развернутое описание других структур данных, например, списка, множества, кортежа и т. д. Статья очень понравилась и разрешила многие вопросы, спасибо)
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time
Change theme settings

Your account

Sections

Information

Services

Support
© 2006–2024, Habr