データ構造その3(動的配列)
赤ちゃんの成長を見てると、もはや進化に近い気がしますね。
まだまだ泣いてばかりだけど、日々新しいことができていく姿に一緒に笑って一緒に学んでいきたいな、と。子供のいる人生って大変だけどすごく楽しいです。これからどんなことに興味を持って、どんな人を好きになるのか。この子の育つ世の中を少しでも楽しくしたいと思います。
まぁ、自分の子供だからかわいいわけで、電車で降車客押しのけて席に座ろうとしたり、ランドセルをぶつけてくる私立小学生とかは普通に邪魔くさいのですが。
さて、前回はデータ構造の標準化、抽象データ型について取り上げました。
いよいよ、今回から実際のデータ構造に入ります。まずはほとんどの人が使っているであろう配列です。ほとんどの言語では動的配列を知らずに使っていると思いますが、配列のメリット・デメリットとその後ろで行われている処理について見ていきます。
期待として、配列やリストは裏でどう動くか、また計算量も知っておくとデータ構造選びの理由付けができるようになります。プロのエンジニアとしてコードを書くなら、データ構造自体を実装することはなくても仕組みを知っていて、なぜそういう速度で動くか、なぜその構造を使うべきか説明できるようになって欲しいです。
一人前のソフトウェアエンジニアを自称するなら、自分のコードの1行1行がそうである理由を説明できるべきだと思っています。なんでそのコレクション(データ構造)を使ったのか説明できる、というのもその一つです。ぜひ、各構造がどういう処理に強く、どういう処理に弱いか、適した処理を考えながら読んでください。
配列のPros/Cons
配列のメリット
シンプル
それぞれの要素にO(1)でアクセスが可能
配列のデメリット
生成時にサイズが固定される
O(1)で要素にアクセスできるのをランダムアクセスと呼びます。
多くの高級言語ではサイズは気にせずに配列に入れていると思いますが、C言語の配列、もしくはC++などで、int[10]などで定義する配列は固定のサイズを宣言時に明示して、それ以上の要素が入れられません。
では、サイズを広げたい場合どうなるでしょうか？
配列とメモリ
これは知っておいて欲しいことなので、配列が連続したメモリが使われることを説明しておきます。これがランダムアクセスできる理由なのですが、要素がメモリの連続する領域に書き込まれているので、データの開始位置から データのサイズ x 何番目か(0 origin) でデータのメモリ上のアドレスがわかります。つまり、
arr[idx]のアドレス = arrの開始アドレス + (データの型のサイズ x idx)となります。
ここで簡単なテストコードを書いてみます。
C++は &変数名 でアドレスが取得できます。
#include <iostream>
using namespace std;
int main() {
int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
cout << "head: " << &arr << endl;
cout << "sizeof(arr[0]) = " << sizeof(arr[0]) << endl << endl;
for (int i = 0; i < 5; ++i) {
if (i != 0) cout << endl;
cout << "arr[" << i << "]= " << &arr[i];
}
cout << endl;
return 0;
}
と、配列自体のアドレスと要素のサイズ、i番目の要素のアドレスを出力してみると、結果は
head: 0x7ffcce3a4ba0
sizeof(arr[0]) = 4
arr[0]= 0x7ffcce3a4ba0
arr[1]= 0x7ffcce3a4ba4
arr[2]= 0x7ffcce3a4ba8
arr[3]= 0x7ffcce3a4bac
arr[4]= 0x7ffcce3a4bb0データのサイズ(int=> 4 byte => 32 bits)ずつアドレスが進んでること、先頭と配列自体のアドレスが同じことがわかります。なので、添え字([n]このnに当たるインデックスの数字)が0から始まるのにも納得できると思います。先頭は0番目の位置にあるわけです。
ということは9番目のデータのアドレスは？
はい。ランダムアクセス可能なのが理解できたと思います。
このコードのwandboxのURL貼っておくので、興味あれば自分でも実行してみてください。
ちなみに、CPUの処理時にCPU上のキャッシュに対してメモリから一定のサイズの塊で連続したメモリ領域を取ってきて使うので、配列でデータが連続しているというのはキャッシュ効率が良く処理速度が速くなったり、という話もあるのですが、初学者にはちょっと理解しにくいですかね。キャッシュのサイズは小さいので、コレクション内のデータが離れていると頻繁にメモリとキャッシュの間での転送が発生します。データが連続していたら、卵のパックのようにまとめて取ってきて次々使えますが、連続していないと、使う度に冷蔵庫を探して取ってきては調理しないといけないようなイメージです。
キャッシュの話とかは並列処理の講座を書いたりしたら詳しく解説しますが、このペースだといつになることか。
動的配列
ここからが本題です。
サイズが固定という問題の解決として出てくるのが動的配列です。
多くの言語で使われる配列は動的配列(サイズが自動拡張される＝サイズを気にしないで使える)かと思います。
目的
動的配列ではAPIの裏側にメモリ管理が隠蔽されます
=> 関数呼び出しだけでメモリ管理の詳細を気にせずに利用できます。
それぞれの要素のアクセスはO(1)が保証されます
動的配列ではcapacity(容量)が可変です
動的配列の構造
動的配列は3つのフィールドを持っています。
一つ目はデータ領域で固定サイズの配列です。また、管理情報を持っており、使用中のサイズ(size)と使用可能な合計サイズ (cap)があります。
size
現在インスタンス内に保持している要素数
追加削除の関数内で管理される
capacity
リサイズが必要になる前に動的配列が保持可能な要素数
要素の追加
sizeのインクリメント(1増やす)
新しい値をdata領域の最後に追加する
では、もし size == capacity となったらどうなるでしょう？
その時はデータの再配置が必要です。
再配置では全てのデータを新しく確保したメモリの領域に全てコピーする必要があります。
これらの詳細はユーザーからは隠蔽されます。
データの再配置
データを再配置する際には、メモリ上により広い連続した領域(通常2倍)を確保して、データをコピーします。コピーしたら変数が向いている動的配列のアドレスを新しい領域に変更します。自分で実装することは基本的にないと思いますが、コピー後に古い配列の領域を解放するのを忘れるとメモリリークになります。
要素の挿入
途中挿入の場合もデータが連続しているという配列の特性からデータの再配置が必要になります。
データの連続性を守るため、挿入箇所移行のデータを全て一つ後ろにコピーする必要があります。上記の例で4を5にコピーしますが、いきなり5に上書きすると5が失われるので、最後から一つずつ後ろにずらします。
for (int i = this.size; i >= idx; --i) {
this.data[idx] = this.data[idx - 1];
}
this.size += 1;さて、この場合の最悪計算量はどうなるでしょう。
明確ですね。最初に挿入した場合に全てのデータを移動するのでO(n)となります。更にそれでcap==sizeになった場合はメモリの再配置も必要になります。
ただし、この再配置の発生はcap=1から始めたとしてlog(n)回発生する程度なのでデータの挿入回数が増えるにつれて発生しなくなるため、計算量としては償却計算量とかみなし計算量でΘ(1)とされます。回数が増えるにつれて1に近づく感じです。
また、データの大体のサイズがわかっていれば初期化時に指定すべき、と聞いたことがあるかも知れませんが、閾値を超える度に再配置が発生し、処理コストが上がるため、最初からcapacityを広く取っておく(メモリの領域を押さえておく)ことで再配置の回数を減らせます。適切に初期化すれば1～3回程度とかに押さえられるのではないでしょうか。
要素の削除
同様に削除の場合も並び替えが必要になります。
その場合は逆に後ろから前にコピーします。
この場合の最悪計算量はなんで、どんな時でしょう。
言うまでもないですね。
動的配列のインターフェース
init(cap)
free() # 要らないかも
size()
get(idx)
add(val)
put(idx, val)
remove(idx)
__double_capacity()__double_capacity()は再配置の説明で新しく領域を確保した部分です。現在のcapacityの2倍の領域を確保してデータをコピーします。
疑似実装コード
ここから疑似コードによる実装での説明になります。
疑似コードは言語によらない汎化したコードですが、ちょっと説明の都合上Cに寄せて型をあいまいに書くような形にしたいと思います。というのも言語で標準の実装がないC言語が一番データ構造の理解によいからです。
初期化部分
class DynArr {
void init(cap) {
assert(cap >= 0);
this.capacity = cap;
this.size = 0;
this.data = new arr[cap];
}
}サイズのチェックを一応入れています。
疑似コードですが、newの部分はメモリを所定の型のサイズの{cap}個分のリストとして確保するイメージを持ってください。型の指定は読者の型の使う言語のやり方でイメージして頂けると。
メモリ解放部分
class DynArr {
void init(cap) {...}
void free() {
assert(this.data != null);
free(this.data);
this.capacity = 0;
this.size = 0;
}
}C系の言語を書いたことがあればわかりやすいと思いますが、メモリは解放しないとメモリリークとなります。また、重複して解放してもダメです。まずはメモリ領域の指定があるかを確認して、解放した上で、利用可能なサイズや現状のサイズをリセットします。この関数はこれ以降このクラスを使わない、という後処理で呼ぶイメージを持ってください。
サイズの取得
class DynArr {
void init(cap) {...}
void free() {...}
int size() {
return this.size;
}
}サイズを返すだけです。
要素の取得
class DynArr {
void init(cap) {...}
void free() {...}
int size() {...}
Type get(idx) {
assert(this.size() > idx && idx >= 0); # 符号が大事
return this.data[idx];
}
}最初のassertでのidxの確認をよく理解してください。
このassertの条件を外れると多くの言語にあるArrayIndexOutOfBoundsのようなエラーになります。
要素の追加
class DynArr {
void init(cap) {...}
void free() {...}
int size() {...}
Type get(idx) {...}
void add(val) {
if (this.size >= this.capacity) {
__double_capacity();
}
this.data[this.size] = val;
this.size += 1;
}
}大事な部分の1つです。
まず準備としてサイズが容量いっぱいだった場合、再配置を行い、容量を2倍にします。
追加部分の準備が整ったら、データを追加します。indexの指定の仕方を理解してください。理解できなければ配列の理解が不十分です。
最後にサイズを1つ増やします。indexの指定の関係もあり、追加後にインクリメントするのが肝です。
容量の2倍化(再配置)
class DynArr {
void init(cap) {...}
void free() {...}
int size() {...}
Type get(idx) {...}
void add(val) {...}
void __double_capacity() {
new_cap = this.capacity * 2;
new_data = new arr[new_capacity];
for (i = 0; i < this.size; ++i) {
new_data[i] = this.data[i];
}
size = this.size;
this.free();
this.capacity = new_cap;
this.size = size;
this.data = new_data;
}
}再配置部分です。Cのインターフェースを基に書いてるので、free()の使い方がちょっと微妙かもです。
課題
putとremoveを自分で書いてみましょう。
というより、疑似コードだけなので、自分の使っている言語で実装してみましょう。と言っても、たいてい配列を使おうとすると動的配列になってしまうので、疑似的な動的配列になるかも知れません。Cで実装するのが一番わかりやすいかも知れませんが、その場合、上記インターフェースの各関数の第一引数に動的配列のstructのポインタを渡すようにしてみてください。
次回予告
次回は今回の動的配列を使ってStackとBagの実装についてみていきます。
この記事が気に入ったらサポートをしてみませんか？