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
Подробный и наглядный обзор часто применяемой структуры.
Что еще планируете разобрать?
Что еще планируете разобрать?
Вот вам задачка на знание, как работает dict в Python'е:
Что выпишет этот код и почему?
print sum({
1: 1,
2: 2,
1.0: 3,
}.values())Что выпишет этот код и почему?
Выведет 5
Потому что hash(1)==hash(1.0), что даст один индекс, заменив значение 1 на 3, вместо добавления 3, оставив в результате 2 и 3, которые попадут в sum?
Знак вопроса в конце — это не опечатка.
Потому что hash(1)==hash(1.0), что даст один индекс, заменив значение 1 на 3, вместо добавления 3, оставив в результате 2 и 3, которые попадут в sum?
Знак вопроса в конце — это не опечатка.
В статье этот момент рассмотрен.
5, хеш 1 и 1.0 одинаковый, элементы добавляются последовательно, 1.0 добавляется позже и он перезапишет 1 на 3.
странно, что все пишут про одинаковый хеш
думаю здесь более значимо то, что 1 == 1.0(True)
разные строки с одинаковым хешем хранились бы обе, так как они не эквивалентны
думаю здесь более значимо то, что 1 == 1.0(True)
разные строки с одинаковым хешем хранились бы обе, так как они не эквивалентны
Совершенно верно. Если хэши значений оказались одинаковыми, сравниваются сами значения. А так как 1 == 1.0, считается что элемент уже есть в словаре и его значение обновляется.
Не претендую на правильность версии, но вы случаем не путаете причину и следствие? Может это 1==1.0 потому что hash(1)==hash(1.0)?
Нет, не путаю. Ведь если бы значения считались равны в случае равенства их хэшей, то два разных значения с одинаковыми хэшами (то есть в случае коллизии) были бы равны, а это неправильно.
В данном случае для сравнения 1 и 1.0 (типы разные — int и float), в соответствии с методом
В данном случае для сравнения 1 и 1.0 (типы разные — int и float), в соответствии с методом
float_richcompare (так как у объекта int не реализован метод tp_richcompare), значения 1 и 1.0 будут приведены к double и сравнены.Спасибо за пост, надеюсь продолжите про структуры данных и поднаготную питона!
Что-то я не очень понял, как такое может быть в пункте 2):
А как же тут же рассматриваемые примеры, в которых сплошь и рядом значение
Это единственное состояние, когда me_value != NULL.
А как же тут же рассматриваемые примеры, в которых сплошь и рядом значение
me_value не пустое?
Спасибо за подробный разбор внутренностей словаря в Python. В очередной раз убеждаюсь, что Python писали инженеры: принимаемые решения обоснованы, перед выбором из нескольких альтернатив всегда проводится тестирование производительности, есть простые правила работы, которые объясняют поведение словаря в любой ситуации. Разработчики даже реализовали свой гибридный алгоритм сортировки Timsort.
Насчет устройства словаря в Python очень было приятно послушать доклад с одного из Python Meetup. Может, кому-нибудь пригодится.
Двойные стандарты. При хешировании они целые числа никак не перемешивают, и «подряд идущие» строки тоже (кстати, как такое возможно? какая хеш-функция у строки?) типа коллизии на «специально подобранных» случаях их не волнуют, зато потом очень заморачиваются с последовательностью проб, потому что коллизии их, внезапно, заволновали.
Не нравится полная нелокальность последовательности проб.
Нету объяснения, зачем на относительно маленьких таблицах увеличение в 4 раза. Они добиваются тем самым очень маленького среднего коэфф. заполнения, коллизии практически не возникают, и эффект нелокальности последовательности проб не бросается в глаза. Зато потом все жалуются, что Питон жрет много памяти.
По моему опыту, ничего лучше самого простейшего линейного хеширования все равно нет.
Не нравится полная нелокальность последовательности проб.
Нету объяснения, зачем на относительно маленьких таблицах увеличение в 4 раза. Они добиваются тем самым очень маленького среднего коэфф. заполнения, коллизии практически не возникают, и эффект нелокальности последовательности проб не бросается в глаза. Зато потом все жалуются, что Питон жрет много памяти.
По моему опыту, ничего лучше самого простейшего линейного хеширования все равно нет.
Если кому интересна тема, то вот в этой полезной книге есть целая глава, посвящённая устройству словарей в Python. «Глава 18. Реализация словарей Python: стремление быть всем во всём полезным.» (стр. 331 на google books)
Возможно следует добавить, что начиная с версии 4.4 в качестве hash-функции по умолчанию (для платформ с поддержкой 64 битных чисел) используется SipHash. Она же используется в Ruby, Rust, Perl и Haskel. Вероятно где-то еще.
UFO just landed and posted this here
Спасибо за статью!
По ходу прочтения возник такой вопрос.
Правильно ли я понял, что сложность поиска элемента, который заведомо отсутствует в словаре (никогда не добавлялся или был удален), всегда будет линейна от размера таблицы?
По ходу прочтения возник такой вопрос.
Правильно ли я понял, что сложность поиска элемента, который заведомо отсутствует в словаре (никогда не добавлялся или был удален), всегда будет линейна от размера таблицы?
В общем случае сложность поиска, добавления и удаления выполняется за константное время. Сложность поиска и добавления будет линейна от размера таблицы только в худшем случае (когда при пробировании будут последовательно происходить коллизии). Например если добавлять элементы, хэши ключей которых будут одинаковые, но сами ключи при этом разные.
Спасибо.
Я похоже разобрался, поправьте, если не так.
При разрешении коллизий методом открытой адресации (в отличие от цепочек, где все элементы с одним хэшем расположены в связанном списке) пришлось ввести понятия неиспользованной и пустой ячеек.
Это необходимо для корректной остановки процедуры поиска элемента — останавливаться только, когда элемент найден или попалась неиспользованная ячейка в процессе пробирования (пустая ячейка никак не влияет на процесс)…
В то же время процедура вставки элемента в словарь должна останавливаться, когда найдется либо неиспользованная либо пустая ячейка.
Я похоже разобрался, поправьте, если не так.
При разрешении коллизий методом открытой адресации (в отличие от цепочек, где все элементы с одним хэшем расположены в связанном списке) пришлось ввести понятия неиспользованной и пустой ячеек.
Это необходимо для корректной остановки процедуры поиска элемента — останавливаться только, когда элемент найден или попалась неиспользованная ячейка в процессе пробирования (пустая ячейка никак не влияет на процесс)…
В то же время процедура вставки элемента в словарь должна останавливаться, когда найдется либо неиспользованная либо пустая ячейка.
пришлось ввести понятия неиспользованной и пустой ячеек.Насколько я понимаю, использование флага для определения удалён ли элемент в ячейке или нет, это общепринятая практика в методе открытой адресации. В данном случае флагом служит состояние ячейки.
Это необходимо для корректной остановки процедуры поиска элемента — останавливаться только, когда элемент найден или попалась неиспользованная ячейка в процессе пробирования (пустая ячейка никак не влияет на процесс)…Это действительно необходимо для корректной работы поиска. «Пустая» ячейка всё-таки влияет на процесс, так как позволяет продолжить пробирование. Если бы при пробировании мы бы попали в удалённую ячейку, но её состояние не было бы помечено как «пустая», то поиск бы закончился, хотя на следующих шагах пробирования могла быть найдена искомая ячейка.
В то же время процедура вставки элемента в словарь должна останавливаться, когда найдется либо неиспользованная либо пустая ячейка.Процедура поиска ячейки для вставки элемента в словарь остановится только когда будет найдена «неиспользованная» ячейка.
«Пустая» ячейка всё-таки влияет на процесс, так как позволяет продолжить пробирование. Если бы при пробировании мы бы попали в удалённую ячейку, но её состояние не было бы помечено как «пустая», то поиск бы закончился, хотя на следующих шагах пробирования могла быть найдена искомая ячейка.
именно так, под «не влияет» я имел в виду не приводит к остановке пробирования.
Процедура поиска ячейки для вставки элемента в словарь остановится только когда будет найдена «неиспользованная» ячейка.
А чем в этом случае не подходит «пустая» ячейка? Почему только «неиспользованная»?
В процедуре поиска выполняется проверка и если найденная ячейка окажется «пустая» она сохранится и начнётся или продолжится пробирование. Когда будет найдена «неиспользованная» ячейка, то сохранённая найденная «пустая» ячейка будет использована заново.
Получается фактически, что при добавлении нового элемента (отсутствующего в словаре) поиск остановится только когда будет найдена «неиспользованная» ячейка.
Получается фактически, что при добавлении нового элемента (отсутствующего в словаре) поиск остановится только когда будет найдена «неиспользованная» ячейка.
Понятно.
Т.о. однажды переведя (2/3)N — 1 ячеек словаря в состояние пустая, мы получим линейное время вставки до перестройки хэш-таблицы.
Т.о. однажды переведя (2/3)N — 1 ячеек словаря в состояние пустая, мы получим линейное время вставки до перестройки хэш-таблицы.
Это могло бы быть верно, если бы «пустые» ячейки не использовались заново, но из-за того, что они используются заново, а в хэш-таблице точно будет найдена «неиспользованная» ячейка, этого не произойдёт.
а каким образом пустые ячейки здесь помогут? Здесь скорее все будет зависеть от алгоритма пробирования и от конкоетных данных. В любом случае повторное заполнение словаря теми же данными в том же порядке должно выполняться дольше.
Есть один нюанс, связанный с тем, что после того как хэш-таблица будет заполнена на 2/3 произойдёт изменение её размера.
В первом случае, после того как будет добавлен новый 6 элемент, будем иметь ma_used = 1, ma_filled = 6. Таблица заполнилась больше чем на 2/3, соответственно произойдёт изменение размера. Новый размер таблицы будет рассчитан так:
Получим 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, произойдёт изменение размера. Новый размер таблицы рассчитывается следующим образом:
Рассмотрим пример первого случая:
Теперь рассмотрим пример второго случая:
однажды переведя (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
Получим 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
Рассмотрим пример первого случая:
>>> 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
Теперь рассмотрим пример второго случая:
>>> 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
Подскажите источник, где можно получить такое же развернутое описание других структур данных, например, списка, множества, кортежа и т. д. Статья очень понравилась и разрешила многие вопросы, спасибо)
Sign up to leave a comment.
Реализация словаря в Python 2.7