Недетерминированные множества в Python 2 и 3

Питон 2

Наборы — это наборы неупорядоченных значений. Если я создаю набор через литерал набора, например.

s = {'a', 'b', 'c'}

а затем распечатать, я получаю элементы в каком-то перемешанном порядке. Однако кажется, что в Python 2.7 приведенный выше пример всегда приводит к одному и тому же порядку:

print(s)  # set(['a', 'c', 'b']) in Python 2.7

Как Python 2.7 решает этот порядок? Даже хэши 'a', 'b' и 'c' не в том порядке, в котором они были созданы.

Питон 3

В Python 3.x (включая 3.6, где dict ключей упорядочены) результирующий порядок кажется случайным, хотя всегда одинаковым в данном процессе Python. То есть повторное построение заданного литерала всегда приводит к одному и тому же порядку, пока я не перезапущу интерпретатор Python.

Чтобы проверить порядок в нескольких процессах Python, рассмотрите код bash

(for _ in {1..50}; do python3 -c "s = {'a', 'b', 'c'}; print(s)"; done) | sort -u

Это (чаще всего) покажет 6 различных способов расположения 3 элементов. Заменяя python3 на python(2), мы видим только порядок ['a', 'c', 'b']. Что определяет порядок в Python 3?

Я вижу, что значение hash объектов является детерминированным в Python 2, в то время как случайное (хотя и постоянное в процессе Python) в Python 3. Я уверен, что это ключ к полному объяснению.

Редактировать

Как пишет deceze в своем комментарии, я хотел бы знать, делает ли Python что-то явно только для достижения этой рандомизации, или это происходит «бесплатно».


python-3.x python python-2.7 set non-deterministic
person jmd_dk    schedule 18.04.2018    source источник
comment
В чем смысл? Вы не должны полагаться на определенный порядок наборов или диктов. Если вам это нужно, используйте OrderedDict. Кроме того, обнаруженное вами поведение хеш-функции согласуется со свойствами, которые должна иметь хеш-функция. Если вам нужен детерминированный хеш, реализуйте свой собственный.   -  person fferri    schedule 18.04.2018
comment
Ожидается, что в детерминированном алгоритме будет некоторый порядок, если только Python не приложит все усилия, чтобы преднамеренно рандомизировать порядок.   -  person deceze♦    schedule 18.04.2018
comment
В то время как полные хэш-значения этих символов не в том порядке, их младшие биты! Для небольших контейнеров на основе хэша python использует только эти младшие биты.   -  person Wombatz    schedule 18.04.2018
comment
@Wombatz Спасибо, это довольно большая часть головоломки.   -  person jmd_dk    schedule 19.04.2018

Ответы (1)


arrow_upward
5
arrow_downward

Причина различия в Python 3 (начиная с Python 3.3) заключается в том, что рандомизация хэшей включена по умолчанию, вы можете отключить ее, установив PYTHONHASHSEED переменной среды на фиксированное значение:

$ export PYTHONHASHSEED=0
$ (for _ in {1..50}; do python3  -c "s = {'a', 'b', 'c'}; print(s)"; done) | sort -u
{'a', 'b', 'c'}

Точно так же вы можете включить рандомизацию хэшей в Python 2 с помощью флага -R:

$ (for _ in {1..50}; do python2 -R -c "s = {'a', 'b', 'c'}; print(s)"; done) | sort -u
set(['a', 'b', 'c'])
set(['a', 'c', 'b'])
set(['b', 'c', 'a'])
set(['c', 'b', 'a'])

Обратите внимание, что обычно вы не хотите отключать его, поскольку включение рандомизации хэшей помогает защитить от определенных атак типа «отказ в обслуживании».

person Chris_Rands    schedule 18.04.2018
comment
Просто не забудьте включить его обратно :). Хороший +1! - person Ma0; 18.04.2018
comment
Основная причина, по которой я хотел бы отключить его, заключается в том, что при написании симуляций методом Монте-Карло я всегда распечатываю значение random.seed и предоставляю средства для указания начального числа при запуске кода. Таким образом, если во время симуляции произойдет что-то смешное (ошибка или интересное поведение), я смогу повторно запустить ту же самую траекторию, скажем, с дополнительными результатами для исследования. - person wchlm; 31.10.2018