セット（抽象データ型）

コンピュータサイエンスにおいて、セットとは、特定の順序なしに一意の値を格納できる抽象データ型です。これは、有限セットという数学的概念のコンピュータ実装です。他のほとんどのコレクション型とは異なり、セットから特定の要素を取得するのではなく、通常は値がセットのメンバーシップかどうかをテストします。

一部のセット データ構造は、構築後に変更されない静的または固定セット用に設計されています。静的セットでは、特定の値がセット内にあるかどうかの確認や、任意の順序での値の列挙など、要素に対するクエリ操作のみが許可されます。動的セットまたは可変セットと呼ばれるその他のバリアントでは、セットへの要素の挿入と削除も許可されます。

マルチセットは、要素がセット内で複数回出現できる特別な種類のセットです。

型理論では、集合は一般にその指示関数（特性関数）によって識別されます。したがって、型の値の集合は、またはで表されます。（サブタイプとサブセットは、精製型によってモデル化され、商集合は、 setoidsによって置き換えられることがあります。）集合の特性関数は、次のように定義されます。 ${\displaystyle A}$${\displaystyle 2^{A}}$${\displaystyle {\mathcal {P}}(A)}$${\displaystyle F}$${\displaystyle S}$

${\displaystyle F(x)={\begin{cases}1,&{\mbox{if }}x\in S\\0,&{\mbox{if }}x\not \in S\end{cases}}}$

理論的には、他の多くの抽象データ構造は、標準操作に追加の操作や追加の公理が課されたセット構造として見ることができます。たとえば、抽象ヒープは、最小値の要素を返す操作を含むセット構造として見ることができます。 min(S)

集合代数の演算を次のように定義することができます。

• union(S,T):セットSとTの和集合を返します。
• intersection(S,T):集合SとTの積集合を返します。
• difference(S,T):セットSとTの差を返します。
• subset(S,T): 集合Sが集合Tのサブセットであるかどうかをテストする述語。

静的セット構造Sによって提供される典型的な操作は次のとおりです。

• is_element_of(x,S): 値xが集合S内にあるかどうかを確認します。
• is_empty(S): 集合Sが空かどうかをチェックします。
• size(S)または: S内の要素の数を返します。cardinality(S)
• iterate(S): 呼び出しごとにSの値を 1 つ以上任意の順序で返す関数を返します。
• enumerate(S): Sの要素を任意の順序で含むリストを返します。
• build(x1,x2,…,xn,): 値x ₁、x ₂、...、x _nを持つセット構造を作成します。
• create_from(collection): 指定されたコレクションのすべての要素、または指定されたイテレータによって返されるすべての要素を含む新しいセット構造を作成します。

動的セット構造では通常、次のものが追加されます。

• create(): 最初は空の新しいセット構造を作成します。
  • create_with_capacity(n): 最初は空ですが、最大n個の要素を保持できる新しいセット構造を作成します。
• add(S,x): 要素xがまだ存在しない場合は、Sに追加します。
• remove(S, x): Sに要素xが存在する場合はそれを削除します。
• capacity(S): S が保持できる値の最大数を返します。

セット構造によっては、これらの操作の一部しか実行できない場合があります。各操作のコストは実装によって異なり、セットに格納されている特定の値や、それらの挿入順序によっても異なります。

上記の点に基づいて（原則として）定義できる他の操作は多数あります。たとえば、次のとおりです。

• pop(S): Sの任意の要素をSから削除して返します。^[1]
• pick(S): Sの任意の要素を返します。^{[2] [3] [4]}機能的には、ミューテーターはpopセレクタのペアとして解釈でき(pick, rest),、rest任意の要素を除くすべての要素からなるセットを返します。^[5]の観点から解釈できますiterate。^[a]
• map(F,S): 関数F をSの各要素に適用した結果の異なる値のセットを返します。
• filter(P,S): 指定された述語P を満たすSのすべての要素を含むサブセットを返します。
• fold(A0,F,S): Sの各要素eに何らかの二項演算F を適用した後、値A _{| S |を返します。これが明確に定義されるためには、} F は結合法則と可換法則を備えている必要があります。Ai+1 := F(Ai, e)
• clear(S): Sのすべての要素を削除します。
• equal(S1', S2'): 指定された 2 つのセットが等しいかどうか (つまり、すべて同じ要素のみが含まれているかどうか) を確認します。
• hash(S):静的集合Sのハッシュ値を返す。equal(S1, S2)hash(S1) = hash(S2)

特殊なタイプの要素を持つセットに対して、他の演算を定義できます。

• sum(S): 何らかの「合計」の定義に従って、 Sのすべての要素の合計を返します。たとえば、整数または実数の場合は、 と定義されます。fold(0, add, S)
• collapse(S): 集合の集合が与えられた場合、その集合の和集合を返す。^[6]例えば、collapse({{1}, {2, 3}}) == {1, 2, 3}は の一種とみなされるsum。
• flatten(S): セットとアトミック要素（セットではない要素）からなるセットが与えられると、元のトップレベルセットのアトミック要素またはそのセットに含まれるセットの要素を要素とするセットを返します。言い換えれば、ネストのレベルを削除します。 と似ていますcollapse,が、アトムを許可します。 これは1回だけ実行することも、再帰的に平坦化してアトミック要素のみのセットを取得することもできます。^[7]たとえば、flatten({1, {2, 3}}) == {1, 2, 3}.
• nearest(S,x): Sの要素のうち、値がxに最も近い要素を返します(ある基準によって)。
• min(S), : Sの最小/最大要素を返します。max(S)

セットは、さまざまなデータ構造を使用して実装できます。データ構造は、さまざまな操作に対してさまざまな時間とスペースのトレードオフを提供します。一部の実装は、またはなどの非常nearestに特殊な操作の効率を向上させるように設計されています。 union「汎用」と説明されている実装は、通常element_of、、、addおよび操作の最適化を目指しています。簡単な実装は、リストをdelete使用して、要素の順序を無視し、重複した値を回避することです。これは単純ですが、セットのメンバーシップや要素の削除などの操作はリスト全体をスキャンする必要があるため、O ( n ) であるため非効率的です。 ^{[b]セットは、多くの場合、より効率的なデータ構造、特にさまざまな種類の}ツリー、トライ、またはハッシュテーブルを使用して実装されます。

セットは（指示関数によって）一種のマップとして解釈できるため、セットは一般に（部分的な）マップ（連想配列）と同じ方法で実装されます。この場合、各キーと値のペアの値はユニット型またはセンチネル値（1など）を持ちます。つまり、ソート済みセットの場合は自己バランス型二分探索木^{[定義が必要]}（ほとんどの操作でO(log n)）、またはソートされていないセットの場合はハッシュテーブル（ほとんどの操作で平均ケースでO(1)、最悪ケースでO(n)）です。ソートされた線形ハッシュテーブル^[8]は、決定論的に順序付けられたセットを提供するために使用できます。

さらに、マップはサポートしているがセットはサポートしていない言語では、セットをマップで実装できます。たとえば、Perlの一般的なプログラミング イディオムでは、配列を、セットとして使用するために、値がセンチネル値 1 であるハッシュに変換します。

私の%elements = map { $_ => 1 } @elements ;         

その他の一般的な方法には配列があります。特に、整数 1.. nのサブセットは、 nビットのビット配列として効率的に実装でき、非常に効率的な結合および交差演算もサポートします。ブルーム マップは、非常にコンパクトな表現を使用してセットを確率的に実装しますが、クエリで誤検出が発生する可能性がわずかにあります。

ブール集合演算は、より基本的な演算 ( pop、clear、add) で実装できますが、特殊なアルゴリズムを使用すると漸近的な時間制限が低くなる可能性があります。たとえば、集合がソートされたリストとして実装されている場合、 の単純なアルゴリズムでは、S の長さ m と T の長さ n の積に比例した時間がかかります。一方、リスト結合アルゴリズムの変形では、m + nに比例した時間で処理が実行されます。さらに、他の演算を犠牲にして、これらの演算の 1 つ以上に最適化された特殊な集合データ構造 (和集合検索データ構造など) もあります。 union(S,T)

セットをサポートする最も初期の言語の 1 つはPascalです。現在では多くの言語が、コア言語または標準ライブラリにセットを組み込んでいます。

• C++では、標準テンプレート ライブラリ(STL) がsetテンプレート クラスを提供します。これは通常、バイナリ検索木 (例: 赤黒木) を使用して実装されます。SGIの STL もテンプレート クラスを提供します。hash_setこれはハッシュ テーブルを使用してセットを実装します。C ++11 は、ハッシュ テーブルを使用して実装されるテンプレート クラスをサポートしていますunordered_set。セットでは、要素自体がキーであり、要素がその (相対または絶対) 位置を使用してアクセスされるシーケンス コンテナーとは対照的です。セット要素には、厳密な弱い順序付けが必要です。
• Rust標準ライブラリはジェネリックHashSetとBTreeSet型を提供します。
• Java は、セットをサポートするためのSet インターフェース(クラスはHashSetハッシュ テーブルを使用して実装) と、SortedSetソートされたセットをサポートするためのサブインターフェース (クラスはバイナリ検索ツリーを使用して実装)を提供しTreeSetます。
• AppleのFoundation フレームワーク( Cocoaの一部) は、Objective-CクラスNSSet、、、、およびを提供します。CoreFoundation APIはNSMutableSet、Cで使用するための CFSet および CFMutableSet 型を提供しNSCountedSetます。NSOrderedSetNSMutableOrderedSet
• Python には2.4 以降、組み込みの set 型と freezeset 型があり、Python 3.0 および 2.7 以降では、中括弧構文を使用した空でない set リテラルをサポートしています。例: ; Python は空の辞書を表すために を使用するため{x, y, z}、空のセットは を使用して作成する必要があります。set(){}
• .NET Framework は、ジェネリック インターフェイスを実装するジェネリック クラスHashSetとクラスを提供します。SortedSetISet
• Smalltalkのクラス ライブラリには、包含テストにそれぞれ等価性および同一性を使用するSetと が含まれています。多くの方言では、圧縮ストレージ ( 、)、順序付け ( 、など)、または弱参照( ) のバリエーションが提供されています。IdentitySetNumberSetCharacterSetOrderedSetSortedSetWeakIdentitySet
• Rubyの標準ライブラリには、ハッシュ テーブルを使用してセットを実装するsetモジュールSetとSortedSetクラスが含まれており、ハッシュ テーブルを使用すると、ソートされた順序で反復処理を行うことができます。
• OCamlの標準ライブラリには、Setバイナリ検索ツリーを使用して機能セット データ構造を実装するモジュールが含まれています。
• HaskellのGHC実装は、二分探索木を使用して不変集合を実装するモジュールを提供します。^[9]Data.Set
• Tcl Tcllibパッケージは、 TCL リストに基づいてセット データ構造を実装するセット モジュールを提供します。
• Swift 1.2 以降、 Swift標準ライブラリには型が含まれていますSet。
• JavaScriptはECMAScript 2015 ^[10]Set標準で標準組み込みオブジェクトとして導入されました。
• Erlangの標準ライブラリにはsetsモジュールがあります。
• Clojure にはハッシュ セットのリテラル構文があり、ソート セットも実装されています。
• LabVIEW はバージョン 2019 からセットをネイティブにサポートしています。
• Ada はAda.Containers.Hashed_Sets、およびパッケージを提供しますAda.Containers.Ordered_Sets。

前のセクションで述べたように、セットを直接サポートしていないが連想配列をサポートしている言語では、要素をキーとして使用し、無視されるダミー値を値として使用することで、連想配列を使用してセットをエミュレートできます。

セットの概念を一般化したものには、マルチセットまたはバッグがあります。これはセットに似ていますが、繰り返される（「等しい」）値（重複）を許可します。これは、2つの異なる意味で使用されます。等しい値は同一とみなされ、単にカウントされるか、等しい値は同等とみなされ、異なる項目として保存されます。たとえば、人（名前別）と年齢（年数）のリストが与えられた場合、年齢のマルチセットを作成できます。これは、特定の年齢の人の数を単純にカウントします。または、人のマルチセットを作成することもできます。この場合、2 人の年齢が同じ（ただし、異なる人で名前が異なる場合もあります）場合は、2 人が同等とみなされます。この場合、各ペア（名前、年齢）を保存する必要があり、特定の年齢を選択すると、特定の年齢のすべての人が返されます。

正式には、コンピュータ サイエンスのオブジェクトは、ある同値関係では「等しい」と見なされる一方で、別の関係では依然として異なると見なされる場合があります。一部のタイプのマルチセット実装では、異なる等しいオブジェクトをデータ構造内の個別の項目として保存します。一方、他の実装では、それを 1 つのバージョン (最初に検出されたバージョン) に縮小し、要素の多重度の正の整数カウントを保持します。

セットと同様に、マルチセットもハッシュ テーブルまたはツリーを使用して自然に実装でき、異なるパフォーマンス特性が得られます。

T 型のすべてのバッグの集合は、式 bag T で与えられます。多重集合によって、等しい項目を同一と見なし、単純にそれらを数える場合、多重集合は、入力ドメインから非負の整数 (自然数) への関数として解釈でき、集合の識別をその指示関数で一般化します。場合によっては、この数える意味での多重集合は、Python のように、負の値を許可するように一般化されることがあります。

• C++ の標準テンプレート ライブラリはmultiset、ソートされたマルチセットとソートされていないマルチセットの両方を実装します。ソートされたマルチセットのクラスは、一種の連想コンテナとして提供され、自己バランス型バイナリ検索ツリーを使用してこのマルチセットを実装します。ソートされていないマルチセットのunordered_multisetクラスは、一種の順序なし連想コンテナとして提供され、ハッシュ テーブルを使用してこのマルチセットを実装します。ソートされていないマルチセットは、 C++11の時点で標準です。以前は SGI の STL がhash_multisetクラスを提供していましたが、これがコピーされて最終的に標準化されました。
• Javaの場合、サードパーティのライブラリがマルチセット機能を提供します。
  • Apache Commons Collections は、やなどの実装クラスを含むBagおよびインターフェースを提供します。SortedBagHashBagTreeBag
  • Google Guava は、やMultisetなどのクラスを実装するインターフェースを提供します。HashMultisetTreeMultiset
• Apple は、CocoaNSCountedSetの一部として クラスを提供し、CoreFoundationの一部としておよび型を提供します。CFBagCFMutableBag
• Python の標準ライブラリにはcollections.Counter、多重集合に似た が含まれています。
• SmalltalkBagには、包含テストの述語として同一性または等価性のいずれかを使用するようにインスタンス化できるクラスが含まれています。

マルチセット データ構造が利用できない場合は、回避策として、通常のセットを使用しながら、その項目の等価述語をオーバーライドして、異なるオブジェクトに対して常に「等しくない」を返す (ただし、同じオブジェクトの複数の出現を格納することはできません) か、値を整数の多重度にマッピングする連想配列を使用します(これにより、等しい要素をまったく区別できなくなります)。

バッグに対する一般的な操作:

• contains(B, x): 要素xがバッグBに（少なくとも1回）存在するかどうかを確認します。
• is_sub_bag(B1, B2): バッグB _{1内の各要素が、バッグ}B ₂内で発生する頻度より多くB _{1内で発生しないかどうかをチェックします。B} 1 ⊑ B ₂と表記されることもあります。
• count(B, x):バッグB内で要素xが出現する回数を返します。 B # xと表記されることもあります。
• scaled_by(B, n):自然数 nを与えると、バッグBと同じ要素を含むバッグを返します。ただし、Bでm回出現するすべての要素は、結果のバッグでもn * m回出現します。 n ⊗ Bと表記されることもあります。
• union(B1, B2): バッグB ₁またはバッグB ₂のいずれかに出現する値だけを含むバッグを返します。ただし、結果のバッグ内で値xが出現する回数は( B ₁ # x) + ( _{B 2 # x) に等しくなります。B 1} ⊎ _B 2 と表記されることもあり_ます。

リレーショナル データベースでは、一部の列に単一性制約があるかどうか (これにより候補キーになる) に応じて、テーブルは (数学的な) セットまたは多重セットになります。

SQL では、リレーショナル テーブルから行を選択できます。キーワードをDISTINCT使用して行がすべて異なるように強制するか、選択に主キー (または候補キー) が含まれていない限り、この操作では一般にマルチセットが生成されます。

ANSI SQLでは、キーワードMULTISETを使用してサブクエリをコレクション式に変換できます。

SELECT式1 、式2 ... FROMテーブル名...    

は、別のより一般的なクエリの サブクエリ式として使用できる一般的な選択ですが、

MULTISET ( SELECT式1 、式2 ... FROMテーブル名...)    

サブクエリを、別のクエリで使用したり、適切なコレクション型の列に割り当てたりできる コレクション式に変換します。

• ブルームフィルタ
• 非結合集合
• 集合（数学）