"SortedMultiset" (データ構造)

"SortedMultiset"

メンバが一般式であり，ソートされた順を保つマルチ集合を表す．

詳細

  • ソートされたマルチ集合は，効率的な挿入と削除だけでなく，同じ要素が2回以上現れることができる場合のメンバシップ検定にも役立つ．
  • CreateDataStructure["SortedMultiset"]標準的な順序付けを使う新しい空の"SortedMultiset"を作成する
    CreateDataStructure["SortedMultiset",elems]要素 elems を持つ新しい"SortedMultiset"を作成する
    CreateDataStructure["SortedMultiset",elems,p]指定の要素と順序関数 p を持つ新しい"SortedMultiset"を作成する
    Typed[x,"SortedMultiset"]x に"SortedMultiset"型を与える
  • "SortedMultiset"型のデータ構造には，以下の演算が使える．
  • ds["Cases",elem]elem にマッチするマルチ集合のメンバを返すtime: O(log n)
    ds["Count", elem]elem にマッチする要素の数を返すtime: O(log n)
    ds["Delete",x]x の1つのインスタンスを ds から削除する．x が実際に要素である場合にはTrueを返すtime: O(log n)
    ds["DeleteAll"]ds からすべての要素を削除するtime: O(n)
    ds["DeleteCases",x]x のすべてのインスタンスを ds; から削除する．x が実際に要素である場合にはTrueを返すtime: O(log n)
    ds["Elements"]ds の要素のリストを返すtime: O(n)
    ds["EmptyQ"]ds がメンバを持たない場合はTruetime: O(1)
    ds["Insert",x]x をマルチ集合に加えるtime: O(log n)
    ds["Length"]ds に保存されるメンバの数を返すtime: O(1)
    ds["MemberQ",x]x が ds のメンバである場合はTruetime: O(log n)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する

例題

すべて開くすべて閉じる

例  (3)

新しい"SortedMultiset"は，CreateDataStructureを使って作成できる：

集合に挿入する：

集合には要素が1つ含まれる：

式が保存されているかどうかを検証する：

式が保存されていない場合には，Falseが返される：

要素を集合から削除する．何かが実際に削除された場合には，Trueを返す：

これで集合に含まれる要素は2つになった：

式バージョンの ds を返す：

要素の数を挿入する：

データ構造の可視化を生成することができる：

上からデータがどのようにソートされていて，複数の要素を含むことが分かる．

順序関数をソートされたマルチ集合に与えることができる：

2つの要素を挿入する：

順序関数によると，これらの要素はすべて等しい：

要素を削除する：

スコープ  (1)

情報  (1)

新しい"SortedMultiset"は，CreateDataStructureを使って作成することができる：

データ構造 ds についての情報：

考えられる問題  (1)

集合のメンバシップ  (1)

順序関数が与えられると，これを使って集合のメンバシップが指定される：

順序関数は最初の要素だけを見るので，これはTrueを返す：