Является ли «набор» python «стабильным»?

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

>>> s1 = {-1, -2} >>> s2 = {-2, -1} >>> s1 == s2 True >>> list(s1), list(s2) ([-1, -2], [-2, -1]) 

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

И когда я повторяю одну и ту же программу python несколько раз (не случайный, не зависимый от ввода), получаю ли я тот же порядок для наборов?

Я могу ответить на эту часть вопроса сейчас после быстрого эксперимента. Используя следующий код:

 class Foo(object) : def __init__(self,val) : self.val = val def __repr__(self) : return str(self.val) x = set() for y in range(500) : x.add(Foo(y)) print list(x)[-10:] 

Я могу спровоцировать поведение, о котором я спрашивал в другом вопросе. Если я буду запускать это повторно, то выход будет изменяться, но не на каждом прогоне. Кажется, он «слабо случайен» в том, что он медленно меняется. Это, безусловно, зависит от реализации, поэтому я должен сказать, что я запускаю macports Python2.6 на снежном барсе. Хотя программа будет выдавать один и тот же ответ в течение длительных периодов времени, делая что-то, что влияет на пул энтропии системы (запись на диск в основном работает) когда-нибудь ударит его в другой выход.

Класс Foo – это просто простая обертка int, поскольку эксперименты показывают, что этого не происходит с наборами int. Я думаю, что проблема вызвана отсутствием членов __eq__ и __hash__ для объекта, хотя я бы очень хотел знать лежащее в основе объяснение / способы избежать этого. Также полезно было бы каким-то образом воспроизвести / повторить «плохой» прогон. Кто-нибудь знает, какое семя он использует, или как я могу установить это семя?

Определение множества неупорядочено, уникальные элементы ( «Неупорядоченные коллекции уникальных элементов» ). Вы должны заботиться только об интерфейсе, а не о реализации. Если вы хотите упорядоченное перечисление, вы должны, вероятно, поместить его в список и отсортировать.

Существует много различных реализаций Python. Не полагайтесь на недокументированное поведение, так как ваш код может сломаться на разных реализациях Python.

Определенно определенная реализация определена. Спецификация набора говорит только о том, что

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

Почему бы не использовать OrderedDict для создания собственного класса OrderedSet?

Как указано, это строго детализация.

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

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

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