"порядок" неупорядоченных наборов Python

Ответ 1

Вы должны посмотреть это видео (хотя это специфичный для CPython ¹ и около словарей), но я предполагаю, что это относится и к наборам).

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

Также обратите внимание, что порядок их распечатки определяется порядком их размещения (из-за столкновений). Итак, если вы переупорядочиваете список, который вы переходите на set_2, вы можете получить другой порядок, если есть ключевые коллизии.

Например:

list1 = [8,16,24]
set(list1)        #set([8, 16, 24])
list2 = [24,16,8]
set(list2)        #set([24, 16, 8])

Обратите внимание на то, что порядок сохраняется в этих наборах, является "совпадением" и имеет отношение к разрешению конфликтов (о котором я ничего не знаю). Дело в том, что последние 3 бит hash(8), hash(16) и hash(24) совпадают. Поскольку они одинаковы, разрешение конфликтов берет на себя и помещает элементы в "резервные" ячейки памяти вместо первого (лучшего) выбора, и поэтому будет ли 8 занимать местоположение или 16 по которому кто-то прибыл в сторону первой, и взял "лучшее место".

Если мы повторим пример с 1, 2 и 3, вы получите последовательный порядок независимо от того, какой порядок у них есть в списке ввода:

list1 = [1,2,3]
set(list1)      # set([1, 2, 3])
list2 = [3,2,1]
set(list2)      # set([1, 2, 3])

поскольку последние 3 бита hash(1), hash(2) и hash(3) уникальны.

¹Примечание. Реализация, описанная здесь, применяется к CPython dict и set. Я думаю, что общее описание действительно для всех современных версий CPython до 3.6. Однако, начиная с CPython3.6, есть дополнительная деталь реализации, которая фактически сохраняет порядок вставки для итерации для dict. Похоже, что у этого set все еще нет этого свойства. Структура данных описана в этом блоге людьми pypy (которые начали использовать это перед людьми CPython). Исходная идея (по крайней мере для экосистемы python) заархивирована в списке рассылки python-dev.

Ответ 2

Причиной такого поведения является то, что Python использует хеш-таблицы для реализации словаря: https://en.wikipedia.org/wiki/Hash_table#Open_addressing

Позиция ключа определяется его адресом памяти. Если вы знаете память повторного использования Python для некоторых объектов:

>>> a = 'Hello world'
>>> id(a)
140058096568768
>>> a = 'Hello world'
>>> id(a)
140058096568480

Вы можете видеть, что каждый объект a имеет другой адрес.

Но для небольших целых чисел это не изменяется:

>>> a = 1
>>> id(a)
40060856
>>> a = 1
>>> id(a)
40060856

Даже если мы создадим второй объект с другим именем, он будет таким же:

>>> b = 1
>>> id(b)
40060856

Этот подход позволяет сохранить память, которую использует интерпретатор Python.

Ответ 3

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

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

Ответ 4

Наборы основаны на хеш-таблице. Хэш значения должен быть последовательным, поэтому порядок будет также - если два элемента хэш не совпадают с одним и тем же кодом, и в этом случае порядок вставки изменит порядок вывода.

Ответ 5

Одна ключевая вещь, которая намекала на большой ответ Майлсона, но не упоминается явно ни в одном из существующих ответов:

Малые целые хэши сами:

>>> [hash(x) for x in (1, 2, 3, 88)]
[1, 2, 3, 88]

Строки hash для значений, которые непредсказуемы. На самом деле, с 3,3 по умолчанию, они построены из семян, которые рандомизировались при запуске. Таким образом, вы получите разные результаты для каждого нового сеанса интерпретатора Python, но:

>>> [hash(x) for x in 'abcz']
[6014072853767888837,
 8680706751544317651,
 -7529624133683586553,
 -1982255696180680242]

Итак, рассмотрим простейшую возможную реализацию хеш-таблицы: просто массив из N элементов, где вставка значения означает помещение его в hash(value) % N (при отсутствии коллизий). И вы можете сделать приблизительное предположение о том, как большой N будет - он будет немного больше, чем количество элементов в нем. При создании набора из последовательности из 6 элементов N легко может быть, скажем, 8.

Что происходит, когда вы храните эти 5 чисел с N = 8? Ну, hash(1) % 8, hash(2) % 8 и т.д. - это просто числа, но hash(88) % 8 равен 0. Итак, массив хэш-таблицы заканчивается тем, что содержит 88, 1, 2, NULL, NULL, 5, NULL, 7. Поэтому должно быть легко понять, почему итерация набора может дать вам 88, 1, 2, 5, 7.

Конечно, Python не гарантирует, что вы получите этот заказ каждый раз. Небольшое изменение способа, которое оно угадывает при правильном значении для N может означать, что 88 заканчивается где-то другим (или заканчивается столкновением с одним из других значений). И, фактически, запуская CPython 3.7 на моем Mac, я получаю 1, 2, 5, 7, 88.0

Между тем, когда вы создаете хэш из последовательности размером 11, а затем вставляете в него рандомизированные хэши, что происходит? Даже предполагая простейшую реализацию и предполагая, что нет столкновений, вы все еще не знаете, какой заказ вы собираетесь получить. Он будет согласован в течение одного прогона интерпретатора Python, но при следующем запуске он будет отличаться. (Если вы не установите PYTHONHASHSEED в 0 или какое-то другое значение int.) Это именно то, что вы видите.

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