【Python】set型の基本と、死ぬほど遅い「hoge in list」からの脱却
# python # set # 入門
set型とは
公式ドキュメントより
公式ドキュメントには以下のような記載があります。
set オブジェクトは、固有の hashable オブジェクトの順序なしコレクションです。通常の用途には、帰属テスト、シーケンスからの重複除去、積集合、和集合、差集合、対称差 (排他的論理和) のような数学的演算の計算が含まれます。
集合は、他のコレクションと同様、
x in set,len(set),for x in setをサポートします。コレクションには順序がないので、集合は挿入の順序や要素の位置を記録しません。従って、集合はインデクシング、スライシング、その他のシーケンス的な振舞いをサポートしません。参照）公式ドキュメント
はい、これだけでは分かりづらいですね。備忘も兼ねて特徴や使い道をまとめていきます。
基本的な特徴
- 同じ要素は一つしか含まれない。
- x in set, len(set), for x in set というような、listのような操作が可能
- 要素を後から追加・削除など変更可能（tupleは変更不可、listは変更可能なのでどちらかというとlistに近い）
- 集合演算が可能（Aに含まれてBに含まれない、A・B両方に含まれるなどの計算が手軽かつ高速に可能）
- 順番が保持されないため、最初に入れたものが最初にあるとは限らない
- listに比べて「x in set」という動作が超高速
言葉でまとめてしまうと、listは順番を付けて並べるもの、setは順番のないユニークな値の集まりです。 順番を保持しないがため諸々の演算がlistに比べて高速に出来るのも大きな特徴です。
set型の集合演算の基本
和集合（AかBに含まれる）
a = set([1,2,3,4,5])
b = set([3,4,5,6,7])
print(a | b)
# {1, 2, 3, 4, 5, 6, 7}
# a.union(b) でもok
見事に重複を排除した値が出力されています（当然）
共通部分（AとBに含まれる）
a = set([1,2,3,4,5])
b = set([3,4,5,6,7])
print(a & b)
# {3, 4, 5}
# a.intersection(b) でもok
差集合（Aに含まれてBに含まれない）
a = set([1,2,3,4,5])
b = set([3,4,5,6,7])
print(a - b)
# {1, 2}
# a.difference(b) でもok
AかBのいずれか一方にだけ含まれる値
a = set([1,2,3,4,5])
b = set([3,4,5,6,7])
print(a ^ b)
# {1, 2, 6, 7}
# a.symmetric_difference(b) でもok
その他にも以下のメソッドがあります。便利です。
- 共通部分の有無を判定する「isdisjoint」
- 部分集合化を判定する「<,<=」（issubset）
- 上位集合かを判定する「>,>=」(issuperset)
listやtupleとは比べ物にならない高速「x in set」
for in set は for in list に比べて圧倒的に速い（dictのキーを用いる検索も高速です）のです。
こんな感じでテストをしてみます（コードはqiitaより拝借）
def list_test(q, h):
ls = [i for i in range(0, q * h, h)]
for i in range(q): i in ls
def set_test(q, h):
st = set(i for i in range(0, q * h, h))
for i in range(q): i in st
def exe(func, num=100):
from timeit import timeit
setup = 'from __main__ import ' + func[:5]
print("%s: %s" % (func, timeit(func, setup, number=num)))
q = 10 ** 4
funcs = ['lists', 'setts']
hits = [1, 2, 3]
for h in hits:
for f in funcs:
func = '%s(%s, %s)' % (f, q, h)
print
func
exe(func, 10)
# -----
# lists(10000, 1): 7.690
# setts(10000, 1): 0.018
# -----
# lists(10000, 2): 9.475
# setts(10000, 2): 0.018
# -----
# lists(10000, 3): 11.316
# setts(10000, 3): 0.016
結果はなんとおよそset型を使用した場合は、listの約100倍ほど高速！
なぜこうなるかというと、list型はすべての要素に対して一致する要素があるかを最初から頑張って探しているからです。 要素が一つ増えることに、100万個あった場合、目的の要素が最後にあると考えると恐ろしいですよね。
それに対してset型は検索が行いやすいようにデータを整列して保持しています。 （逆に言えば、そのため要素を追加した順番は保持されません。） データが整列されているため、例えば「1,000」があるかを探したいとなった場合、真ん中の数字より大きいか小さいを判定、大きければ大きい方の真ん中の数字より大きいか小さいか判定・・・ というように要素を半分ずつに絞り込んで行く、というようなことが可能となっています。
データベースでindexを貼られているようなイメージを持っていて差し支えありません。
set要素はこんな時に使え！
- 大量の要素に「x in list」するなら、代わりに「x in set」
- 重複を省いた結果を返したい
- Aに含まれてBに含まれないなど、集合演算をする時
set要素を効果的に使ってコーディングをすることで、速度を改善できることや、見通しのよいコードを書くことが出来るようになります。 setを使いこなしてよいPythonライフを！