Кто-нибудь на самом деле знает, как порядок набора определяется в Python?

Кажется, есть некоторая согласованность в том, что вызов set() в строке всегда разрешается в одном и том же (не алабетическом) порядке, и оба

set([1,2,3]) & set([1,2,3,4])

и его перепутанный двоюродный брат

set([2,3,1]) & set([4,3,1,2])

приведет к упорядоченному виду set([1,2,3]).

С другой стороны, что-то более пикантное, например

from random import randint
set([randint(0,9) for x in range(3)])

иногда будет давать что-то вроде set([9, 6, 7])...

... Что здесь происходит?


python implementation cpython unordered-set
person ben    schedule 13.02.2013    source источник
comment
en.wikipedia.org/wiki/Hash_table   -  person SLaks    schedule 14.02.2013
comment
Эта ветка может показаться вам интересной: stackoverflow.com/questions/ 3949310/   -  person ben_frankly    schedule 14.02.2013
comment
Некоторое время назад я провел несколько небольших экспериментов и думаю, что обнаружил, что это как-то бинарно, как двоичное дерево поиска (но у меня есть ощущение, что я ужасно ошибаюсь, поскольку ожидается, что оно будет вести себя как хеш-таблица). Вас могут заинтересовать это и это   -  person inspectorG4dget    schedule 14.02.2013

Ответы (1)


arrow_upward
5
arrow_downward

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

Они хранятся в хеш-таблице.

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

Нет никакой гарантии, что порядок будет одинаковым для разных версий/реализаций Python.

person John La Rooy    schedule 13.02.2013
comment
Я просто пришел оставить bugs.python.org/issue13703 здесь. Порядок, являющийся детерминированным, является деталью реализации, которая не имеет значения, важно только то, что set неупорядочен. - person mmgp; 14.02.2013
comment
@mmgp, я хотел сказать это первым, но забыл :) - person John La Rooy; 14.02.2013
comment
Я также неявно просил не упоминать, что порядок детерминирован (см. отчет). Например, запустите Python 3.3 и выполните hash('x'), выйдите из интерпретатора и запустите снова, попробуйте hash('x') еще раз. - person mmgp; 14.02.2013