データ構造 Part1-2 「静的配列2」

はじめに

前回の記事では静的配列の基本的な情報について解説しました。
想定される操作とその計算量などです。

この記事では、もう少し踏み込んで静的配列の性質を確認していきます。

特定条件下での性能

配列をリストのように扱いたい場合、要素の挿入と削除に O(n) かかる。

配列に隙間がないようにするためには、挿入や削除が行われた場所より後ろの
全ての要素を移動する必要がある。
この隙間を作らないようにする操作に O(n) かかってしまいます。

 

挿入の例

int scoreArray[4];
scoreArray[0] = 100;
scoreArray[1] = 50;
scoreArray[2] = 25;
// scoreArray: [100, 50, 25, 0]

// insert
// scoreArray[1] = 75;
// scoreArray: [100, 75, 25, 0]
scoreArray[3] = scoreArray[2];
scoreArray[2] = scoreArray[1];
scoreArray[1] = 75;
// scoreArray: [100, 75, 50, 25]

 

削除の例

int scoreArray[4];
scoreArray[0] = 100;
scoreArray[1] = 75;
scoreArray[2] = 50;
scoreArray[3] = 25;
// scoreArray: [100, 75, 50, 25]

// delete
// scoreArray[1] = 0;
// scoreArray: [100, 0, 50, 25]
scoreArray[1] = scoreArray[2];
scoreArray[2] = scoreArray[3];
scoreArray[3] = 0;
// scoreArray: [100, 50, 25, 0]

 

配列長を超える場合は、新しい配列を確保する必要がある。

ソースコードの例で説明します。

int scoreArray[3];
scoreArray[0] = 100;
scoreArray[1] = 50;
scoreArray[2] = 25;
// scoreArray: [100, 50, 25]

// push
// scoreArray[3] = 10;
// Index Out of Bounds Error
int scoreArray2[4];
scoreArray2[0] = scoreArray[0];
scoreArray2[1] = scoreArray[1];
scoreArray2[2] = scoreArray[2];
scoreArray2[3] = 10;
// scoreArray2: [100, 50, 25, 10]

探索は一般的に O(n) かかるが、ソート済みであれば O(log(n)) になる。

ソート済みの配列に対しては線形探索ではなく二分探索を選択できるので、
探索にかかる最悪計算時間量が O(n) ではなく O(log(n)) になる。
詳しくは概要欄から私が以前投稿した動画をご覧ください。

 

デメリットとメリット

  • デメリット
    • 配列の長さが変えられない
    • 隙間を作らないようにしたい場合、挿入と削除が煩雑
  • メリット
    • 占有する領域の上限を明示的に管理できる

簡単に言うと、使用できるメモリ領域が限られている場合に便利。
いわゆる組み込み系と呼ばれる職種では有用になることがある(らしい)。

近年のコンピュータの性能の向上によって、一般的には
静的配列を意識する場面はかなり少なくなってきている。

とはいえ、低レイヤーでは配列が使用されているので、
配列のことを知っていて損はない。
配列を使用することで時間や空間が著しく節約できることもある。

 

より便利なデータ構造

もっと簡単に追加や削除が行えるデータ構造として、
動的配列や連結リストが挙げられる。

動的配列や連結リストでは、その長さを意識せず追加や削除が行える。
便利なデータ構造を利用することで、メモリ管理を意識しないで良くなるとも言えます。

 

さいごに

次回は少し静的配列より少し便利な動的配列について解説します。
興味が沸いたという方は是非チャンネル登録をお願いいたします。
また、指摘や感想のコメントや、高評価もお待ちしております。

この記事を最後までご覧いただきありがとうございました。