WOLFRAM

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

"DynamicArray" (データ構造)

"DynamicArray"

要素が一般式である拡張可能配列を表す．

詳細

  • 拡張可能配列は，連続的に要素を加えるためだけでなく，要素を効率的に抽出および更新するために役立つ．
  • CreateDataStructure["DynamicArray"]新しい空の"DynamicArray"を作成する
    CreateDataStructure["DynamicArray",elems]elems を含む新しい"DynamicArray"を作成する
    Typed[x,"DynamicArray"]x に"DynamicArray"型を与える
  • "DynamicArray"型のデータ構造には，以下の演算が使える．
  • ds["Append",x]x を ds に加えるtime: O(1)
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["Drop",i]ds の i 番目の部分を省くtime: O(n)
    ds["DropAll"]ds からすべての要素を省くtime: O(n)
    ds["DropLast"]ds の最後の要素を省くtime: O(1)
    ds["Elements"]ds の要素のリストを返すtime: O(n)
    ds["EmptyQ"]ds が要素を持たない場合はTruetime: O(1)
    		ds["Fold",fun]fun を ds の要素に適用し，結果を累積するtime: O(n)
    ds["Fold",fun,init]fun を ds の要素に適用する．init で始めて，結果を累積するtime: O(n)
    ds["Insert",x,i ]x を ds の位置 i に挿入するtime: O(1)
    ds["JoinBack",elems ]elems を ds の後ろに繋げるtime: O(nelems)
    ds["Length"]ds に保存される要素の数time: O(1)
    ds["Part",i]ds の i 番目の部分を返すtime: O(1)
    ds["SetPart",i,elem]ds の i 番目の部分を更新するtime: O(1)
    ds["SwapPart",i,j]ds の i 番目と j 番目の部分を交換するtime: O(1)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    ds["Part",i]=valds の i 番目の要素を val に設定する
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Length[ds]配列の長さ
    Normal[ds]ds を通常の式に変換する

例題

すべて開く すべて閉じる

例  (2)

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

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

要素は加えることができる：

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

長さを返す：

Wolfram Language code: ds["Length"]

最初の要素を抽出する：

Wolfram Language code: ds["Part", 1]

要素を変更する：

Wolfram Language code: ds["Part", 1] = f[2]

要素が更新された：

Wolfram Language code: ds["Part", 1]

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

Wolfram Language code: Normal[ds]

素早く加えることができる：

Wolfram Language code: ds = CreateDataStructure["DynamicArray"]; Do[ds["Append", i], {i, 1000}]

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

Wolfram Language code: ds["Visualization"]

全要素を合計する：

Wolfram Language code: ds["Fold", Plus, 0]

スコープ  (18)

情報  (1)

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

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

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

Wolfram Language code: Information[ds]

作成  (2)

空の"DynamicArray"を作成する：

Wolfram Language code: CreateDataStructure["DynamicArray"]

初期値を含む"DynamicArray"を作成する：

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

演算  (15)

"Append"  (1)

要素を"DynamicArray"に加える：

Wolfram Language code: ds = CreateDataStructure["DynamicArray"]; ds["Append", f[x, y]]

配列のコンテンツを得る：

Wolfram Language code: Normal[ds]

"Copy"  (1)

初期値を含む"DynamicArray"を作成する：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {1, 2, 3}]

配列のコピーを得る：

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

2つの配列のコンテンツは等しい：

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

コピーを変更しても，もとの配列には影響を与えない：

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

"Drop"  (1)

初期値を含む"DynamicArray"を作成する：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]; ds["Visualization"]

配列の5番目の要素を省く：

Wolfram Language code: ds["Drop", 5]

もう一度配列を可視化する：

Wolfram Language code: ds["Visualization"]

"DropAll"  (1)

"DynamicArray"を作成する：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]; ds["Visualization"]

配列のすべての要素を省く：

Wolfram Language code: ds["DropAll"]

配列は空になった：

Wolfram Language code: Length[ds]

"DropLast"  (1)

初期値を含む"DynamicArray"を作成する：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]; ds["Visualization"]

最後の要素を省き，省いた値を得る：

Wolfram Language code: ds["DropLast"]

配列を可視化する：

Wolfram Language code: ds["Visualization"]

"Elements"  (1)

初期値を含む"DynamicArray"を作成する：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[10]]; ds["Visualization"]

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

Wolfram Language code: ds["Elements"]

Normalは同じリストを返す：

Wolfram Language code: Normal[ds]

"EmptyQ"  (1)

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

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

要素を加えた後は，配列はもはや空ではない：

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

"Fold"  (1)

初期値を含む"DynamicArray"を作成する：

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

Plusを使って配列の全要素を結合し，その合計を得る：

Wolfram Language code: ds["Fold", Plus]

累計を始める初期値を指定することも可能である：

Wolfram Language code: ds["Fold", Plus, 42]

"Insert"  (1)

初期値を含む"DynamicArray"を作成する：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[8]]

要素を指定の場所に挿入する：

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

配列のコンテンツを可視化する：

Wolfram Language code: ds["Visualization"]

"JoinBack"  (1)

初期値を含む"DynamicArray"を作成する：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[5]]

複数の要素を配列の最後に追加する：

Wolfram Language code: ds["JoinBack", Range[6, 10]]

配列を可視化する：

Wolfram Language code: ds["Visualization"]

"Length"  (1)

初期値を含む"DynamicArray"を作成する：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Range[5]]

配列中の要素の数を得る：

Wolfram Language code: ds["Length"]

Lengthは同じ値を返す：

Wolfram Language code: Length[ds]

"Part"  (1)

初期値を含む"DynamicArray"を作成する：

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

配列の5番目の要素を得る：

Wolfram Language code: ds["Part", 5]

"SetPart"  (1)

初期値を含む"DynamicArray"を作成する：

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

配列の5番目の要素を別の値に設定する：

Wolfram Language code: ds["SetPart", 5, x]

配列を可視化する：

Wolfram Language code: ds["Visualization"]

以下のシンタックスうも有効である：

Wolfram Language code: ds["Part", 6] = y; ds["Visualization"]

"SwapPart"  (1)

初期値を含む"DynamicArray"を作成する：

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

5番目と6番目の位置にある要素の値を交換する：

Wolfram Language code: ds["SwapPart", 5, 6]

配列を可視化する：

Wolfram Language code: ds["Visualization"]

"Visualization"  (1)

初期値を含む"DynamicArray"を作成する：

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

配列のコンテンツを可視化する：

Wolfram Language code: ds["Visualization"]

アプリケーション  (11)

逆配列  (1)

"DynamicArray"をインプレースで逆順にする簡単な関数：

Wolfram Language code: ArrayReverse[ ds : DataStructure["DynamicArray", _]] := Module[{start = 0, end = ds["Length"] + 1}, While[++start < --end, ds["SwapPart", start, end] ]; ds];

使用するサンプルデータ構造：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

要素を逆にする：

Wolfram Language code: Normal[ArrayReverse[ds]]

バブルソート  (1)

バブルソートは，単純なソートアルゴリズムである．コードするのは簡単だが，通常性能は良くない：

Wolfram Language code: BubbleSort[ ds : DataStructure["DynamicArray", _]] := Module[{repeat = True}, While[repeat, repeat = False; Do[ If[ds["Part", i] > ds["Part", i + 1], ds["SwapPart", i, i + 1]; repeat = True];, {i, ds["Length"] - 1}]]; ds];

使用するサンプルデータ構造：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

要素をソートする：

Wolfram Language code: Normal[BubbleSort[ds]]

データ構造はインプレースでソートされる：

Wolfram Language code: Normal[ds]

挿入ソート  (1)

挿入ソートは，単純なソートアルゴリズムである．コードするのは簡単だが，通常性能は大きな配列に対しては良くないが，小さい配列には役立つ：

Wolfram Language code: InsertionSort[ ds : DataStructure["DynamicArray", _]] := Module[{len, i, j}, len = ds["Length"]; Do[j = i; While[j > 1 && ds["Part", j - 1] > ds["Part", j], ds["SwapPart", j, j - 1];j--], {i, 2, len}]; ds]

使用するサンプルデータ構造：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

要素をソートする：

Wolfram Language code: Normal[InsertionSort[ds]]

データ構造はインプレースでソートされる：

Wolfram Language code: Normal[ds]

クイックソート  (1)

クイックソートは，効率的なソートアルゴリズムである．この基本的な実装は，ネストした関数を使う：

Wolfram Language code: Quicksort[ ds : DataStructure["DynamicArray", _]] := Module[{partitionFun, sortFun}, partitionFun = Function[{low, high}, Module[{pivot = ds["Part", high], i = low, j}, Do[ If[ds["Part", j] ≤ pivot, ds["SwapPart", i, j];i = i + 1], {j, low, high - 1}]; ds["SwapPart", i, high]; i]]; sortFun = Function[{low, high}, If[low < high, Module[{p = partitionFun[low, high]}, sortFun[low, p - 1]; sortFun[p + 1, high] ] ]]; sortFun[1, ds["Length"]]; ds]

使用するサンプルデータ構造：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

要素をソートする：

Wolfram Language code: Normal[Quicksort[ds]]

データ構造はインプレースでソートされる：

Wolfram Language code: Normal[ds]

マージソート  (1)

マージソートは，効率的なソートアルゴリズムである．この基本的な実装は，ワークスペースを使う：

Wolfram Language code: MergeSort[ ds : DataStructure["DynamicArray", _]] := MergeSortSplit[ds["Copy"] , 1, ds["Length"] + 1, ds]
Wolfram Language code: MergeSortSplit[ b_, start_, end_, a_] := Module[{mid}, If[end - start > 1, mid = Quotient[end + start, 2]; MergeSortSplit[a, start, mid, b]; MergeSortSplit[a, mid, end, b]; MergeSortJoin[ b, start, mid, end, a] ]; a]
Wolfram Language code: MergeSortJoin[ a_, start_, mid_, end_, b_] := Module[{i = start, j = mid, k}, Do[ If[i < mid && (j ≥ end || a["Part", i] ≤ a["Part", j]), b["Part", k] = a["Part", i];i++, b["Part", k] = a["Part", j];j++], {k, start, end - 1}]; ]

使用するサンプルデータ構造：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

要素をソートする：

Wolfram Language code: Normal[MergeSort[ds]]

データ構造はインプレースでソートされる：

Wolfram Language code: Normal[ds]

ヒープソート  (1)

マージソートは，効率的なソートアルゴリズムであり，ヒープを構築することによってインプレースで使える：

Wolfram Language code: Heapsort[ds : DataStructure["DynamicArray", _]] := Module[{len = ds["Length"]}, Do[Heapify[ds, ii], {ii, Quotient[len, 2], 1, -1}]; ds ]
Wolfram Language code: Heapify[p : DataStructure["DynamicArray", _], k_Integer] := Module[{i = k, l, n = p["Length"]}, While[(l = 2 i) ≤ n, If[(l < n) && (p["Part", l] > p["Part", l + 1]), l++]; If[p["Part", i] > p["Part", l], p["SwapPart", l, i]; i = l, i = n + 1];];]

使用するサンプルデータ構造：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

要素はインプレースでソートされる：

Wolfram Language code: Heapsort[ds]; Normal[ds]

ティムソート  (1)

ティムソートは，ハイブリッドで効率的なソートアルゴリズムである：

Wolfram Language code: Timsort[ds : DataStructure["DynamicArray", _]] := Module[{blockSize = 32, len = ds["Length"], size, mid, right}, Do[InsertionWorker[ds, ii, Min[ii + 32, len]], {ii, 1, len, blockSize}]; size = blockSize; While[size < len, Do[ mid = left + size; right = Min[left + 2 * size, len]; MergeWorker[ds, left, mid, right] , {left, 1, len, 2 * size} ]; size *= 2 ]; ]
Wolfram Language code: InsertionWorker[ ds : DataStructure["DynamicArray", _], left_, right_] := Module[{i, j}, Do[j = i; While[j > left && ds["Part", j - 1] > ds["Part", j], ds["SwapPart", j, j - 1];j--], {i, left, right}]; ds]
Wolfram Language code: MergeWorker[ b_, start_, mid_, end_] := Module[{a, i = start, j = mid, k}, a = b["Copy"]; Do[ If[i < mid && (j ≥ end || a["Part", i] ≤ a["Part", j]), b["Part", k] = a["Part", i];i++, b["Part", k] = a["Part", j];j++], {k, start, end - 1}]; ]

使用するサンプルデータ構造：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

要素はインプレースでソートされる：

Wolfram Language code: Timsort[ds]; Normal[ds]

フィッシャー・イェーツのシャッフル  (1)

フィッシャー・イェーツのシャッフルは，有限数列のランダムな順列を生成する：

Wolfram Language code: FisherYatesShuffle[ ds : DataStructure["DynamicArray", _]] := ( Do[ ds["SwapPart", i, RandomInteger[{1, i}]], {i, ds["Length"] - 1, 1, -1} ]; ds );

シャッフルに使うサンプル配列：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100} ];

シャッフルを適用する：

Wolfram Language code: Normal[FisherYatesShuffle[ds]]

回文配列  (1)

配列は，真ん中の周りで対称である場合には回文配列である：

Wolfram Language code: IsPalindrome[ ds : DataStructure["DynamicArray", _]] := Module[{start = 0, end = ds["Length"] + 1}, While[++start < --end, If[ds["Part", start] =!= ds["Part", end], Return[False] ] ]; True];

これは回文配列ではない：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}]; IsPalindrome[ds]

これは回文配列である：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 2, 9}]; IsPalindrome[ds]

クイックセレクト  (1)

クイックセレクトは，クイックソートアルゴリズムに関連する選択アルゴリズムである．リスト中の k 番目に小さい要素を返す：

Wolfram Language code: Quickselect[ds : DataStructure["DynamicArray", _], k_] := QuickselectWorker[ds, 1, ds["Length"], k];
Wolfram Language code: QuickselectWorker[ds_, low0_, high0_, k_] := Module[{pivotIdx, low = low0, high = high0}, While[True, If[low === high, Return[ds["Part", low]]]; pivotIdx = SelectPartition[ds, low, high]; Which[ k === pivotIdx, Return[ds["Part", k]], k < pivotIdx, high = pivotIdx - 1, True, low = pivotIdx + 1 ] ] ];
Wolfram Language code: SelectPartition[ds_, low_, high_] := Module[{pivot = ds["Part", high], i = low, j}, Do[ If[ds["Part", j] ≤ pivot, ds["SwapPart", i, j];i = i + 1], {j, low, high - 1}]; ds["SwapPart", i, high]; i];

使用するサンプルデータ構造：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", {9, 2, 7, 0}];

3番目に小さい要素は7である：

Wolfram Language code: Quickselect[ds, 3]

ヒープ  (1)

ヒープは，木ベースのデータ構造であり，（最小ヒープについて）子でソートされた値がその親でソートされたものより小さい構造である．優先キューお実装するためによく使われ，通常木ではなく配列で実装される．

以下は配列をヒープに変換する：

Wolfram Language code: MinHeapify[ds : DataStructure["DynamicArray", _]] := MinHeapify[ds, 1]
Wolfram Language code: MinHeapify[ds_, i_] := Module[{l, r, p, smallest}, l = If[getLeftChildIdx[i] <= ds["Length"], ds["Part", getLeftChildIdx[i]], -Infinity ]; r = If[getRightChildIdx[i] <= ds["Length"], ds["Part", getRightChildIdx[i]], -Infinity ]; p = ds["Part", i]; smallest = If[getLeftChildIdx[i] <= ds["Length"] && l < p, getLeftChildIdx[i], i]; If[getRightChildIdx[i] <= ds["Length"] && r < ds["Part", smallest], smallest = getRightChildIdx[i]]; If[smallest =!= i, ds["SwapPart", i, smallest]; MinHeapify[ds, smallest] ]; ];
Wolfram Language code: getLeftChildIdx[i_] := 2i
Wolfram Language code: getRightChildIdx[i_] := 2i + 1
Wolfram Language code: getParentIdx[i_] := Quotient[i, 2]

使用するサンプルデータ構造：

Wolfram Language code: ds = CreateDataStructure["DynamicArray", Reverse[{9, 8, 7, 6, 5, 4, 3, 2, 1}]];

以下は配列をヒープに変換する．ヒープの特性は見にくい：

Wolfram Language code: MinHeapify[ds]; Normal[ds]

この関数は木を生成する：

Wolfram Language code: MakeHeapTree[array_] := Module[{data = Normal[array]}, TreeGraph[Flatten[MakeHeapTree[data, 1]], VertexLabels -> "Name", GraphLayout -> {"LayeredEmbedding", "RootVertex" -> First[data]}] ] MakeHeapTree[arry_, idx_] := { If[getLeftChildIdx[idx] <= Length[arry], { DirectedEdge[arry[[idx]], arry[[getLeftChildIdx[idx]]]], MakeHeapTree[arry, getLeftChildIdx[idx]] }, Nothing ], If[getRightChildIdx[idx] <= Length[arry], { DirectedEdge[arry[[idx]], arry[[getRightChildIdx[idx]]]], MakeHeapTree[arry, getRightChildIdx[idx]] }, Nothing ] }

可視化が最小ヒープの特性を見やすくする：

Wolfram Language code: MakeHeapTree[ds]

特性と関係  (5)

InputForm  (1)

InputFormは，"DynamicArray"の連続するコンテンツを返す：

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

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

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

Length  (1)

Lengthを使って"DynamicArray"の要素数を得ることができる：

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

同じ結果は"Length"演算でも得られる：

Wolfram Language code: ds["Length"]

Normal  (1)

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

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

同じ結果は"Elements"演算でも得られる：

Wolfram Language code: ds["Elements"]

SameQ  (1)

SameQを使って2つの配列に同一の要素が同じ順序で含まれるかどうかをテストすることができる：

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

要素が1つ省かれると，配列はもはや同じではない：

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

"FixedArray"  (1)

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