Почему порядок в словарях и множествах произвольный?
Я не понимаю, как зацикливание словаря или набора в python осуществляется в произвольном порядке.
Я имею в виду, что это язык программирования, поэтому все в языке должно быть определено на 100%, верно? У Python должен быть какой-то алгоритм, который решает, какая часть словаря или набора выбрана, 1-я, вторая и так далее.
Что мне не хватает?
6 ответов
Порядок не является произвольным, но зависит от истории вставки и удаления словаря или набора, а также от конкретной реализации Python. В оставшейся части этого ответа, для словаря, вы также можете прочитать "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 работает, или возьмите копию Beautiful Code, которая включает в себя главу о реализации, написанную Эндрю Кучлингом.
Обратите внимание, что в Python 3.3 также используется случайное начальное число хешей, что делает коллизии хеша непредсказуемыми, чтобы предотвратить определенные типы отказа в обслуживании (когда злоумышленник делает сервер Python без ответа, вызывая массовые коллизии хеша). Это означает, что порядок данного словаря также зависит от случайного начального числа хэша для текущего вызова Python.
Другие реализации могут свободно использовать другую структуру для словарей, если они удовлетворяют документированному интерфейсу Python для них, но я считаю, что все реализации до сих пор используют разновидность хеш-таблицы.
CPython 3.6 представляет новый dict реализация, которая поддерживает порядок вставки, а также быстрее и более эффективно использует память для загрузки. Вместо того чтобы хранить большую разреженную таблицу, в которой каждая строка ссылается на сохраненное хеш-значение, а также на объекты ключа и значения, новая реализация добавляет меньший хеш- массив, который ссылается только на индексы в плотной таблице (та, которая содержит столько строк, сколько существует фактических пары ключ-значение), и это плотная таблица, в которой перечисляются содержащиеся элементы по порядку. Смотрите предложение к Python-Dev для более подробной информации. Обратите внимание, что в Python 3.6 это считается деталью реализации, Python-the-language не указывает, что другие реализации должны сохранять порядок. Это изменилось в Python 3.7, где эта деталь была повышена до языковой спецификации; для того чтобы любая реализация была должным образом совместима с Python 3.7 или новее, она должна скопировать это поведение, сохраняющее порядок.
Python 2.7 и новее также предоставляет OrderedDict класс, подкласс dict это добавляет дополнительную структуру данных для записи порядка ключей. Ценой некоторой скорости и дополнительной памяти этот класс запоминает, в каком порядке вы вставляли ключи; перечисление ключей, значений или элементов будет происходить в таком порядке. Он использует двусвязный список, хранящийся в дополнительном словаре, чтобы эффективно поддерживать порядок в актуальном состоянии. Посмотрите пост Раймонда Хеттингера с изложением этой идеи. Обратите внимание, что set Тип по-прежнему неупорядочен.
Если вы хотели заказать комплект, вы можете установить oset упаковка; это работает на Python 2.5 и выше.
Это скорее ответ на Python 3.41 Набор до того, как он был закрыт как дубликат.
Другие правы: не полагайтесь на порядок. Даже не притворяйся, что есть.
Тем не менее, есть одна вещь, на которую вы можете положиться:
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 хранятся так:
Набор хешей может быть не более 2/3. Если имеется 20 элементов, а резервный массив имеет длину 30 элементов, резервное хранилище изменится, чтобы быть больше. Это потому, что вы часто сталкиваетесь с небольшими запасными магазинами, а столкновения замедляют все.
Резервное хранилище изменяет размеры в степени 4, начиная с 8, за исключением больших наборов (50 тыс. Элементов), размер которых изменяется в степени двух: (8, 32, 128, ...).
Поэтому, когда вы создаете массив, резервное хранилище имеет длину 8. Когда оно заполнено на 5 единиц, и вы добавляете элемент, он кратко будет содержать 6 элементов. 6 > ²⁄₃·8 так что это вызывает изменение размера, и резервное хранилище увеличивается в четыре раза до размера 32.
В заключение, hash(n) просто возвращается n для номеров (кроме -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 реализован довольно просто по внешнему виду: он пересекает список и выдает первый.
Это все детали реализации.
"Произвольный" - это не то же самое, что "неопределенный".
Они говорят, что нет никаких полезных свойств порядка итераций словаря, которые находятся "в открытом интерфейсе". Почти наверняка есть много свойств порядка итерации, которые полностью определяются кодом, который в настоящее время реализует итерацию словаря, но авторы не обещают их вам как то, что вы можете использовать. Это дает им больше свободы изменять эти свойства между версиями Python (или даже просто в разных условиях работы, или совершенно случайно на этапе выполнения), не беспокоясь о том, что ваша программа сломается.
Таким образом, если вы пишете программу, которая зависит от какого-либо свойства во всех словарных порядках, то вы "нарушаете договор" использования типа словаря, и разработчики Python не обещают, что это всегда будет работать, даже если кажется, что оно работает сейчас, когда вы проверяете это. Это в основном эквивалент доверия "неопределенному поведению" в C.
Другие ответы на этот вопрос превосходны и хорошо написаны. ФП спрашивает "как", что я интерпретирую как "как им сойти с рук" или "почему".
Документация Python говорит, что словари не упорядочены, потому что словарь Python реализует ассоциативный массив абстрактных типов данных. Так как они сказали
порядок, в котором возвращаются привязки, может быть произвольным
Другими словами, студент по информатике не может предположить, что ассоциативный массив упорядочен. То же самое верно для наборов в математике
порядок, в котором перечислены элементы набора, не имеет значения
набор - это абстрактный тип данных, который может хранить определенные значения без какого-либо определенного порядка
Реализация словаря с использованием хеш-таблицы - это интересная деталь реализации, которая имеет те же свойства, что и ассоциативные массивы, что касается порядка.
Python использует хеш-таблицу для хранения словарей, поэтому порядок в словарях или других итерируемых объектах, использующих хеш-таблицу, отсутствует.
Но что касается индексов элементов в хеш-объекте, Python вычисляет индексы на основе следующего кода в hashtable.c:
key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);
Таким образом, поскольку хеш-значение целых является самим целым числом * индекс основан на числе (ht->num_buckets - 1 является константой), поэтому индекс рассчитывается по битам и между (ht->num_buckets - 1) и само число * (ожидайте для -1, хэш которого равен -2), а для других объектов с их хеш-значением.
рассмотрим следующий пример с set которые используют хэш-таблицу:
>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])
Для номера 33 у нас есть:
33 & (ht->num_buckets - 1) = 1
Это на самом деле это:
'0b100001' & '0b111'= '0b1' # 1 the index of 33
Обратите внимание, в этом случае (ht->num_buckets - 1) является 8-1=7 или же 0b111,
И для 1919:
'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919
И для 333:
'0b101001101' & '0b111' = '0b101' # 5 the index of 333
Для более подробной информации о хэш-функции Python полезно прочитать следующие цитаты из исходного кода Python:
Основные тонкости впереди: большинство хеш-схем зависят от наличия "хорошей" хеш-функции в смысле симуляции случайности. Python не делает: его наиболее важные хеш-функции (для строк и целых чисел) очень обычны в обычных случаях:
>>> map(hash, (0, 1, 2, 3)) [0, 1, 2, 3] >>> map(hash, ("namea", "nameb", "namec", "named")) [-1658398457, -1658398460, -1658398459, -1658398462]Это не обязательно плохо! Наоборот, в таблице размером 2**i, бита младшего разряда i в качестве начального индекса таблицы чрезвычайно быстра, и нет никаких коллизий для кодов, индексируемых непрерывным диапазоном целых чисел. То же самое примерно верно, когда ключи являются "последовательными" строками. Так что это дает поведение лучше случайного в обычных случаях, и это очень желательно.
OTOH, когда происходят коллизии, тенденция заполнять непрерывные фрагменты хеш-таблицы делает хорошую стратегию разрешения коллизий решающей. Получение только последних i-х бит хеш-кода также уязвимо: например, рассмотрим список
[i << 16 for i in range(20000)]как набор ключей. Поскольку целые числа являются их собственными хеш-кодами, и это соответствует размеру 2**15, последние 15 бит каждого хеш-кода равны 0: все они соответствуют одному и тому же индексу таблицы.Но угощение необычными случаями не должно замедлять обычные, так что в любом случае мы просто берем последние биты. Остальное зависит от разрешения столкновений. Если мы обычно находим ключ, который ищем, с первой попытки (и, как выясняется, мы обычно это делаем - коэффициент загрузки таблицы держится на уровне 2/3, поэтому шансы остаются в нашу пользу), тогда он имеет смысл сохранить начальные вычисления индекса дешевыми.
* Хеш-функция для класса int :
class int:
def __hash__(self):
value = self
if value == -1:
value = -2
return value
Начиная с Python 3.7 (и уже в CPython 3.6), элементы словаря остаются в том порядке, в котором они были вставлены.