オブジェクト・プログラミング

オブジェクト・プログラミング
第６回
効率
品質の高いプログラム（復習）

品質の高いプログラムって？





正しさ
使いやすさ
再利用性
可読性（読みやすさ）
効率（速さ）
今日の目標

ソフトウエアの効率について説明できるようにな
る。



効率の悪いプログラムを使うとどうなるか説明できる
ようになる。
効率を調べるための指標(BigO記法)を説明できるよ
うになる。
メソッドの返り値について説明できるようになる。

メソッドの返り値を使ったプログラムが書けるようにな
る。
効率が悪いとどうなるか？



１万人の社員がいる会社があります。
ログインするために社員番号でパスワード
を検索します。
１人の検索に0.１秒かかると、全員がログ
インし終わるまでに何分かかりますか？
こたえ:
１分で６００人だから
10000/600=16.66分
→大変だ！
前回のプログラムを復習

配布資料（解答例）を参照
ItemInfoFolder
VendingMachineMain
main(args : String[])
取扱商品情報の操作の
順番に責任を持つ
insert(insertInfo : Iteminfo)
delete(deleteKey : int)
search(searchKey : int)
display()
取扱商品情報を
管理する責任を持つ
1
0..n
ItemInfo
no : int
name : String
取扱商品情報の保持に
責任を持つ
今日の問題

今日はたくさんの商品情報を取り扱います。



１万個の商品情報
１０万個の商品情報
現実の自動販売機ではありえませんが、コ
ンピュータの自動販売機ならできますね。

例えば、WEBでソフトやゲームを販売する場
合。
たくさんの商品情報を取り扱う

ItemInfoFolderクラスの変更



配列の大きさを増やす
forループの回数を増やす
VendingMachineMainクラスの変更

forループを使って、たくさんの商品情報を挿
入する。
ItemInfoFolderクラスの変更

配列の大きさを一元管理できるように変数を用
意する。（１０万まで入るようにする）
int arrayMax = 100000;

配列の大きさを増やす
ItemInfo[] itemInfoArray = new ItemInfo[arrayMax];

検索、削除などに使っているforループの回数を
増やす
for(int i=0;i<arrayMax;i++){
}
VendingMachineMainクラスの
変更

forループを使って、たくさんの商品情報を
挿入する。10000と100000でやってみます。
//メインメソッド
public static void main(String[] args) {
ItemInfoFolder folder = new ItemInfoFolder();//商品情報を
管理するオブジェクトを作る
int registerNum = 10000;
//取扱商品を10000種類登録する
for(int i=0;i<registerNum;i++){
folder.insert(new ItemInfo(i, “コーラ”+i));//今日の商品名は
仮にコーラ+商品番号
ex)コーラ2030
}
System.out.println("挿入終了");
}
このプログラム、動きます？



10000個挿入はそれなりの早さでできます。
(Pentium800MHzで約0.5秒)
ですが、100000個挿入にするとなかなか
“挿入終了”と出てきません。やたら時間が
かかります。
何故でしょう？
insertのif文


問題：insertのif文は何回実行されているでしょ
うか？
10000回の時と100000回の時でどうでしょう？
public void insert(ItemInfo insertItem){
for(int i=0;i<arrayMax;i++){
if(itemInfoArray[i] == null){
itemInfoArray[i] = insertItem;
break;
}
}
}
計算方法





１つ挿入の時→１回
２つ挿入の時→１＋２回＝３回
３つ挿入の時→１＋２＋３回＝６回
１００個挿入の時→1+2+…..+100回
=(1+100)×50 = 5050回
N個挿入の時→(1+n)×n/2回
=約n^2/2回
答え


10000個のとき
約10000×10000 / 2
= 50,000,000回
（５千万回)
100000個のとき
約100000×100000 / 2
= 5,000,000,000回
(50億回)
約0.5秒
おそらく50秒
挿入を早くする方法

挿入する番地を覚えておけばよい。

属性にsizeを加えます。
//ItemInfoFolderクラス
public class ItemInfoFolder {
ItemInfo[] itemInfoArray = new ItemInfo[arrayMax];//商品
情報を管理するための配列を作る
int size = 0;
…
}
効率のよい挿入のプログラム
//ItemInfoFolderクラス
public class ItemInfoFolder {
ItemInfo[] itemInfoArray = new ItemInfo[arrayMax];
int size = 0;
public void insert(ItemInfo insertItem){
itemInfoArray[size] = insertItem;
size++;//一つ挿入したら番地を増やす
}
…
}
削除のプログラムも変更する
//ItemInfoFolderクラス
public class ItemInfoFolder {
ItemInfo[] itemInfoArray = new ItemInfo[arrayMax];
int size = 0;
public void delete(int deleteKey){
…(削除のプログラムを書く)
size--;//一つ削除したら番地をへらす
}
…
}
検索、削除のプログラムも少し
効率化する。
nullかどうか
調べる必要なくなる
//取扱商品情報を検索するメソッド(size導入前）
public void search(int num){
for(int i=0;i<arrayMax;i++){
if(itemInfoArray[i] != null){
if(itemInfoArray[i].no == num){
//System.out.println("見つかりました。");
return;
}
}
}
//System.out.println("見つかりませんでした。");
}
配列全部を検索
//取扱商品情報を検索するメソッド(size導入後）
public void search(int num){
for(int i=0;i<size;i++){
if(itemInfoArray[i].no == num){
//System.out.println("見つかりました。");
return;
}
}
}
//System.out.println("見つかりませんでした。");
入っている分だけ検索
時間を計る方法

StopWatchクラスの作成
StopWatchクラス
public class StopWatch {
long startTime;
long stopTime;
public void start(){
startTime = System.currentTimeMillis();
}
public void stop(){
stopTime = System.currentTimeMillis();
}
}
public long getTime(){
long time = stopTime – startTime;
return time;
}
コメントは省略
StopWatchクラス解説(1)

long型

int型と同じで整数が入る変数ですが、int型よ
りも、多くの数を表わすことができます。



int型----- -2147483648～2147483647
long型--- -9223372036854775808～
9223372036854775807
今回は時間をlong型であらわします。

単位はミリ秒単位。(1/1000秒単位)
StopWatchクラス解説(2)

start()メソッド
public void start(){
startTime = System.currentTimeMillis();
}
System.curretnTimeMills()メソッドは、現在の時刻をlong型で
返します。
（ 1970 年 1 月 1 日午前 0 時 0秒を0とした差が返ってきます。)
startTime変数に格納します。stop()メソッドも同様です。
StopWatchクラス解説(3)

getTime()メソッド
public long getTime(){
long time = stopTime – startTime;//①
return time;//②
}
①では、start()メソッドが呼ばれた時刻とstop()メソッドが呼ばれた
時刻を引き算した結果（要するにかかった時間）をtime変数に格納
します。
②では、①で格納した時間を返り値として返します。
次で説明
メソッドの返り値
今までは、
今日は
ここまで。
返り値
のお話
仕事してくれよ！＋引数
メソッドA()
呼び出し側
終わったぜ！＋返り値
getTime()メソッドの返り値
かかった時間を計算して！＋（引数なし）
呼び出し側
getTime()
計算終わったよ！＋1203ミリ秒かかったよ
返り値のあるメソッドの書き方
①
public long getTime(){
long time = stopTime – startTime;
return time;
}
②
①何も返さない場合、voidと宣言していたところに戻す返り値の型
名を書きます。
②値を返すときは、return [変数名] で返します。
そこでメソッドは終了します。
StopWatchクラスの利用法
//メインメソッド
public static void main(String[] args) {
ItemInfoFolder folder = new ItemInfoFolder();
StopWatch sw = new StopWatch();//StopWatchをインスタンス化
sw.start();//ストップウオッチをスタートさせる。
//10万個の商品情報を登録
int registerNum = 100000;
for(int i = 0;i<registerNum;i++){
folder.insert(new ItemInfo(i, “コーラ”+i));
}
sw.stop();//ストップウオッチを止める。
long time = sw.getTime();//かかった時間を返り値として受け取り、変数に格納
System.out.println(“かかった時間は”+time+”ミリ秒です”);//かかった時間を表示
}
検索の効率

問題:１万個のデータを１万回検索します。
//メインメソッド
//一万個のデータを一万回検索する
public static void main(String[] args) {
ItemInfoFolder folder = new ItemInfoFolder();//商品情報を
管理するオブジェクトを作る
//取扱商品を10000種類登録する
//省略
}
//今登録した取扱商品をすべて検索する
for(int i=0;i<10000;i++){
folder.search(i);
}
1万行の出力！


１万回検索すると、１万行「見つかりまし
た」が出力されてしまいます。これは分かり
ずらいし、速度も遅くなってしまうので、
searchメソッドを修正します。
searchメソッドにboolean型の返り値を加え
ます。


見つかったら,trueを返します。
見つからなかったら,falseを返します。
searchメソッドの修正
返り値を返すことを宣言します。
//取扱商品情報を検索するメソッド（ItemInfoFolderクラス）
public boolean search(int searchKey){
for(int i=0;i<size;i++){
if(itemInfoArray[i].no == searchKey){
return true;
}
見つかったら、trueを
}
返します。
return false;
この時点で、このメソッドは
}
終了します。
見つからなかったら、
falseを返します。
searchメソッド呼び出しの修正
//メインメソッド
//一万個のデータを一万回検索する
public static void main(String[] args) {
ItemInfoFolder folder = new ItemInfoFolder();//商品情報を
管理するオブジェクトを作る
int registerNum = 10000;
//取扱商品を10000種類登録する
//省略
}
//今登録した取扱商品をすべて検索する
for(int i=0;i<registerNum;i++){
boolean result = folder.search(i);//検索し結果を格納
if(result == false){
System.out.println(“見つかりませんでした”);
}
必ず見つかるはずなので、
}
この行は表示されない。
実験環境は整った



さて、実験してみましょう。
Pentium800MHzでは１万個の検索に800
ミリ秒(0.8秒)かかりました。
１０万個ではどれぐらいかかるでしょう？
（実験しないほうが賢明）
if文の実行回数を調べる

例によってif文の実行回数を調べます。
//取扱商品情報を検索するメソッド（ItemInfoFolderクラス）
public boolean search(int searchKey){
for(int i=0;i<size;i++){
if(itemInfoArray[i].no == searchKey){
return true;
}
}
}
return false;
}
最初と最後で違う！


0を検索した場合→１回のif文で見つかる。
9999を検索した場合→１万回のif文で見つ
かる。
平均5000回のif文で見つかる。
よって、if文の回数は5000×10000=50,000,000
(５千万回)
よって、n個の検索で必要なif文の数は
n/2 × n = n^2/2
10万回検索をしたら、


１０万要素を１０万回検索した場合は、
100000×100000 /2 = 5,000,000,000
(50億回)
の比較が必要です。
理論上は50秒で検索が終わります。
ですが、実際にやってみると、７分ぐらいか
かります。これはオブジェクトにアクセスの
オーバーヘッドが大きくなるためです。
検索の効率を考える

前回までの方法を「リニアサーチ」といいま
す。
９を探す場合
1
2
3
4
5
6
7
8
9
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
10
11
[9] [10]
あった！
検索の効率を上げる方法

バイナリサーチ！

配列の中身がソート済み（順番に並んでいる）
の場合に有効。

今日はfor文で入れているのでソート済みになって
います。
バイナリサーチの考え方(1)
①まず、真ん中を探します。
②違った場合も、探す範囲は半分に絞られます。
（数が少なかったら右半分、逆なら左半分にあります。）
９を探す場合
1
2
3
4
5
6
7
8
9
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
ちがった！
10
11
[9] [10]
９は６より大きいから、
この範囲に絞られる
バイナリサーチの考え方(2)
③次に、その範囲の中のまた真ん中を探します。
④それを見つかるまで繰り返します。
９を探す場合
1
2
3
4
5
6
7
8
9
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
ちがった！
10
11
[9] [10]
９は８より大きいから、
この範囲に絞られる
バイナリサーチの実装
//バイナリサーチをするメソッド(ItemInfoFolderクラスに追加する)
public boolean binarySearch(int searchKey){
int lower = 0;//探す配列の範囲の最小値
int upper = size-1;//探す配列の範囲の最大値
int center;//次に調べるべき配列の番地
while(true){
center = (lower + upper)/2;//次に調べるのを範囲の真中に設定
if(itemInfoArray[center].no == searchKey){
return true;//見つかった
}else if(lower > upper){
return false;//見つからず、かつ、もう調べる範囲がなくなった。
}else{
//見つからないので、次に調べる範囲を狭める
if(itemInfoArray[center].no < searchKey){
lower = center +1;//範囲を右半分にする
}else{
upper = center -1;//範囲を左半分にする
}
}
}
}
バイナリサーチの効率（１）

例えば、100個の要素の中から検索するこ
とを考えてみましょう。
リニアサーチの場合
比較の回数は
－最小の場合で１回
－最大の場合で１００回
－平均５０回
バイナリサーチの場合
比較の回数は
－最小の場合で１回
－最大の場合で７回
－平均７回以下
バイナリサーチの効率（２）
要素数
比較最大回数
リニアサーチ
バイナリサーチ
10
10
2
100
100
7
1000
1000
10
10000
10000
14
100000
100000
17
1000000
1000000
20
10000000
10000000
24
バイナリサーチの効率（３）
バイナリサーチの
比較回数
検索できる範囲
0
1
1
2
2
4
3
8
4
16
5
32
6
64
7
128
2^比較回数
ようするに
「２の巾乗」
が検索できる範囲
になる。
２の巾乗を逆計算する

問題：100をバイナリサーチすると、最大何
回の比較が必要か。計算で求めよ
答え log2(100) = 6.644
切り上げて7回
バイナリサーチの効率（４）

Nつの要素の中から検索するときの効率
は、以下のように計算されます。
リニアサーチの場合
比較の回数は
－最小の場合で1回
－最大の場合でN回
－平均N/2回
Nに比例
バイナリサーチの場合
比較の回数は
－最小の場合で１回
－最大の場合でlog2(N)回
－平均log2(N)回以下
Log2(N)
に比例
効率を比べる一般的な記法

BigO記法

BigO記法は、その名の通り、大文字のOを使
いますが、order(次数)の意味です。
bigO記法
Nに比例
O(N)
Log2(N)に比例
O(LogN)
Nの２乗に比例
O(N^2)
BigOのグラフ化
40
35
30
O(N)
O(N＾２)
O(logN)
O(1)
25
20
15
10
5
0
1
2
3
4
5
6
7
8
9 10 11 12 13
課題

実行するプログラムを配りますが、それに
は、コメントが一つも書いてありません。


適切なコメントをつけて提出しなさい。
プログラムを動かして、リニアサーチとバイ
ナリサーチの速さを比べてみなさい。Nの
数は最低1000,10000,20000,30000の４
種類で比べなさい。

結果と考察を提出しなさい。
提出方法



[email protected]宛て。
今回はソースのほかに、
実行結果、考察を書いて送ってください。
Subjectはログイン名を必ず書いてください。



ex) t96844ym
余計な[]などをつけないでください。
水曜まで。

Download Report