0

Pythonのset構造のadd関数を使用すると、要素が理解できない位置に追加されているように見えることがわかりました。

>>> a=set([(0, 2)])
>>> a.add((0,4))
>>> a
set([(0, 2), (0, 4)])
>>> a.add((1,0))
>>> a
set([(1, 0), (0, 2), (0, 4)])
>>> a.add((2,5))
>>> a
set([(2, 5), (1, 0), (0, 2), (0, 4)])
>>> a.add((3,0))
>>> a
set([(3, 0), (2, 5), (1, 0), (0, 2), (0, 4)])
>>> a.add((1,6))
>>> a
set([(3, 0), (0, 2), (1, 6), (0, 4), (2, 5), (1, 0)])

ご覧のとおり、要素が最初に追加される場合と、最後または途中で追加される場合があります。最後の例では、既存の要素も並べ替えられました。

挿入がどのように行われるかについてのアイデアはありますか？

4

5 に答える 5

11

セットは順序付けられていません。要素がセット内の「どこ」にあるかという概念は定義されていません。

于 2012-09-02T20:30:32.147 に答える
4

Pythonのセットは順序がありません。順序は任意です。

于 2012-09-02T20:30:49.373 に答える
1

セットは、dictと同じハッシュ関数を使用して要素を追加します。確かに、それらは値要素なしでただ口述されています。

このビデオはあなたがそれをよりよく理解するのを助けるかもしれません。

整数を使用する場合、セットは（「人間の」ソートされた意味で）順序付けられます。

>>> s=set()
>>> for e in range(10):
...    s.add(e)
...    print s
... 
set([0])
set([0, 1])
set([0, 1, 2])
set([0, 1, 2, 3])
set([0, 1, 2, 3, 4])
set([0, 1, 2, 3, 4, 5])
set([0, 1, 2, 3, 4, 5, 6])
set([0, 1, 2, 3, 4, 5, 6, 7])
set([0, 1, 2, 3, 4, 5, 6, 7, 8])
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

ただし、タプルを使用する場合、人間の目には「順序付け」されていません。

>>> s=set()
>>> for t in ((i,i*i) for i in range(10)):
...    s.add(t)
...    print s
... 
set([(0, 0)])
set([(0, 0), (1, 1)])
set([(0, 0), (1, 1), (2, 4)])
set([(3, 9), (0, 0), (1, 1), (2, 4)])
set([(3, 9), (0, 0), (1, 1), (4, 16), (2, 4)])
set([(0, 0), (4, 16), (5, 25), (3, 9), (2, 4), (1, 1)])
set([(6, 36), (0, 0), (4, 16), (5, 25), (3, 9), (2, 4), (1, 1)])
set([(6, 36), (0, 0), (7, 49), (4, 16), (5, 25), (3, 9), (2, 4), (1, 1)])
set([(6, 36), (0, 0), (7, 49), (4, 16), (5, 25), (3, 9), (2, 4), (1, 1), (8, 64)])
set([(6, 36), (0, 0), (7, 49), (4, 16), (5, 25), (3, 9), (9, 81), (2, 4), (1, 1), (8, 64)])

次に、インタプリタで次の2行を試してください。

>>> dict.fromkeys(range(10),None)
{0: None, 1: None, 2: None, 3: None, 4: None, 5: None, 6: None, 7: None, 8: None, 9: None}
>>> dict.fromkeys(((i,i*i) for i in range(10)),None)
{(6, 36): None, (0, 0): None, (7, 49): None, (4, 16): None, (5, 25): None, (3, 9): None, (9, 81): None, (2, 4): None, (1, 1): None, (8, 64): None}

生成されたdictは、設定された例と同じ「順序」であることがわかります。

dictとintキーのみを使用したセットは「順序付け」できますが、実用的な観点からは、dictとsetには順序がありません。

リンクされたビデオを見ると、その理由がわかります。

于 2012-09-02T20:37:39.900 に答える
1

要素は、ハッシュ値に従ってハッシュテーブルの特定の場所に移動します。最後の3ビットが同じ要素の場合、衝突が発生し、他のスポットが選択されます。ハッシュテーブルは、2/3がいっぱいになるとすぐに拡張され、衝突率が低下します。ハッシュテーブルでこのビデオを参照してください。

>>> def bits(n):
    n+=2**32
    return bin(n)[-32:]

>>> bits(hash('a'))
'11100100000011011011000111100000' #last three bits are picked to determine the spot in hash table
>>> bits(hash('b'))
'11101011101011101101001101100011'
于 2012-09-02T20:42:36.790 に答える
0

他の答えが言ったように：

  • セットは順序がないように動作することになっています
  • セットに物を追加するための実際のメカニズムは、辞書の場合と同じです。セットは基本的にアイテムのないキーの辞書です
  • 辞書はハッシュテーブルに基づいています（これについて詳しくは、辞書とハッシュテーブルの本当の違いは何ですか？）

舞台裏で何が起こっているのかを見るのは役に立つかもしれないと思ったので、setのadd()メソッドの実際のソースコードをコメントしました（スクロールして申し訳ありません）。

def add(self, element):
    """Add an element to a set.

    This has no effect if the element is already present.
    """
    try:
        self._data[element] = True                             # self._data is the dictionary where all of the set elements are stored
    except TypeError:                                          # this try...except block catches the cases when element cannot be a dict key (that is, it isn't hashable)
        transform = getattr(element, "__as_immutable__", None) # the getattr() call is the same as trying to get element.__as_immutable__ and returning None if element doesn't have __as_immutable__
        if transform is None:                                     
            raise # re-raise the TypeError exception we caught # if we get to this line, then the element has no defined way to make it immutable (and thus hashable), so a TypeError is raised
        self._data[transform()] = True                         # so if we get here, transform() is the same as calling element.__as_immutable__() (which we know exists), and we can now add it to the self._data dict

ご覧のとおり、セットadd(element)はdictと同じですが、add(element)ハッシュするのが少し難しい点が異なりelementます。

于 2012-09-02T21:07:56.663 に答える