セット(抽象データ型)

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

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

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

マルチセットは、要素が数回計算できる特殊な種類のセットです。

型理論

型理論では、集合は一般にそのインジケーター関数(特性関数)で識別されます。したがって、型の値の集合で表すことができますまた(サブタイプとサブセットは詳細化タイプでモデル化でき、商集合はsetoidで置き換えることができます。)特性関数セットのと定義されている:

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

操作

コア集合論的操作

集合の代数の演算を定義することができます

  • union(S,T):集合STの集合を返します
  • intersection(S,T):セットSTの共通部分を返します
  • difference(S,T):セットSTのを返します
  • 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 1x 2、...、xnでセット構造を作成します
  • create_from(collection):指定されたコレクションのすべての要素または指定されたイテレータによって返されるすべての要素を含む新しいセット構造を作成します

動的セット

動的セット構造は通常、以下を追加します。

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

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

追加操作

上記の観点から(原則として)定義できる操作は他にもたくさんあります。たとえば、次のようなものです。

  • pop(S): Sの任意の要素を返し、Sから削除します。[1]
  • pick(S): Sの任意の要素を返します[2] [3] [4]機能的には、ミューテーターは、任意の要素を除くすべての要素で構成されるセットを返すセレクターpopのペアとして解釈できます。[5]の観点から解釈することができます[a](pick, rest),restiterate
  • map(F,S):関数FをSの各要素に適用した結果の個別の値のセットを返します
  • filter(P,S):指定された述語Pを満たすSのすべての要素を含むサブセットを返します
  • fold(A0,F,S):値Aを返します| S | Sの各要素e適用した後、いくつかの二項演算F. 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): 「sum」の定義について、 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): xに値が最も近いSの要素を返しますメトリックによって)。
  • min(S)、 : Sの最小/最大要素を返しますmax(S)

実装

セットは、さまざまなデータ構造を使用して実装できます。これにより、さまざまな操作に対してさまざまな時間と空間のトレードオフが提供されます。一部の実装は、やなどの非常に特殊な操作の効率を向上させるように設計されていnearestますunion「一般的な使用」と呼ばれる実装は、通常、、、および操作を最適element_of化するように努めます。簡単な実装は、要素の順序を無視し、値が繰り返されないように注意しながら、リストを使用することです。これは単純ですが、リスト全体をスキャンする必要があるため、メンバーシップの設定や要素の削除などの操作はOn )であるため、非効率的です。[b]adddelete代わりに、セットは、より効率的なデータ構造、特にさまざまな種類のツリー試行、またはハッシュテーブルを使用して実装されることがよくあります。

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

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

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

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

ブール集合演算は、より基本的な演算(、、、および)の観点から実装できますpopclearadd特殊なアルゴリズムでは、漸近的な時間範囲が低くなる可能性があります。たとえば、セットがソートされたリストとして実装されている場合、の単純なアルゴリズムは、 Sの長さmTの長さn掛けたものに比例する時間がかかります。一方、リストマージアルゴリズムの変形は、 m + nに比例する時間で仕事をします。さらに、他の操作を犠牲にして、これらの操作の1つ以上に最適化され た特殊なセットデータ構造(union-findデータ構造など)があります。union(S,T)

言語サポート

セットをサポートする最も初期の言語の1つはPascalでした。現在、コア言語であろうと標準ライブラリであろうと、多くの言語に含まれています。

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

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

マルチセット

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

正式には、コンピュータサイエンスのオブジェクトは、ある同値関係では「等しい」と見なされる可能性がありますが、別の関係では依然として区別されます。一部のタイプのマルチセット実装は、データ構造内の個別のアイテムとして別個の等しいオブジェクトを格納します。他の人はそれを1つのバージョン(最初に遭遇したバージョン)に折りたたみ、要素の多重度の正の整数カウントを保持します。

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

タイプTのすべてのバッグのセットは、式bag Tによって与えられます。マルチセットによって、等しいアイテムを同一と見なし、それらを単純にカウントする場合、マルチセットは、入力ドメインから非負の整数(自然数)への関数として解釈できます。番号)、そのインジケーター機能でセットの識別を一般化します。場合によっては、Pythonのように、このカウントの意味でのマルチセットを一般化して負の値を許可することができます。

  • C ++の標準テンプレートライブラリは、並べ替えられたマルチセットと並べ替えられていないマルチセットの両方を実装します。multisetソートされたマルチセットのクラスを一種の連想コンテナとして提供し、自己平衡二分探索木を使用してこのマルチセットを実装しますこれは、ハッシュテーブルを使用してこのマルチセットを実装する一種の順序付けされていない連想コンテナunordered_multisetとして、ソートされていないマルチセットのクラスを提供しますソートされていないマルチセットは、C ++ 11の時点で標準です。以前は、SGIのSTLがクラスを提供していましたが、これはコピーされ、最終的には標準化されました。hash_multiset
  • Javaの場合、サードパーティライブラリはマルチセット機能を提供します。
  • Appleは、CocoaNSCountedSet一部としてクラスを提供し、 CoreFoundationの一部としておよびタイプを提供しますCFBagCFMutableBag
  • Pythonの標準ライブラリにはcollections.Counter、マルチセットに似たが含まれています。
  • SmalltalkにはBagクラスが含まれており、包含テストの述語として同一性または同等性のいずれかを使用するようにインスタンス化できます。

マルチセットデータ構造が利用できない場合、回避策は通常のセットを使用することですが、そのアイテムの等式述語をオーバーライドして、個別のオブジェクトで常に「等しくない」を返します(ただし、そのようなものは、同じオブジェクト)または、値を整数の多重度にマッピングする連想配列を使用します(これにより、等しい要素をまったく区別できなくなります)。

バッグの典型的な操作:

  • contains(B, x):要素xがバッグBに(少なくとも1回)存在するかどうかをチェックします
  • is_sub_bag(B1, B2):バッグB1の各要素がバッグB2で発生する頻度よりもB1で発生する頻度が低いかどうかをチェックしますB1⊑B2表記されることあります
  • count(B, x):要素xがバッグBで発生する回数を返します; Bxと表記されることもあります。
  • scaled_by(B, n)自然数 nが与えられると、バッグBと同じ要素を含むバッグを返します。ただし、 Bでm発生するすべての要素は、結果のバッグでn * m回発生します。n⊗Bと表記されることもあります
  • union(B1, B2):結果のバッグで値xが発生する回数が( B 1#x)+(B 2 )に等しい場合を除いて、バッグB1またはバッグB2のいずれかで発生する値のみを含むバッグを返します。バツ); B1⊎B2表記されることあります

SQLのマルチセット

リレーショナルデータベースでは、一部の列にユニシティ制約が存在するかどうかに応じて、テーブルを(数学的な)セットまたはマルチセットにすることができます(これにより、テーブルが候補キーになります)。

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

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

SELECT  expression1  expression2 ...  FROM  table_name ..。

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

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

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

も参照してください

メモ

  1. ^ たとえば、Pythonでは、次 pickに組み込みの派生クラスに実装できset
    class  Set set ):
        def  pick self ):
            return  next iter self ))
    
  2. ^ 要素の挿入は、最後に挿入するだけでO(1)時間で実行できますが、重複を避ける場合は、 O n)時間かかります。

参考文献

  1. ^ Python: pop()
  2. ^ 複雑なデータ構造の管理と処理:情報システムと人工知能に関する第3回ワークショップ、ドイツ、ハンブルク、1994年2月28日から3月2日。Proceedings、 ed。Kaiv。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
  6. ^ データ型仕様の最近の傾向:第5回COMPASSワークショップと共同で、抽象データ型の仕様に関する第10回ワークショップ、S。Margherita、イタリア、1994年5月30日から6月3日。SelectedPapers、Volume 10、 ed。Egidio Astesiano、Gianna Reggio、Andrzej Tarlecki、 p。38
  7. ^ Ruby: flatten()
  8. ^ Wang、Thomas(1997)、Sorted Linear Hash Table 、 2006-01-12のオリジナルからアーカイブ
  9. ^ Stephen Adams、効率的なセット:バランスをとる行為、Journal of Functional Programming 3(4):553-562、1993年10月。2015年3月11日に取得。
  10. ^ 「ECMAScript2015言語仕様–ECMA-262第6版」www.ecma-international.org 2017年7月11日取得