Pythonでライブラリセットクラスを使用せずにセットデータ構造を定義するプログラム

次のメソッドを使用してセットデータ構造を実装するとします-

• セットの新しいインスタンスを構築するコンストラクター
• add（val）を使用して、整数valをセットに挿入します
• presents（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が挿入されます
• 10はすでにsに含まれているため、何も起こりません
• s.exists（10）は、10が存在するためtrueを返します
• s.remove（10）で10を削除
• s.exists（10）は、10が削除され、1つの要素が1回しか存在できないため、falseを返します
• s.exists（20）は、20が存在するため、trueを返します。

これを解決するには、次の手順に従います-

• コンストラクターを定義します。
• バケット：=空のマップ。これはデータのリストを保持します
• 関数add（）を定義します。これにはvalが必要です
• presents（val）がfalseの場合、
  • バケットの最後にvalを挿入します[val]
• 関数exists（）を定義します。これにはvalが必要です
• valがbuckets[val]にある場合はtrueを返し、そうでない場合はfalseを返します
• 関数remove（）を定義します。これにはvalが必要です
• バケットを削除[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