"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,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 の入力形
    Normal[ds]ds を通常の式に変換する

例題

すべて開くすべて閉じる

例  (2)

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

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

長さを返す：

最初の要素を抽出する：

要素を変更する：

要素が更新された：

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

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

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

全要素を合計する：

スコープ  (1)

情報  (1)

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

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

アプリケーション  (11)

逆配列  (1)

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

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

要素を逆にする：

バブルソート  (1)

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

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

要素をソートする：

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

挿入ソート  (1)

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

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

要素をソートする：

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

クイックソート  (1)

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

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

要素をソートする：

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

マージソート  (1)

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

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

要素をソートする：

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

ヒープソート  (1)

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

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

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

ティムソート  (1)

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

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

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

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

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

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

シャッフルを適用する：

回文配列  (1)

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

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

これは回文配列である：

クイックセレクト  (1)

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

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

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

ヒープ  (1)

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

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

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

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

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

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

特性と関係  (1)

"FixedArray"  (1)

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