WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

"OrderedHashSet" (データ構造)

"OrderedHashSet"

メンバが一般式であり，ハッシュ関数を使ってメンバシップが計算され，メンバを挿入する順序が保存される集合を表す．

詳細

  • 順序付きのハッシュ集合は，効率的な挿入と削除だけでなく，挿入の順序を保存することが重要であるメンバシップの検証に役立つ．
  • CreateDataStructure["OrderedHashSet"]新しい空の"OrderedHashSet"を作成する
    CreateDataStructure["OrderedHashSet",elems]elems を含む新しい"OrderedHashSet"を作成する
    Typed[x,"OrderedHashSet"]x に"OrderedHashSet"型を与える
  • "OrderedHashSet"型のデータ構造には，以下の演算が使える．
  • ds["Complement",list]list に現れる要素を ds から削除するtime: O(n)
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["Delete",x]x を ds から削除する．x が実際に要素である場合にはTrueを返すtime: O(1)
    ds["DeleteAll"]ds からすべての要素を削除するtime: O(n)
    ds["Elements"]ds の要素のリストを返すtime: O(n)
    ds["EmptyQ"]ds が要素を持たない場合はTruetime: O(1)
    ds["Insert",x]x を集合に加え，追加に成功した場合にはTrueを返すtime: O(1)
    ds["Intersection",list]list に現れない要素を ds から削除するtime: O(n)
    ds["Length"]ds に保存される要素の数を返すtime: O(1)
    ds["MemberQ",x]x が ds のメンバである場合はTruetime: O(1)
    ds["Pop"]ds から要素を削除し，それを返すtime: O(1)
    ds["Union",list]list に現れる要素を ds に加えるtime: O(n)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Length[ds]ds の長さ
    Normal[ds]ds を通常の式に変換する

例題

すべて開く すべて閉じる

例  (2)

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

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet"]

集合に挿入する：

Wolfram Language code: ds["Insert", f[1]]

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

Wolfram Language code: ds["Length"]

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

Wolfram Language code: ds["MemberQ", f[1]]

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

Wolfram Language code: ds["MemberQ", f[2]]

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

Wolfram Language code: ds["Delete", f[1]]

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

Wolfram Language code: Normal[ds]

要素は素早く挿入できる：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet"]; Do[ds["Insert", i], {i, 100}]

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

Wolfram Language code: ds["Visualization"]

要素が挿入された順序は保存される：

Wolfram Language code: ds["Elements"]

スコープ  (16)

作成  (2)

空の"OrderedHashSet"を作成する：

Wolfram Language code: CreateDataStructure["OrderedHashSet"]

初期要素を含む"OrderedHashSet"を作成する：

Wolfram Language code: CreateDataStructure["OrderedHashSet", {x, y, z}]

情報  (1)

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

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet"]

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

Wolfram Language code: Information[ds]

演算  (13)

"Complement"  (1)

初期要素を含む"OrderedHashSet"を作成する：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[100]]

もとの"OrderedHashSet"のメンバであるが，与えられたリストのメンバではない要素を含む新しい集合を作成する：

Wolfram Language code: ds1 = ds["Complement", Range[50]]

新しい順序付きのハッシュ集合の要素を確かめる：

Wolfram Language code: ds1["Elements"]

"Copy"  (1)

初期要素を含む"OrderedHashSet"を作成する：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[4]]

集合のコピーを得る：

Wolfram Language code: ds1 = ds["Copy"]

両方の配列のコンテンツは同じである：

Wolfram Language code: {Normal[ds], Normal[ds1]}

コピーを変更しても，もとの集合には影響しない：

Wolfram Language code: ds1["Insert", 42]; {Normal[ds], Normal[ds1]}

"Elements"  (1)

初期要素を含む"OrderedHashSet"を作成する：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[10]]

コンテンツをリストとして得る：

Wolfram Language code: ds["Elements"]

Normalは同じリストを返す：

Wolfram Language code: Normal[ds]

"EmptyQ"  (1)

"OrderedHashSet" が空かどうかをテストする：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet"]; ds["EmptyQ"]

要素を挿入した後は，集合はもはや空ではない：

Wolfram Language code: ds["Insert", f[x]]; ds["EmptyQ"]

"Delete"  (1)

"OrderedHashSet"から要素を削除し，削除が成功した場合にはTrueを返す：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", {f[x], f[y], f[z]}]; ds["Delete", f[x]]

集合いない要素を削除することは不可能であるので，Falseが返される：

Wolfram Language code: ds["Delete", f[w]]

"DeleteAll"  (1)

"OrderedHashSet"内のすべての要素を削除する：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[300]]; ds["DeleteAll"]

集合は空になった：

Wolfram Language code: ds["EmptyQ"]

"Insert"  (1)

"OrderedHashSet"に要素を挿入し，挿入に成功した場合にはTrueを返す：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet"]; ds["Insert", f[x]]

同じ要素をもう一度挿入することはできないので，Falseが返される：

Wolfram Language code: ds["Insert", f[x]]

"Intersection"  (1)

初期要素を含む"OrderedHashSet"を作成する：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[100]]

もとの"OrderedHashSet"と指定されたリストに共通の要素のみを含む新しい集合を作成する：

Wolfram Language code: ds1 = ds["Intersection", Range[50]]

新しい順序付きのハッシュ集合の要素を確かめる：

Wolfram Language code: ds1["Elements"]

"Length"  (1)

初期要素を含む"OrderedHashSet"を作成する：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[100]]

集合内の要素数を得る：

Wolfram Language code: ds["Length"]

Lengthは同じ値を与える：

Wolfram Language code: Length[ds]

"MemberQ"  (1)

ある要素が"OrderedHashSet"内に存在するかどうかをテストする：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", {f[x], f[y], f[z]}]
Wolfram Language code: {ds["MemberQ", f[x]], ds["MemberQ", f[w]]}

"Pop"  (1)

初期要素を含む"OrderedHashSet"を作成する：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", {f[x], f[y], f[z]}]; ds["Elements"]

集合から要素を削除する：

Wolfram Language code: ds["Pop"]

"Union"  (1)

初期要素を含む"OrderedHashSet"を作成する：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[10]]

もとの"OrderedHashSet"と与えられたリストの両方に存在する要素を含む新しい集合を作成する：

Wolfram Language code: ds1 = ds["Union", Range[10, 20]]

新しいハッシュ集合の要素を確かめる：

Wolfram Language code: ds1["Elements"]

"Visualization"  (1)

初期要素を含む"OrderedHashSet"を作成する：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[300]]

ハッシュ集合のコンテンツを可視化する：

Wolfram Language code: ds["Visualization"]

アプリケーション  (2)

安定した重複  (1)

ランダムな要素のリストを作成する：

Wolfram Language code: list = RandomChoice[{"A", "B", "C", "D"}, 20]

最初に起った順序を維持しながら，リストから重複する要素を削除する：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet"]; ds["Union", list];

集合の要素を得る：

Wolfram Language code: ds["Elements"]

DeleteDuplicatesと比べる：

Wolfram Language code: DeleteDuplicates[list]

順序付きの共通要素  (1)

2つのコレクションの共通要素を，1つ目の順序を維持しながら求める：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", {a, b, c, d, e}]; ds["Intersection", {e, c, a, f}]//Normal

特性と関係  (5)

InputForm  (1)

InputFormは，"OrderedHashSet"の連続番号付きのコンテンツを返す：

Wolfram Language code: InputForm[CreateDataStructure["OrderedHashSet", Range[10]]]

この連続番号付きの形式を使ってデータ構造を再作成することができる：

Wolfram Language code: DataStructure["OrderedHashSet", {"Data" -> Range[10]}]

Length  (1)

Lengthを使って，"OrderedHashSet"内の要素数を得る：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[10]]; Length[ds]

"Length"演算を使っても同じものが得られる：

Wolfram Language code: ds["Length"]

Normal  (1)

Normalを使って"OrderedHashSet"の要素を得ることができる：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Range[10]]; Normal[ds]

"Elements"演算でも同じものが得られる：

Wolfram Language code: ds["Elements"]

SameQ  (1)

SameQを使って，2つのハッシュ集合に同一の要素が同じ順序で含まれているかどうかをテストする：

Wolfram Language code: ds1 = CreateDataStructure["OrderedHashSet", Range[10]]; ds2 = CreateDataStructure["OrderedHashSet", Range[10]]; ds1 === ds2

"HashSet"  (1)

"HashSet"に使えるアルゴリズムの多くは，"OrderedHashSet"にも使える．

"HashSet"の場合とは違って，要素が"OrderedHashSet"に挿入される順序は保存される．

おもしろい例題  (1)

最初の整数の約数の順序付き集合を作成する：

Wolfram Language code: ds = CreateDataStructure["OrderedHashSet", Divisors[45]]

2つ目の整数の約数と交差させることによって，2つの整数の公約数を求める：

Wolfram Language code: ds["Intersection", Divisors[78]]//Normal

最大公約数を最終要素として抽出する：

Wolfram Language code: Last[%]

組込み関数を使って，結果を確かめる：

Wolfram Language code: GCD[45, 78]