セット（抽象データ型）

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

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

多重集合とは、ある要素が集合内に複数回出現する特殊な集合のことである。

型理論

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

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(x₁,x₂,…,x_n,): 値x ₁、x ₂、...、x _nを持つセット構造を作成します。
create_from(collection): 指定されたコレクションのすべての要素、または指定されたイテレータによって返されるすべての要素を含む新しいセット構造を作成します。

動的セット

動的な集合構造は通常、以下を追加します。

create(): 最初は空の新しい集合構造を作成します。
- create_with_capacity(n): 新しいセット構造を作成します。最初は空ですが、最大n個の要素を保持できます。
add(S,x): 要素x が S にまだ存在しない場合、要素xをSに追加します。
remove(S, x): 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(A₀,F,S):集合 Sの各要素eに対して、ある二項演算Fを適用した後の値A _{| S |を返します。この演算が正しく定義されるためには、}F は結合法則と交換法則を満たしている必要があります。A_i+1 := F(A_i, e)
clear(S)Sのすべての要素を削除します。
equal(S₁', S₂'): 与えられた 2 つのセットが等しいかどうか (つまり、すべての要素が同じかどうか) をチェックします。
hash(S):静的セットSのハッシュ値を返します。equal(S₁, S₂)hash(S₁) = hash(S₂)

特殊な型の要素を持つ集合に対しては、他の演算を定義することもできます。

sum(S): 何らかの「合計」の定義に基づいて、 Sのすべての要素の合計を返します。たとえば、整数または実数では、次のように定義できます。fold(0, add, S)
collapse(S): 集合のセットが与えられた場合、その和集合を返します。^{[ 6 ]}例えば、collapse({{1}, {2, 3}}) == {1, 2, 3}。は、の一種と考えることができますsum。
flatten(S): セットと原子要素 (セットではない要素) からなるセットが与えられた場合、元のトップレベルセットの原子要素、またはそれに含まれるセットの要素を要素とするセットを返します。言い換えれば、ネストのレベルを 1 つ削除します。と同様ですcollapse,が、原子を許可します。これは 1 回だけ実行することも、再帰的に平坦化して原子要素のみのセットを取得することもできます。^{[ 7 ]}例えば、flatten({1, {2, 3}}) == {1, 2, 3}。
nearest(S,x):何らかの指標に基づいて、 xの値に最も近いSの要素を返します。
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であるハッシュに変換してセットとして使用する方法があります。

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

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

popブール集合演算は、より基本的な演算（、、clearおよび）で実装できますaddが、特殊なアルゴリズムを使用すると、漸近的な時間制限が低くなる場合があります。たとえば、集合をソート済みリストとして実装する場合、の単純なアルゴリズムでは、Sの長さmとTの長さnの積に比例する時間がかかりますが、リストマージアルゴリズムの変種では、m + nに比例する時間で処理できます。さらに、これらの演算の 1 つ以上に最適化され、他の演算が犠牲になる特殊な集合データ構造（ユニオンファインドデータ構造など）も存在します。union(S,T)

言語サポート

セットをサポートした初期の言語の一つは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、NSMutableSet、NSCountedSet、NSOrderedSet、を提供しますNSMutableOrderedSet。CoreFoundation APIは、 Cで使用するためのCFSetおよびCFMutableSet型を提供します。
Python には 2.4 以降、組み込みのsetとfrozenset型があり、Python 3.0 および 2.7 以降では、波括弧構文を使用して空でないセットリテラルをサポートしています。例: {x, y, z}; 空のセットはを使用して作成する必要がありますset()。これは、Python が{}空の辞書を表すためにを使用するためです。
.NET Frameworkは、汎用インターフェースを実装する汎用クラスHashSetと汎用クラスを提供します。SortedSetISet
Smalltalkのクラスライブラリには、それぞれ等価性と同一性を使用して包含テストを行うとSetが含まれています。多くの方言では、圧縮ストレージ ( 、)、順序付け ( 、、など)、または弱い参照( )のためIdentitySetのバリエーションが提供されています。NumberSetCharacterSetOrderedSetSortedSetWeakIdentitySet
Rubyの標準ライブラリには、ハッシュテーブルを使用してセットを実装するクラスをset含むモジュールが含まれており、後者はソートされた順序での反復処理を可能にします。SetSortedSet
OCamlの標準ライブラリにはSet、二分探索木を用いて関数型集合データ構造を実装するモジュールが含まれています。
GHCの Haskell 実装には、二分探索木を使用して不変セットを実装するモジュールが用意されていますData.Set。^{[ 9 ]}
Tclの Tcllibパッケージは、TCLリストに基づいたセットデータ構造を実装するセットモジュールを提供します。
Swift標準ライブラリには、Swift 1.2 以降、型が含まれていますSet。
JavaScriptは、ECMAScript 2015 ^[¹⁰^]Set標準で標準組み込みオブジェクトとして導入されました。
Erlangの標準ライブラリにはsetsモジュールがあります。
Clojureにはハッシュセットのためのリテラル構文があり、ソート済みセットも実装されています。
LabVIEWはバージョン2019以降、セットをネイティブでサポートしています。
AdaはAda.Containers.Hashed_Sets、およびパッケージを提供しますAda.Containers.Ordered_Sets。

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

マルチセット

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

コンピュータサイエンスにおいては、ある同値関係の下ではオブジェクトが「等しい」とみなされても、別の関係の下では依然として異なるとみなされる可能性がある。マルチセットの実装によっては、異なる等しいオブジェクトをデータ構造内の別々の項目として格納するものもあれば、最初に見つかったもの（1つのバージョン）に集約し、要素の多重度を正の整数でカウントするものもある。

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

型 T 上のすべてのバッグの集合は、式 bag T で表されます。マルチセットが等しい項目を同一とみなし、単純に数を数える場合、マルチセットは入力ドメインから非負整数 (自然数) への関数として解釈でき、セットとその指示関数の同一視を一般化します。場合によっては、この計数的な意味でのマルチセットは、Python のように負の値を許容するように一般化されることがあります。

C++ の標準テンプレートライブラリ (STL)は、ソート済みマルチセットとソートされていないマルチセットの両方を実装しています。multisetソート済みマルチセット用のクラスは、一種の連想コンテナとして提供され、自己平衡二分探索木を使用してマルチセットを実装します。unordered_multisetソートされていないマルチセット用のクラスは、一種の順序なし連想コンテナとして提供され、ハッシュテーブルを使用してマルチセットを実装します。ソートされていないマルチセットはC++11以降標準となっています。それ以前は SGI の STL がhash_multisetクラスを提供していましたが、それがコピーされ、最終的に標準化されました。
Javaの場合、サードパーティライブラリがマルチセット機能を提供します。
- Apache Commons Collections はBag、やSortedBagなどの実装クラスを備えたインターフェースを提供します。HashBagTreeBag
- Google Guava は、やMultisetなどのクラスを実装したインターフェースを提供します。HashMultisetTreeMultiset
Apple はCocoaNSCountedSetの一部としてクラスを提供し、CoreFoundationの一部として型と型を提供します。CFBagCFMutableBag
Pythonの標準ライブラリにはcollections.Counter、マルチセットに似たものが含まれています。
SmalltalkにBagは、包含テストの述語として同一性または等価性のいずれかを使用するようにインスタンス化できるクラスが含まれています。

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

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

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

SQLにおけるマルチセット

リレーショナルデータベースでは、テーブルは、一部の列に一意性制約が存在するかどうかに応じて、（数学的な）集合または多重集合になります（これにより、テーブルは候補キーになります）。

SQLでは、リレーショナルテーブルから行を選択できます。この操作は、一般的にはマルチセットを生成しますが、キーワードをDISTINCT使用して行をすべて異なるものに強制したり、選択に主キー（または候補キー）を含めたりした場合は例外です。

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

SELECT expression1 , expression2 ... FROM table_name ...

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

MULTISET ( SELECT expression1 , expression2 ... FROM table_name ...)

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

注記

↑
例えば、Python では、pick組み込み関数の派生クラスでset次のように実装できます。
```
class Set ( set ): def pick ( self ): return next ( iter ( self ))
```
↑要素の挿入は、単純に末尾に挿入すればO (1)の時間で実行できますが、重複を避ける場合はO ( n )の時間が必要になります。

参考文献

↑ Python: pop()
↑複雑なデータ構造の管理と処理：第3回情報システムと人工知能ワークショップ、ドイツ、ハンブルク、1994年2月28日～3月2日。議事録、編集：Kai v. Luck、Heinz Marburger、 p. 76
↑ Python Issue7212 : セットから任意の要素を削除せずに取得する。標準名についてはmsg106593 を参照。
↑ Ruby機能 #4553 : Set#pick と Set#pop を追加
↑関数型プログラムの帰納的合成：普遍的計画、有限プログラムの折り畳み、類推的推論によるスキーマ抽象化、Ute Schmid、Springer、2003年8月21日、 p. 240
↑データ型仕様の最近の動向：第10回抽象データ型仕様ワークショップ（第5回COMPASSワークショップ併催）、イタリア、サンタ・マルゲリータ、1994年5月30日～6月3日。選集、第10巻、 Egidio Astesiano、Gianna Reggio、Andrzej Tarlecki編、 38ページ
↑ Ruby: flatten()
↑ Wang, Thomas (1997), Sorted Linear Hash Table、2006年1月12日にオリジナルからアーカイブ済み
↑ Stephen Adams、「効率的なセット：バランスの取り方」、Journal of Functional Programming 3(4):553-562、1993年10月。2015年3月11日に取得。
↑ 「ECMAScript 2015 言語仕様 – ECMA-262 第 6 版」。www.ecma -international.org。2017年 7 月 11 日に取得。

[6] 例えば、Python では、pick組み込み関数の派生クラスでset次のように実装できます。
class Set ( set ): def pick ( self ): return next ( iter ( self ))

[9] 要素の挿入は、単純に末尾に挿入すればO (1)の時間で実行できますが、重複を避ける場合はO ( n )の時間が必要になります。

[1] Python: pop()

[2] 複雑なデータ構造の管理と処理：第3回情報システムと人工知能ワークショップ、ドイツ、ハンブルク、1994年2月28日～3月2日。議事録、編集：Kai v. Luck、Heinz Marburger、 p. 76

[3] Python Issue7212 : セットから任意の要素を削除せずに取得する。標準名についてはmsg106593 を参照。

[4] Ruby機能 #4553 : Set#pick と Set#pop を追加

[5] 関数型プログラムの帰納的合成：普遍的計画、有限プログラムの折り畳み、類推的推論によるスキーマ抽象化、Ute Schmid、Springer、2003年8月21日、 p. 240

[7] データ型仕様の最近の動向：第10回抽象データ型仕様ワークショップ（第5回COMPASSワークショップ併催）、イタリア、サンタ・マルゲリータ、1994年5月30日～6月3日。選集、第10巻、 Egidio Astesiano、Gianna Reggio、Andrzej Tarlecki編、 38ページ

[8] Ruby: flatten()

[10] Wang, Thomas (1997), Sorted Linear Hash Table、2006年1月12日にオリジナルからアーカイブ済み

[11] Stephen Adams、「効率的なセット：バランスの取り方」、Journal of Functional Programming 3(4):553-562、1993年10月。2015年3月11日に取得。

[12] 「ECMAScript 2015 言語仕様 – ECMA-262 第 6 版」。www.ecma -international.org。2017年 7 月 11 日に取得。

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ a ]

[ 6 ]

[ 7 ]

[ b ]

[ 8 ]

[ 9 ]

[

セット（抽象データ型）

型理論

業務

コア集合論的演算

静的セット

動的セット

追加手術

実装

言語サポート

マルチセット

SQLにおけるマルチセット

関連項目

注記

参考文献

関連するトピック

コンピュータサイエンス

順序

抽象的なデータ型

、有限集合という