"ExtensibleVector" (データ構造)

"ExtensibleVector"

要素が一般式である，動的に拡張可能なベクトルを表す．

詳細

  • 拡張可能なベクトルは，連続的に前後に要素を付加するだけでなく，要素を効率的に抽出したり更新したりする際にも役立つ．
  • CreateDataStructure[ "ExtensibleVector"]新しい空の"ExtensibleVector"を作成する
    CreateDataStructure[ "ExtensibleVector",elems]elems を含む新しい"ExtensibleVector"を作成する
    Typed[x,"ExtensibleVector"]x に"ExtensibleVector"型を与える
  • "ExtensibleVector"型のデータ構造には，以下の演算が使える．
  • 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["JoinFront",elems ]elems を ds の前に繋げるtime: O(nelems)
    ds["Length",x]ds に保存された要素の数time: O(1)
    ds["Part",i]ds の i 番目の部分を返すtime: O(1)
    ds["Prepend",x]x を ds の先頭に付加する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)

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

要素は後ろに付加できる：

要素は先頭に付加できる：

長さを返す：

第1要素を抽出する：

要素を変更する：

要素が更新された：

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

要素は素早く付加できる：

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

全要素を合計する：

スコープ  (1)

情報  (1)

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

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

アプリケーション  (11)

逆ソート  (1)

"ExtensibleVector"のインプレース逆ソートを行う簡単な関数：

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

要素を逆順にする：

バブルソート  (1)

バブルソートとは，コーディングするのは簡単だが，通常パーフォーマンスは良くない簡単なソートアルゴリズムである：

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

要素をソートする：

データ構造はその場でソートされる：

挿入ソート  (1)

挿入ソートとは，簡単にコード化でき，通常大きな配列に対するパーフォーマンスは良くないが，小さな配列に対しては有用である簡単なソートアルゴリズムである：

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

要素をソートする：

データ構造はその場でソートされる：

クイックソート  (1)

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

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

要素をソートする：

データ構造はその場でソートされる：

マージソート  (1)

クイックソートとは，効率的なソートアルゴリズムである．これは，ワークスペースを使う簡単な実装である：

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

要素をソートする：

データ構造はその場でソートされる：

ヒープソート  (1)

ヒープソートとは，ヒープを構築することで，その場で使える効率的なソードアルゴリズムである：

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

データ構造はその場でソートされる：

ティムソート  (1)

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

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

データ構造はその場でソートされる：

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

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

シャッフルに使う簡単な配列：

シャッフルを適用する：

回文  (1)

中央の周りで対称である配列は回文である：

これは回文ではない：

これは回文である：

クイックセレクト  (1)

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

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

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

ヒープ  (1)

ヒープとは，（最小値のヒープの場合）子に保存された値が親に保存されたものより小さい，木ベースのデータ構造である．これは，優先度付き待ち行列を実装するのに使われることが多く，通常木ではなく配列で実装される．

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

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

これは配列をヒープに変換する．ヒープの特性は見分けにくい：

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

可視化すると，最小値のヒープの特性が見分けやすくなる：

特性と関係  (2)

"FixedArray"  (1)

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

"DynamicArray"  (1)

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