WOLFRAM

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

"HashSet" (データ構造)

"HashSet"

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

詳細

  • ハッシュ集合は，一意的な要素の集合を整理するのに役立ち，メンバシップの非常に効率的な検証，挿入，削除を行うことができる．
  • CreateDataStructure["HashSet"]新しい空の"HashSet"を作成する
    CreateDataStructure["HashSet",elems]elems を含む新しい"HashSet"を作成する
    Typed[x,"HashSet"]x に"HashSet"型を与える
  • "HashSet"型のデータ構造には，以下の演算が使える．
  • ds["Complement",list]list に現れる要素を ds から削除するtime: O(n)
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["Elements"]x を ds から削除し，x が実際に要素である場合にTrueを返すtime: O(n)
    ds["EmptyQ"]ds からすべての要素を削除するtime: O(1)
    ds["Delete",x]ds の要素のリストを返すtime: O(1)
    ds["DeleteAll"]ds が要素を持たない場合はTruetime: O(n)
    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["SubsetQ",ds1]ハッシュ集合 ds1が ds の部分集合である場合にはTrueを返すtime: O(n)
    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)

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

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

集合に挿入する：

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["HashSet"]; Do[ds["Insert", i], {i, 1000}]

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

Wolfram Language code: ds["Visualization"]

スコープ  (17)

情報  (1)

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

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

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

Wolfram Language code: Information[ds]

作成  (2)

空の"HashSet"を作成する：

Wolfram Language code: CreateDataStructure["HashSet"]

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

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

演算  (14)

"Complement"  (1)

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

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

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

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

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

Wolfram Language code: ds1["Elements"]

"Copy"  (1)

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

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

集合のコピーを得る：

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

2つの配列のコンテンツは同じである：

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

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

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

"Elements"  (1)

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

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

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

Wolfram Language code: ds["Elements"]

Normalは同じリストを返す：

Wolfram Language code: Normal[ds]

"EmptyQ"  (1)

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

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

要素を挿入をすると，集合はもはや空ではない：

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

"Delete"  (1)

"HashSet"から要素を削除し，削除がうまくいった場合にはTrueを返す：

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

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

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

"DeleteAll"  (1)

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

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

集合は空になった：

Wolfram Language code: ds["EmptyQ"]

"Insert"  (1)

"HashSet"に要素を挿入し，挿入がうまくいったらTrueを返す：

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

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

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

"Intersection"  (1)

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

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

もとの"HashSet"と与えられたリストに共通する要素のみを含む新しい集合を作成する：

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

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

Wolfram Language code: ds1["Elements"]

"Length"  (1)

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

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

集合内の要素数を得る：

Wolfram Language code: ds["Length"]

Lengthは同じ値を返す：

Wolfram Language code: Length[ds]

"MemberQ"  (1)

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

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

"Pop"  (1)

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

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

集合の要素を削除する：

Wolfram Language code: ds["Pop"]

"SubsetQ"  (1)

1つの集合に含まれる要素がすべて別の集合に含まれるかどうかをテストする：

Wolfram Language code: ds1 = CreateDataStructure["HashSet", {1, 3, 5}]; ds2 = CreateDataStructure["HashSet", {1, 2, 3, 4, 5}]; ds1["SubsetQ", ds2]

小さい集合が大きい集合の部分集合であるかどうかをチェックする：

Wolfram Language code: ds2["SubsetQ", ds1]

"Union"  (1)

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

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

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

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

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

Wolfram Language code: ds1["Elements"]

"Visualization"  (1)

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

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

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

Wolfram Language code: ds["Visualization"]

アプリケーション  (2)

文字列集合  (1)

組込みの集合の演算は，機械数字の矩形配列を使う場合に便利である．データ構造の演算は，文字列等の数字ではないデータの集合に役立つ．1000000個の文字列のリストを作成する：

Wolfram Language code: list1 = Table[ StringJoin[RandomChoice[ {"A", "B", "C"}, 4]], 1000000];
Wolfram Language code: ds = CreateDataStructure["HashSet"]; ds["Union", list1];//AbsoluteTiming
Wolfram Language code: Union[list1];//AbsoluteTiming

"Complement"が役に立つことを示す同様の例：

Wolfram Language code: list1 = Table[ StringJoin[ RandomChoice[ {"A", "B", "C"}, 10]], 100000]; listC = Table[ StringJoin[{"A", RandomChoice[ {"A", "B", "C"}, 9]}], 50];
Wolfram Language code: ds = CreateDataStructure["HashSet"]; ds["Union", list1];//AbsoluteTiming
Wolfram Language code: listI = Union[list1];//AbsoluteTiming
Wolfram Language code: ds["Complement", listC];//AbsoluteTiming
Wolfram Language code: Complement[listI, listC];//AbsoluteTiming

グラフ閉路の検知  (1)

"HashSet"を使って有向グラフに閉路が含まれるかどうかを検知して，深さ優先探索走査中に訪れたノードを追跡する：

Wolfram Language code: hasCycle[graph_ ? GraphQ] := Module[{ visited = CreateDataStructure["HashSet"], recursionStack = CreateDataStructure["HashSet"], dfs}, dfs[node_] := If[!visited["MemberQ", node], visited["Insert", node]; recursionStack["Insert", node]; Do[ If[recursionStack["MemberQ", neighbor], Return[True, Module] , dfs[neighbor] ], {neighbor, VertexOutComponent[graph, node, {1}]} ]; recursionStack["Delete", node]; ]; Scan[dfs, VertexList[graph]]; False ]

以下のグラフが自己閉路を持たないグラフであるかどうかをチェックする：

Wolfram Language code: hasCycle /@ {[image], [image], [image]}

特性と関係  (5)

InputForm  (1)

InputFormは，"HashSet"の通し番号が付けられたコンテンツを返す：

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

この通し番号付きの形式は，データ構造を再度作成するために使える：

Wolfram Language code: DataStructure["HashSet", {"Data" -> {3, 4, 2, 1, 7, 6, 10, 9, 5, 8}}]

Length  (1)

Lengthは，"HashSet"内の要素数を得るために使える：

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

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

Wolfram Language code: ds["Length"]

Normal  (1)

Normalは，"HashSet"の要素を得るために使える：

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

"Elements"演算を使っても同じ結果が得られる：

Wolfram Language code: ds["Elements"]

SameQ  (1)

SameQを使って，2つのハッシュ集合が順序は関係なく，同一の要素を含むかどうかをテストすることができる：

Wolfram Language code: ds1 = CreateDataStructure["HashSet", Range[10]]; ds2 = CreateDataStructure["HashSet", Reverse@Range[10]]; ds1 === ds2

要素の1つが削除されると，2つの集合は同じではなくなる：

Wolfram Language code: ds1["Pop"]; ds1 === ds2

"OrderedHashSet"  (1)

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

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

おもしろい例題  (1)

最大公約数の計算  (1)

2つの約数集合の共通集合を求めると，最大のものが求めやすくなる：

Wolfram Language code: ds = CreateDataStructure["HashSet", Divisors[45]]; ds["Intersection", Divisors[78]]//Normal

最大の結果は3である：

Wolfram Language code: Max[%]

これは最大公約数に等しい：

Wolfram Language code: GCD[45, 78]