セット

概要

セット型は複数の要素を持つことができるリストに似た型です。 ただ、セットの要素には順序がなく、同じ要素を重複して持つことができません。

順序がないということは要素群「A, B」と要素群「B, A」に違いがないということで、 重複した要素群を持てないということは「A, B, A」とできないことです。 「A, B」を「A, B, A」にしようとしても「A, B」のまま変わりません。

これらの制約が問題ないのであれば、リストよりもセットを使うことを検討すべきです。 順序管理の仕組みを持たないセットはリストよりも高速に効率よく動作します。 これは内部的にハッシュという仕組みを使っているためです。

セット型の特徴

セット型は数学の「 集合 」という概念を実現するための型です。 かなり大雑把にいってしまうと「同じ要素の重複がなく、順番がないリスト」という性質をもつデータ構造の型だといえます。

たとえば、なにも要素を持たない(このことを「空(から)」といいます)セットにたいして、Aを追加したとします。 そのセットの中には要素Aがあります。 このセットにBを追加すると、セットの中にはAとBの2つが存在するようになります。

しかし、ここにさらにAを追加しても、「A、A、B」とはならずに「A、B」のままです。 これはセットの「同じ要素の重複はない」という性質からきています。

また、セットの要素には順序はないので、「AとB」と「BとA」に違いはありません。 リストのようなインデックス番号を使った操作は一切できないため、最初にいれた要素を取り出したり、 最後にいれた要素を更新するといったこともできません。

できるのはある値と同じ値を持つ要素が存在するかを確認したり、 無作為に要素を取り出したりするといったことです。

セットはリストより制限が多いですが、要素数が多くなっても動作が非常に高速という強みもあります。 そのため、セットでもリストでもどちらでもよい状況ではセットを利用します。

セット型の基本操作

初期化

何も要素を持たないセットのインスタンスを作るにはset関数を使います。

>>> a = set()
>>> print(type(a))
<class 'set'>

空でないセットを作る場合は中括弧「{}」に要素をコンマ区切りで並べることで作れます。

>>> a = {3, 1, 2, 1}
>>> print(type(a))
<class 'set'>
>>> print(a)
{1, 2, 3}

初期化をする際に2つの1を要素としていますが、 要素は重複できないためセットの中身を確認した際に1はひとつしか表示されていません。

空のセットは「{}」としても作成されないので注意をしてください。 これは空のセットではなく、空の辞書型をつくります。

セットへのキャスト

set関数を使うことでリストや辞書型をセットにすることができます。

>>> a = [1,2,3,1,5,4]
>>> b = set(a)
>>> print(b)
{1, 2, 3, 4, 5}

リストでは重複していた1という要素が、セットにすると重複しなくなっています。 ただ、順序も変わっていることが分かります。

辞書型のキーのみが必要な場合はセットにキャストできます。

>>> a = {'a':1, 'b':2, 'c':3}
>>> set(a)
{'c', 'a', 'b'}
>>> b = set(a)
>>> print(b)
{'c', 'a', 'b'}

セットの演算子

in演算子

# in, not in を使える
a = {1,3,5,7}
print(1 in a)
# True
print(2 in a)
# False

比較演算子

あまり利用場面は多くないかもしれませんが、集合特有の演算をすることもできます。

# 比較
print({1,2,3} < {1,2,3,4})
# True

# AND(両方含むもののみ)
print({1,2,3} & {3,4,5})
# {3}

# OR(結合)
print({1,2,3} | {3,4,5})
# {1, 2, 3, 4, 5}

セットのメソッド

add : 集合への要素の追加

セットへの要素の追加や削除にはメソッドを使います。 追加をするにはセットのインスタンスにたいしてaddメソッドを呼び出します。

a = {1, 2, 3}
a.add(4)
print(a)
# {1, 2, 3, 4}

addメソッドですでに存在している要素を追加しようとしても、何も変わりません。 エラーにもならないのでin演算子で存在の有無を確認する必要はないです。

a.add(2)
print(a)
# {1, 2, 3, 4}

remove : 集合から要素を削除

削除にはremoveメソッドを使います。

a.remove(1)
print(a)
# {2, 3, 4}

存在しない要素をremoveメソッドで消そうとするとエラーになるので注意してください。

pop : 要素の取得

セットから要素を一つ抜き出すにはpopメソッドを使います。 このメソッドを呼ぶとセットからランダムに要素を一つ削除して、それを返り値として返します。 セットには順番がないため、引数にインデックス番号は指定しません。

b = a.pop()
print(a)
# {3, 5, 7}
print(b)
# 1

union : 2つのセットの結合

リストと若干異なるのはセットの結合です。 先程説明したようにセットは重複した要素を持たないため、 結合される2つのセットが同じものを持っていれば1つだけになります。 プラス記号を使った結合はできません。

a = {1,2,3}
a.union({3,4,5})
print(a)
# {1, 2, 3, 4, 5}

print(a + {5,6,7})
# Traceback (most recent call last):
# ...
# TypeError: unsupported operand type(s) for +: 'set' and 'set'

ハッシュの仕組み

セットで使われている重要なコンピュータ技術に、ハッシュ(Hash)と呼ばれているものがあります。 集合はハッシュを使わずにでも実現できるでしょうが、 PythonのセットはJavaでいうところのHashSetに近いです。 このハッシュの概念図を以下に示します。

image

ハッシュは「ハッシュ関数」と呼ばれるものに特定の値(キー)を与えて「ハッシュ値」を得ることで実現されています。 ハッシュ値はある範囲のなかの数値(一般的には0からN)のどれかとなり、 同じキーから生成されるハッシュ値は常に同じです。

上記の図でいうと、キーとして「John Smith」をハッシュ関数にかけるとハッシュ値「02」が得られています。 同様に「Lisa Smith」をハッシュ関数にかけると「01」となります。 そしてハッシュ値の範囲は00から15です。 この性質を考慮したうえで「ある集合に要素Xはあるか」ということをどのようにして実現するか想像してください。

ハッシュを使う場合、たとえば「John Smith」を集合に加える際には、 ハッシュ値「02」の場所に「John Smith」を格納します。 そして「John Smith」が存在するかどうかのチェックはハッシュ値「02」の場所に「John Smith」がいるかどうか確認すればいいのです。 一方、リストの探索であれば「先頭から末尾まで順に「John Smith」かどうかを確認していく」ことが必要です。 リストのサイズが大きければこの探索コストは非常に大きくなります。 「要素」の探索という面においてハッシュはリストに比べるとであるのに比べると随分スマートだと思いませんか。 実際、ハッシュを使った要素の探索は非常に高速です。

ただ、ハッシュも使い方を間違えると効率が悪くなります。もう一度図を見てください。 よく見ると「John Smith」と「Sandra Dee」は同じハッシュ値に割り当てられています。 これはいわゆる「ハッシュの衝突」と呼ばれており、これが多発すると探索のスピードが遅くなります。 なぜなら「Sandra Dee」の有無の確認をする際に「01」を見にいって、 そこに「John Smith」やほかの要素がたくさん入っていると、 「01」のなかで「リストの探索」のようにして全部をチェックしていかないといけないからです。

この問題を防ぐためにハッシュ値の範囲は十分な広さを持たせる必要があります。 たとえば今回のように00から15などという範囲は狭すぎるので、これをもっと広げます。 そうすると確率的には衝突は発生しにくくなります。 ただ、通常はこんなことを気にしなくてもPythonがよしなに処理してくれるので大丈夫です。