いつもソートされたリストを作ろう
ここでは例として、「いつもソートされたリスト」を作ってみましょう。
C++言語のテンプレートライブラリやJava言語に用意されているリストは、データが追加された順に並んでいます。ここでは、追加された順に関係なく、いつもデータがソートされているリスト、というものを作ってみます。
「いつもソートされたリスト」は、次の2つのメソッドを持つものとします。これが、「いつもソートされたリスト」の要求仕様です。
| メソッド | 説明 |
|---|---|
| add | データを１つリストに追加する。 |
| getAt(i) | i番目に小さなデータを取り出す。 |
言われたとおりに作る
「いつもソートされたリスト」を、言われたとおりに素直に作ると、次のようになるでしょう。
class AlwaysSortedList {
private int[] array = new int[10000];
private int num = 0;
public void add ( int value ) {
array[num++] = value;
// 並べ替え
for ( int n = num - 1 ; n > 0 ; n-- ) {
if ( array[n] < array[n-1] ) {
int swap = array[n];
array[n] = array[n-1];
array[n-1] = swap;
}
}
}
public int getAt ( int i ) {
return array[i];
}
}
※ここでは例として、Java言語で実装しています。また、単純化のため、データは整数のみ、データ数は最大1万個までとし、エラー処理は省略しました。
addメソッドでデータを追加するたびに並べ替えを行っているので、このリストは、「いつもソートされた」状態になっています。もちろん、getAtメソッドを順に呼び出せば、値の小さなものから順に取り出せます。
ちょっと変わったやり方で作る
しかし、次のようなやり方もあります。
class AlwaysSortedList {
private int[] array = new int[10000];
private int num = 0;
private boolean sorted = true;
public void add ( int value ) {
array[num++] = value;
sorted = false;
}
public int getAt ( int i ) {
// 並べ替え
if ( sorted == false ) {
int[] ar = new int[num];
for ( int n = 0 ; n < num ; n++ ) {
ar[n] = array[n];
}
java.util.Arrays.sort(ar);
for ( int n = 0 ; n < num ; n++ ) {
array[n] = ar[n];
}
sorted = true;
}
return array[i];
}
}
さきほどの実装と違って、addメソッドでデータを追加した時点では、並べ替えを行いません。getAtメソッドを呼んだ時点で、初めて並べ替えを行っています。
実は、この実装では、arrayフィールドの中身は「いつもソートされた」状態にはなっていません。
しかし、このクラスが要求仕様を満たしていない、という訳ではありません。addメソッドを呼べば、データを１つリストに追加できますし、getAtメソッドを呼べば、きちんと、i番目に小さなデータを取り出すことができます。
ここでは、「いつもソートされたリスト」を作っています。「いつもソートされた」とは、sortメソッドなどを呼び出さなくても、いつgetAtメソッドを呼んでもソートされた順にデータが取り出せる、という意味です。これが、クラスの振る舞いの仕様です。
arrayフィールドの中身は、クラスの実装の話です。これが「いつもソートされた」状態かどうかは、クラスの仕様とは関係がないのです。
もっと特殊なやり方で作る
もう１つ、別のやり方を考えてみましょう。
class AlwaysSortedList {
private int[] array = new int[10000];
private int num = 0;
private boolean sorted = true;
public void add ( int value ) {
array[num++] = value;
sorted = false;
}
public int getAt ( int i ) {
if ( sorted == false ) {
if ( i == 0 ) {
// 最小値を探す
int min_n = 0;
for ( int n = 1 ; n < num ; n++ ) {
if ( array[min_n] > array[n] ) {
min_n = n;
}
}
return array[min_n];
} else if ( i == num - 1 ) {
// 最大値を探す
int max_n = 0;
for ( int n = 1 ; n < num ; n++ ) {
if ( array[max_n] < array[n] ) {
max_n = n;
}
}
return array[max_n];
} else {
// 並べ替え
int[] ar = new int[num];
for ( int n = 0 ; n < num ; n++ ) {
ar[n] = array[n];
}
java.util.Arrays.sort(ar);
for ( int n = 0 ; n < num ; n++ ) {
array[n] = ar[n];
}
sorted = true;
}
}
return array[i];
}
}
この実装では、addメソッドを呼んだ時点だけでなく、getAtメソッドを呼んだ時点でも、並べ替えを行わないことがあります。最小値または最大値を取り出すだけであれば、一通り調べてみるだけで、データを並べ替えません。
だいぶ変わった作りになっていますが、このクラスも、addメソッドを呼べば、データを１つリストに追加できますし、getAtメソッドを呼べば、きちんと、i番目に小さなデータを取り出すことができますので、要求仕様を満たしている「いつもソートされたリスト」です。
どれが一番良い方法か
ここでは、「いつもソートされたリスト」を、3通りの方法で実装しました。これらは、振る舞いの仕様はすべて同じです。ただ、実行速度には違いがあります。
次の4つのケースで、それぞれの実装の速度を比べてみましょう。
- 1万個のランダムなデータを追加する。1つデータを追加するたびに、ランダムにi番目のデータを取り出す。
- 1万個のランダムなデータを追加する。100個データを追加するたびに、ランダムにi番目のデータを取り出す。
- 1万個のランダムなデータを追加する。すべてのデータを追加し終わったら、最後に一度だけ、0番目から9999番目までのデータを順に取り出す。
- 1万個のランダムなデータを追加する。1つデータを追加するたびに、最大値を取り出す。すべてのデータを追加し終わったら、最後に一度だけ、0番目から9999番目までのデータを順に取り出す。
それぞれの実行にかかった時間を測定すると、次のようになりました。
| 実装方法 | ケース1 | ケース2 | ケース3 | ケース4 |
|---|---|---|---|---|
| 言われたとおりに作ったクラス | 234 | 235 | 188 | 235 |
| ちょっと変わったやり方で作ったクラス | 4031 | 63 | 31 | 4172 |
| もっと特殊なやり方で作ったクラス | 4172 | 110 | 32 | 219 |
なお、データの数を1万個から2万個に増やすと、次のようになりました。
| 実装方法 | ケース1 | ケース2 | ケース3 | ケース4 |
|---|---|---|---|---|
| 言われたとおりに作ったクラス | 781 | 828 | 890 | 812 |
| ちょっと変わったやり方で作ったクラス | 17140 | 312 | 31 | 17000 |
| もっと特殊なやり方で作ったクラス | 17062 | 172 | 31 | 921 |
言われたとおりに作ったクラスは、どのようなケースでも同じくらいの時間がかかりました。
ちょっと変わったやり方で作ったクラスや、もっと特殊なやり方で作ったクラスは、ケース1では、かなり遅くなってしまいました。
しかし、リストにデータを追加しながら、同じくらいの頻度でデータを取り出すことは、実際にはあまり無さそうです。もし、データを取り出す回数が少ないのであれば、ちょっと変わったやり方で作ったクラスの方が、良いパフォーマンスを発揮できます。
さらに、最小値や最大値は良く使うけれども、実は、真ん中あたりのデータはめったに取り出さない、ということも、あるかもしれません。もしそうなら、もっと特殊なやり方で作ったクラスの方が、良いパフォーマンスを発揮できます。
言われたとおりに作ったクラスは、仕様と実装が一致しているので、分かりやすいです。しかし、必ずしも、それが最適な方法ではないこともあります。
このように、「いつもソートされたリスト」といっても、必ずしも、そのとおりに実装するとは限りません。クラスの振る舞いの仕様と、中身の実装とは、まったく別物です。これが、オブジェクト指向におけるカプセル化ということなのです。