Pythonでsetクラスを使わずにセット（集合）データ構造を自作するプログラム

本記事では、Pythonの組み込みsetクラス（ライブラリ）に頼らず、独自のセット（集合）データ構造を実装する方法を解説します。実装するセットは、以下のメソッドを持つものとします。

• コンストラクタ：セットの新しいインスタンスを生成する
• add(val)：整数valをセットに挿入する
• exists(val)：valがセット内に存在するかどうかを判定する
• remove(val)：valをセットから削除する

例えば、セットsを生成し、s.add(10)、s.add(20)、s.add(10)、s.exists(10)、s.remove(10)、s.exists(10)、s.exists(20) の順に呼び出した場合、それぞれの動作と最終的な出力は以下のようになります。

• s.add(10) → 10を挿入する
• s.add(20) → 20を挿入する
• s.add(10) → 10はすでにセット内に存在するため、何も起こらない（重複は許されない）
• s.exists(10) → 10が存在するのでTrueを返す
• s.remove(10) → 10を削除する
• s.exists(10) → 10は削除済みのためFalseを返す（同じ要素は一度しか存在できない）
• s.exists(20) → 20が存在するのでTrueを返す

アルゴリズム（実装手順）

この問題を解くためには、次の手順に従います。

• コンストラクタを定義します。
• buckets := 空の辞書（マップ）とし、ここにデータのリストを保持します。
• 関数 add() を定義します。引数として val を受け取ります。
• exists(val) が False の場合、buckets[val] の末尾に val を挿入します。
• 関数 exists() を定義します。引数として val を受け取ります。
• val が buckets[val] 内に存在すれば True、そうでなければ False を返します。
• 関数 remove() を定義します。引数として val を受け取ります。
• del によって buckets[val] を削除します。

実装例

それでは、以下のコードを見ながら理解を深めましょう。

from collections import defaultdict
class MySet:
    def __init__(self):
        self.buckets = defaultdict(list)

    def add(self, val):
        if not self.exists(val):
            self.buckets[val].append(val)

    def exists(self, val):
        return val in self.buckets[val]

    def remove(self, val):
        del self.buckets[val]

s = MySet()
s.add(10)
s.add(20)
s.add(10)
print(s.exists(10))
s.remove(10)
print(s.exists(10))
print(s.exists(20))

入力

s = MySet()
s.add(10)
s.add(20)
s.add(10)
s.exists(10)
s.remove(10)
s.exists(10)
s.exists(20)

出力

True
False
True

実装のポイント

この実装では、collectionsモジュールのdefaultdictを活用しています。defaultdict(list)を使うことで、まだ存在しないキーにアクセスした際に自動的に空のリストが生成されるため、キーの存在チェックを省略でき、コードをシンプルに保つことができます。

なお、バケット内のデータをリストで管理しているため、exists()やremove()の計算量はO(n)となります。より高速な検索が必要な場合は、バケット内部にハッシュベースの仕組みを採用するなどの工夫が考えられます。実際の開発ではPython標準のset型を使うのが一般的ですが、データ構造の学習や技術面接の対策として、このような内部実装を理解しておくことは非常に有益です。