Почему порядок в словарях и наборах произвольный?
Я не понимаю, как перебор словаря или набора в python выполняется в "произвольном" порядке.
Я имею в виду, что это язык программирования, поэтому все в языке должно быть определено на 100%, правильно? В Python должен быть какой-то алгоритм, который решает, какая часть словаря или набора выбрана, первая, вторая и так далее.
Чего я не понимаю?
Переведено автоматически
Ответ 1
Примечание: Этот ответ был написан до изменения типа реализации
dictв Python 3.6. Большинство деталей реализации в этом ответе по-прежнему применимы, но порядок перечисления ключей в словарях больше не определяется значениями хэша. Установленная реализация остается неизменной.
Порядок не является произвольным, но зависит от истории вставок и удалений словаря или набора, а также от конкретной реализации Python. В оставшейся части этого ответа вместо "dictionary" вы также можете прочитать "set"; наборы реализованы как словари только с ключами и без значений.
Ключи хэшируются, а хэш-значения присваиваются слотам в динамической таблице (она может увеличиваться или уменьшаться в зависимости от потребностей). И этот процесс сопоставления может привести к конфликтам, а это означает, что ключ придется поместить в следующий слот на основе того, что там уже есть.
Перечисление содержимого повторяется по слотам, и поэтому ключи перечислены в том порядке, в котором они в данный момент находятся в таблице.
Возьмем, к примеру, ключи 'foo' и 'bar' и предположим, что размер таблицы равен 8 слотам. В Python 2.7, hash('foo') является -4177197833195190597, hash('bar') является 327024216814240868. По модулю 8 это означает, что эти два ключа помещены в слоты 3 и 4, затем:
>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4
Это определяет порядок их перечисления:
>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}
Все слоты, кроме 3 и 4, пусты, при циклическом просмотре таблицы сначала отображается слот 3, затем слот 4, поэтому 'foo' указан перед 'bar'.
bar и baz, однако, имеют хэш-значения, которые разделены ровно на 8 и, таким образом, отображаются в один и тот же слот, 4:
>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4
Их порядок теперь зависит от того, какой ключ был вставлен первым; второй ключ нужно будет переместить в следующий слот:
>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}
Порядок таблиц здесь отличается, потому что тот или иной ключ был введен первым.
Техническое название базовой структуры, используемой CPython (наиболее часто используемая реализация Python), - это хэш-таблица, которая использует открытую адресацию. Если вам любопытно и вы достаточно хорошо понимаете C, взгляните на реализацию C, чтобы узнать все (хорошо документированные) детали. Вы также можете посмотреть эту презентацию на Pycon 2010 от Брэндона Роудса о том, как работает CPython dict, или взять копию Красивого кода, который включает главу о реализации, написанную Эндрю Кухлингом.
Обратите внимание, что начиная с Python 3.3, также используется случайный начальный хэш, что делает хэш-коллизии непредсказуемыми для предотвращения определенных типов отказа в обслуживании (когда злоумышленник делает сервер Python невосприимчивым, вызывая массовые хэш-коллизии). Это означает, что порядок данного словаря или набора также зависит от случайного начального значения хэша для текущего вызова Python.
Другие реализации могут свободно использовать другую структуру для словарей, при условии, что они удовлетворяют документированному интерфейсу Python для них, но я считаю, что все реализации до сих пор используют вариацию хэш-таблицы.
CPython 3.6 представляет новую dict реализацию, которая поддерживает порядок вставки и обеспечивает более быструю загрузку и большую экономию памяти. Вместо сохранения большой разреженной таблицы, где каждая строка ссылается на сохраненное хэш-значение и объекты key и value, новая реализация добавляет меньший по размеру хэш-массив, который ссылается только на индексы в отдельной "плотной" таблице (той, которая содержит столько строк, сколько существует фактических пар ключ-значение), и именно в плотной таблице происходит перечисление содержащихся элементов по порядку. Смотрите предложение Python-Dev для получения более подробной информации. Обратите внимание, что в Python 3.6 это считается деталью реализации, язык Python не указывает, что другие реализации должны сохранять порядок. Это изменилось в Python 3.7, где эта деталь была повышена до языковой спецификации; чтобы любая реализация была должным образом совместима с Python 3.7 или новее, она должна копировать это поведение с сохранением порядка. И, чтобы быть точным: это изменение не распространяется на наборы, поскольку наборы уже имеют "небольшую" хэш-структуру.
Python 2.7 и новее также предоставляет OrderedDict класс, подкласс dict, который добавляет дополнительную структуру данных для записи порядка ключей. Ценой некоторой скорости и дополнительной памяти этот класс запоминает, в каком порядке вы вставили ключи; затем в этом порядке будет выполняться перечисление ключей, значений или элементов. Он использует двусвязный список, хранящийся в дополнительном словаре, чтобы эффективно поддерживать порядок в актуальном состоянии. Смотрите Пост Раймонда Хеттингера, в котором излагается идея. OrderedDict объекты обладают другими преимуществами, такими как возможность переупорядочивания.
Если вам нужен упорядоченный набор, вы можете установить oset пакет; он работает на Python 2.5 и выше.
Ответ 2
Это скорее ответ на Python 3.41 A set до того, как он был закрыт как дубликат.
Остальные правы: не полагайтесь на порядок. Даже не притворяйтесь, что он есть.
Тем не менее, есть одна вещь, на которую вы можете положиться:
list(myset) == list(myset)
То есть порядок стабильный.
Понимание того, почему существует воспринимаемый порядок, требует понимания нескольких вещей:
Что Python использует хэш-наборы,
Как хэш-набор CPython хранится в памяти и
Как хэшируются числа
Сверху:
Хэш-набор - это метод хранения случайных данных с действительно быстрым временем поиска.
У него есть резервный массив:
# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6
Мы проигнорируем специальный фиктивный объект, который существует только для того, чтобы упростить обработку удалений, потому что мы не будем удалять из этих наборов.
Чтобы обеспечить действительно быстрый поиск, вы совершаете некоторую магию для вычисления хэша из объекта. Единственное правило заключается в том, что два одинаковых объекта имеют одинаковый хэш. (Но если два объекта имеют одинаковый хэш, они могут быть неравными.)
Затем вы создаете индекс, принимая модуль за длину массива:
hash(4) % len(storage) = index 2
Это действительно ускоряет доступ к элементам.
Хэши - это только большая часть истории, поскольку hash(n) % len(storage) и hash(m) % len(storage) может привести к одному и тому же числу. В этом случае конфликт можно попытаться разрешить несколькими разными стратегиями. CPython использует "линейное зондирование" 9 раз перед выполнением псевдослучайного зондирования, поэтому он будет искать справа от слота до 9 мест, прежде чем искать в другом месте.
Хэш-наборы CPython хранятся следующим образом:
Хэш-набор может быть заполнен не более чем на 60% (примечание: этот коэффициент загрузки составлял ранее 66%, он был уменьшен в Python 3.7). Если имеется 20 элементов, а резервный массив имеет длину 30 элементов, размер резервного хранилища будет увеличен. Это потому, что вы чаще сталкиваетесь с небольшими резервными хранилищами, а столкновения замедляют работу.
Когда резервное хранилище становится слишком полным, его размер автоматически изменяется, чтобы увеличить долю неиспользуемого пространства (более высокое соотношение неиспользуемого пространства означает, что быстрее найти слот при обработке коллизии хэшей). Для небольших наборов объем хранилища будет увеличен в четыре раза, а для больших наборов (> 50 000) - в два раза (исходный код).
Итак, когда вы создаете массив, резервная память имеет длину 8. Как только он заполнится на 4 и вы добавите элемент, он будет содержать 5 элементов. 5 > ³⁄₅·8 таким образом, это вызывает изменение размера, и хранилище резервных копий увеличивается в четыре раза до размера 32.
>>> import sys
>>> s = set()
>>> for i in range(10):
... print(len(s), sys.getsizeof(s))
... s.add(i)
...
0 216
1 216
2 216
3 216
4 216
5 728
6 728
7 728
8 728
9 728
Наконец, hash(n) просто возвращает n для целых чисел (за исключением hash(-1) который возвращает -2, потому что значение -1 зарезервировано для другого использования).
Итак, давайте рассмотрим первый вариант:
v_set = {88,11,1,33,21,3,7,55,37,8}
len(v_set) равно 10, значит, запасное хранилище составляет не менее 15 (+ 1) после добавления всех элементов. Соответствующая степень 2 равна 32. Таким образом, запасное хранилище равно:
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
У нас есть
hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1) % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3) % 32 = 3
hash(7) % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8) % 32 = 8
итак, они вставляются как:
__ 1 __ 3 __ 37 __ 7 8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
33 ← Can't also be where 1 is;
either 1 or 33 has to move
Итак, мы ожидали бы порядка, подобного
{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}
с 1 или 33, которых нет в начале где-то еще. При этом будет использоваться линейное зондирование, поэтому у нас будет либо:
↓
__ 1 33 3 __ 37 __ 7 8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
или
↓
__ 33 1 3 __ 37 __ 7 8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
Вы могли бы ожидать, что 33 будет смещено, потому что 1 уже был там, но из-за изменения размера, которое происходит по мере сборки набора, на самом деле это не так. Каждый раз, когда набор перестраивается, уже добавленные элементы эффективно переупорядочиваются.
Теперь вы можете видеть, почему
{7,5,11,1,4,13,55,12,2,3,6,20,9,10}
может быть по порядку. Всего 14 элементов, поэтому резервная память составляет не менее 21 + 1, что означает 32:
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
хэш от 1 до 13 в первых 13 слотах. 20 помещается в слот 20.
__ 1 2 3 4 5 6 7 8 9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __
55 идет в слот, hash(55) % 32 который равен 23:
__ 1 2 3 4 5 6 7 8 9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __
Если бы мы выбрали 50 вместо этого, мы бы ожидали
__ 1 2 3 4 5 6 7 8 9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __
И о чудо:
>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}
pop на первый взгляд реализован довольно просто: он обходит базовый массив и извлекает первый элемент, пропуская неиспользуемые слоты и "фиктивные" записи (маркеры надгробий из удаленных элементов).
Это все детали реализации.
Ответ 3
"Произвольный" - это не то же самое, что "неопределенный".
Они говорят, что нет полезных свойств порядка итерации словаря, которые есть "в общедоступном интерфейсе". Почти наверняка существует множество свойств порядка итераций, которые полностью определяются кодом, который в настоящее время реализует итерацию по словарю, но авторы не обещают их вам как нечто, что вы можете использовать. Это дает им больше свободы изменять эти свойства между версиями Python (или даже просто в разных условиях работы, или совершенно случайным образом во время выполнения), не беспокоясь о том, что ваша программа сломается.
Таким образом, если вы пишете программу, которая зависит от вообще какого-либо свойства словарного порядка, то вы "нарушаете контракт" на использование словарного типа, и разработчики Python не обещают, что это будет работать всегда, даже если сейчас, когда вы тестируете, кажется, что это работает. По сути, это эквивалентно тому, чтобы полагаться на "неопределенное поведение" в C.
Ответ 4
Другие ответы на этот вопрос отличные и хорошо написаны. OP спрашивает "как", что я интерпретирую как "как им это сходит с рук" или "почему".
В документации Python говорится, что словари не упорядочены, потому что словарь Python реализует абстрактный тип данных ассоциативный массив. Как говорится
порядок, в котором возвращаются привязки, может быть произвольным
Другими словами, студент, изучающий информатику, не может предположить, что ассоциативный массив упорядочен. То же самое верно для наборов в математике
порядок, в котором перечислены элементы набора, не имеет значения
set - это абстрактный тип данных, который может хранить определенные значения без какого-либо определенного порядка
Реализация словаря с использованием хэш-таблицы - это деталь реализации, интересная тем, что она обладает теми же свойствами, что и ассоциативные массивы, в том, что касается порядка.