В python установлен set.pop() детерминированный?

Я понимаю, что элементы набора python не упорядочены. Вызов метода pop возвращает произвольный элемент; Я в порядке с этим.

То, что мне интересно, это то, будет ли поп ВСЕГДА возвращать тот же самый элемент, когда набор имеет ту же историю. Разумеется, в одной версии python я не против, если разные версии/реализации python делают свое дело. В частности, я спрашиваю о python 2.7. Это вопрос реализации больше, чем api в этом случае.

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

Ответ 1

Ответ в целом нет. Источником python, который @Christophe и @Marcin (un) полезно указывают на то, что элементы отображаются в том порядке, в котором они отображаются в хеш-таблице. Таким образом, порядок pop (и, предположительно, порядок итерации) является детерминированным, но только для фиксированных хеш-значений. Это случай для чисел, но не для строк, в соответствии с Примечание в документации __hash__, что, кстати, также затрагивает ваш вопрос непосредственно:

Примечание по умолчанию значения хеш() объектов str, bytes и datetime "соленые" с непредсказуемым случайным значением. Хотя они остаются постоянными в рамках отдельного процесса Python, они не предсказуемы между повторными вызовами Python.

[...]

Изменение хэш-значений влияет на порядок итераций dicts, множеств и других сопоставлений. Python никогда не предоставлял гарантии об этом заказе (и обычно он варьируется между 32-битными и 64-битными сборками).

Изменить: Как указывает @Marcin, ссылка, которую я цитировал, не относится к Python 2. Хэш-рандомизация стала стандартной с Python 3.3. Python 2.7 по умолчанию не имеет намеренно не детерминированного хеширования строк.

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

Ответ 2

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

Короче: Нет, set.pop() не является детерминированным. Не принимайте никакого заказа, поскольку API явно заявляет, что

объект set - это неупорядоченная коллекция

Документы: http://docs.python.org/library/stdtypes.html#set-types-set-frozenset
Источник: http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup

Ответ 3

В документации не указывается, что она должна быть детерминированной, поэтому вы должны предположить, что это не так.

Ответ 4

Если вы хотите заставить детерминизм, вы можете попробовать что-то вроде

value = min(my_set)
my_set.remove(value)

Ответ 5

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

Если вам нужна переносимость или вы обнаружите, что set не работает по мере необходимости, используйте orderdict (здесь один: http://code.activestate.com/recipes/576693/, есть множество других, поэтому найдите один из них, который вам нравится) и адаптируйте его как набор.

Обновление: здесь упорядоченный набор: http://packages.python.org/Brownie/api/datastructures.html#brownie.datastructures.OrderedSet