59

Python のセットが順序付けられていないことは理解していますが、一貫しているように見えるため、それらが表示される「順序」に興味があります。それらは毎回同じように順不同のようです:

>>> set_1 = set([5, 2, 7, 2, 1, 88])
>>> set_2 = set([5, 2, 7, 2, 1, 88])
>>> set_1
set([88, 1, 2, 5, 7])
>>> set_2
set([88, 1, 2, 5, 7])

...そして別の例:

>>> set_3 = set('abracadabra')
>>> set_4 = set('abracadabra')
>>> set_3
set(['a', 'r', 'b', 'c', 'd'])
>>>> set_4
set(['a', 'r', 'b', 'c', 'd'])

これがなぜなのか、私はただ興味があります。何か助けはありますか？

4

5 に答える 5

52

このビデオを見る必要があります(これは CPython 1固有の辞書に関するものですが、セットにも当てはまると思います)。

基本的に、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])

これらのセットで順序が保持されるという事実は「偶然」であり、衝突の解決に関係していることに注意してください(これについては何も知りません)。hash(8)ポイントは、 、、 の最後の 3 ビットが同じであることです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)は一意です。

1注ここで説明する実装は、CPythondictおよびset. 一般的な説明は、3.6 までの CPython のすべての最新バージョンに有効だと思います。ただし、CPython3.6 以降では、 の反復の挿入順序を実際に保持する追加の実装の詳細がありますdict。このプロパティはsetまだないようです。データ構造は、pypy の人々 (CPython の人々よりも前にこれを使い始めた)によるこのブログ投稿で説明されています。元のアイデア (少なくとも python エコシステム用)は python-dev メーリング リスト にアーカイブされています。

于 2012-08-28T18:23:18.547 に答える
6

このような動作の理由は、Python が辞書の実装にハッシュ テーブルを使用するためです: https://en.wikipedia.org/wiki/Hash_table#Open_addressing

キーの位置は、そのメモリ アドレスによって定義されます。一部のオブジェクトで Python がメモリを再利用することを知っている場合:

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

オブジェクトが初期化されるたびに異なるアドレスを持つことがわかります。

ただし、小さな整数の場合は変更されません。

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

別の名前で 2 番目のオブジェクトを作成しても、同じになります。

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

このアプローチにより、Python インタープリターが消費するメモリを節約できます。

于 2015-09-09T17:09:25.903 に答える
3

AFAIK Python セットは、ハッシュ テーブルを使用して実装されます。アイテムが表示される順序は、使用するハッシュ関数によって異なります。プログラムの同じ実行内では、ハッシュ関数はおそらく変更されないため、同じ順序になります。

ただし、常に同じ関数を使用するという保証はなく、実行間で順序が変更されるか、または多くの要素を挿入してハッシュ テーブルのサイズを変更する必要がある場合は、同じ実行内で順序が変更されます。

于 2012-08-28T18:29:57.183 に答える
2

セットはハッシュ テーブルに基づいています。値のハッシュは一貫している必要があるため、順序も同じになります。ただし、2 つの要素が同じコードにハッシュされる場合を除きます。この場合、挿入の順序によって出力順序が変更されます。

于 2012-08-28T18:23:26.137 に答える