ソフトウェアエンジニアを目指す人のブログ

ソフトウェアエンジニアになるために勉強したことを書いていきます

Dynamic Array (Cousera Data Structures week 2)

前回の記事に引き続き、CouseraのData Structuresコースのweek2講義のメモです www.coursera.org

前回のweek1の内容の記事はこちら

rikeiin.hatenablog.com

Dynamic Arrays

通常の静的な配列と異なり、Dynamic Arrayは後から配列のサイズを増やすことができる。 Dynamaic Arrayは以下の操作を持つデータ構造である。

  • Get(i):インデックスiの要素を返す
  • Set(i, val):インデックスiの場所にvalをセット
  • PushBack(val):valを配列の末尾にセット
  • Remove(i):インデックスiの要素を削除する
  • Size():要素の合計数を返す

Dynamic ArrayはC++ではvector, JavaではArrayList, pythonではlistなどで実装されている。

配列にpushbackを繰り返してサイズが一杯になった場合、新たに現在の配列のサイズの2倍のサイズの新しい空間をメモリに確保する。 そして、現在の配列に入っている要素を新しい配列にコピーし、現在の配列をメモリから開放してから新しい配列にpushbackしていく。

各操作のオーダーは以下の通り。 f:id:rikeiin:20180407173703p:plain

Dynamic Arrayまとめ

  • 静的な配列と異なり、Dynamic Arrayはサイズが変更できる
  • 新しい要素の追加は基本的に定数時間だが、配列のリサイズが伴う場合はO(n)
  • 確保したメモリ空間が無駄になることがある

Amortized Analysis

Amortized Analysisは償却解析、ならし解析とも呼ばれ、一回の実行で毎回最悪時間計算量を見積もるのではなく、 一連の操作でどのくらいの計算量になるかを解析する手法である。 例えば、上のDynamic Arrayの要素追加において時間計算量は基本O(1)だがリサイズが伴うとO(n)になるという話があった。こういったときに配列に連続して要素を追加していったときにトータルとして計算量がどのくらいになるかというのを見積もる。

ここで操作をn回連続して行ったときのAmortized costというものを導入し、以下のように計算される。

\frac{\mathrm{Cost(}n \mathrm{\ operations)}}{n}

Aggreggate Method

n回の操作の平均を計算量とする手法 以下はDynamic arrayでpushbackを連続して行う例 f:id:rikeiin:20180410194129p:plain

Banker's Method

  • コストの低い操作にチャージを掛け、トークンとしてデータ構造に保存する。
  • コストの高い操作にトークンを使用する

参考動画↓

Amortized Analysis - YouTube

f:id:rikeiin:20180410195619p:plain

Physicist's Method

  • データ構造の状態を表すポテンシャル関数\Phiを定義
  • ポテンシャル関数は非負であり、初期状態は0とする
  • 操作tの償却コストは次のようになる
    • c_t + \Phi(h_t) - \Phi(h_{t-1})
  • n回の操作のコストは \sum_{i=1}^n(c_i)
    • 償却コストの合計は次のようになる

f:id:rikeiin:20180410205623p:plain

f:id:rikeiin:20180410205848p:plain

f:id:rikeiin:20180410205913p:plain