第８回　検索とその効率

第８回　検索とその効率

～効率の良いプログラムとは？～

学習目標

 効率が考慮されたプログラムが書ける

 効率の悪いプログラムを使うとどうなるか 説明できる

 効率を指標 (BigO 記法 ) を使って説明でき る

 バイナリサーチを Java で実装できる

 アルゴリズムをオブジェクトにしたプ ログラムが書ける

8.1 プログラムと効率



8.1.1

る？



8.1.2



8.1.3



8.1.4

8.1.1 プログラムの

効率が悪いとどうなる？

 品質の高いプログラムって？

 正しさ

 使いやすさ

 再利用性

 可読性（読みやすさ）

 効率（速さ）

効率が悪いとどうなるか？

 １万人の社員がいる会社があります。

 ログインするために社員番号でパス ワードを検索します。

 １人の検索に

0.

こたえ :

１分で６００人だから

10000/600=16.66 分　　　→大変だ！

今回考えること

 今回はたくさんの商品種類を取り扱います

 １万個の商品種類

 １０万個の商品種類

 現実の自動販売機ではありえませんが、コ ンピュータの自動販売機ならできます

 例えば、 WEB でソフトやゲームを販売する場 合。

8.1.2 性能を測るプログラム

 今回、次回は配列実装版だけ扱います

（例題

8-1

 ItemTypeArrayList→ ItemTypeList

時間を計る方法

 前回のプログラムは意味が明確でない

 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;

追加の時間を測る

public static void main(String[] args) {

StopWatch sw = new StopWatch();// ストップウオッチをインスタンス化

ItemTypeList itemTypeList = new ItemTypeList();// 配列版をインスタンス化 int addItemTypeId = 10000;// 商品種類を追加 / 検索する数

// 商品種類を追加する

sw.start();// ストップウオッチをスタート // 指定された回数追加する

for(int i=0; i<addItemTypeId; i++){

itemTypeList.add(new ItemType(i, "商品種類 "+i,120));

}

sw.stop();// ストップウオッチを止める

long time = sw.getTime();// かかった時間

System.out.println(" 追加にかかった時間は "+time+" ミリ秒です ");

}

ストップウオッチを スタート

1 万回 ストップウオッチを停止追加

8.1.3 効率の

計測結果についての考察



1

(Pentium700MHz

0.7

)

 ですが、

2

2.8

10

何故か考えてみましょう！

if 文の回数を調べる



add

if



1

10

/**

* 商品種類を追加する

*/ public void add(ItemType addItemType){

// 商品種類が入っていない箱を探す

for(int i=0; i<ARRAY_SIZE; i++){

if(itemTypeArray[i] == null){// 入っていない itemTypeArray[i] = addItemType;// 書き込む break;

} } }

計算方法



1

1



2

1

2

3



3

1

2

3

6



100

1+2+...+100

=(1+100)×50 = 5050



N

(1+N)×N/2

=

N^2/2

10 万要素追加に かかる時間予測

 10000 個のとき

約 10000×10000 / 2

= 50,000,000 回（５千万回 )

約 0.7 秒

 100000 個のとき

約 100000×100000 / 2

= 5,000,000,000 回 (50 億回 ) 　　　　　　　　　 　　　　　　　 おそらく 70 秒

8.1.4 追加の効率を上げる

 追加する番地を覚えておけばよい

 変数に size を加えます

//ItemTypeArrayList クラス

public class ItemTypeArrayList implements …{

private ItemType[] itemTypeArray = … private int size = 0;

… }

例題8-2

(ItemTypeList.java)

効率のよい追加のプログラム

public class ItemTypeArrayList implements ItemTypeList{

private ItemType[] itemTypeArray;// 商品種類を保存する配列 private int size = 0;// 現在の要素数

/**

* 商品種類を追加する

*/ public void add(ItemType addItemType){

itemTypeArray[size] = addItemType;// 空の箱から順に書き込む size++;// 要素数を 1 つ増やす

} … }

if 文がなくなった！

一つ追加したら、要素数を一つ増やします

削除のプログラムも変更

　 // 商品種類を削除するメソッド

public void delete(int deleteId){

int i=0;// ループの回数を保存する for(i=0;i<size;i++){

if(itemTypeArray[i].getId() == deleteId){// 見つかった

itemTypeArray[i] = null;//見つかったら、削除する（実は不要）

break;

} }

// 残りの要素をシフトする for(;i<size-1;i++){

itemTypeArray[i] = itemTypeArray[i+1];

}

size--;

}

一つ削除したら、要素数を一つ減らします

検索、削除の

プログラムも少し効率化

// 商品種類を検索するメソッド

public boolean search(int num){

for(int i=0;i<ARRAY_SIZE;i++){

if(itemTypeArray[i] != null){

if(itemTypeArray[i].id == num){

return true;

} } }

return false;

}

// 商品種類リスト種類を検索するメソッド public boolean search(int num){

for(int i=0;i<size;i++){

if(itemTypeArray[i].id == num){

return true;;

} }

return false;

}

入っている分だけ検索 配列全部を検索

null チェック

size 導入前 size 導入後 必要なし

速くなったかな？

 実験結果

 1 万個 (Pentium700MHz) で 0.08 秒！

2 万個でも 0.14 秒です

 これで運用でも耐えられそうです

8.2 検索アルゴリズム



8.2.1



8.2.2



8.2.3

8.2.1 検索の効率を考える

 検索の実験結果

 1 万個－ 2 ． 5 秒

 2 万個－ 20 秒

 これでは実用に耐えません

if 文の実行回数を調べる

 例によって

if

// 商品種類を検索するメソッド

public boolean search(int searchId){

for(int i=0;i<size;i++){

if(itemTypeArray[i].getId() == searchId){

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

ですが、実際にやってみると、７分ぐらい かかります。これはインスタンスにアクセ スのオーバーヘッドが大きくなるためです

8.2.2 リニアサーチ

 前回までの方法を「リニアサーチ」と いいます。

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

4 5 6 7 8 9 10

3 2

1

９を探す場合

[10]

11

あった！

8.2.3 バイナリサーチ

 バイナリサーチ

 配列の中身がソート済み（順番に並んでい る）の場合に有効

 今回は for 文で順番に追加されているのでソー ト済みになっています

バイナリサーチの考え方 (1)

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

4 5 6 7 8 9 10

3 2

1

９を探す場合

[10]

11

① まず、真ん中を探します。

ちがった！

② 違った場合も、探す範囲は半分に絞られます。

（数が少なかったら右半分、逆なら左半分にあります。）

９は６より大きいから、

バイナリサーチの考え方 (2)

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

4 5 6 7 8 9 10

3 2

1

９を探す場合

[10]

11

③ 次に、その範囲の中のまた真ん中を探します。

ちがった！

④ それを見つかるまで繰り返します。

９は８より大きいから、

この範囲に絞られる

① バイナリサーチの実装

// バイナリサーチをするメソッド

public boolean search(int searchId){

int lower = 0;// 探す配列の範囲の最小値

int upper = size-1;// 探す配列の範囲の最大値 int center;// 次に調べるべき配列の番地

while(true){

center = (lower + upper)/2;// 次に調べるのを範囲の真中に設定 if(itemTypeArray[center].id == searchKey){

return true;// 見つかった }else if(lower > upper){

return false;// 見つからず、かつ、もう調べる範囲がなくなった }else{

// 見つからないので、次に調べる範囲を狭める

if(itemTypeArray[center].id < searchKey){

lower = center +1;// 範囲を右半分にする }else{

upper = center -1;// 範囲を左半分にする }

} }

例題8-3

(ItemTypeList.java)

② バイナリサーチの効率

 例えば、

100

リニアサーチの場合

比較の回数は　　　－最小の場合で１回

　　　　　　－最大の場合で１００回 　　　　　　－平均５０回

バイナリサーチの場合

比較の回数は　　　－最小の場合で１ 回　　　　　　－最大の場 合で７回　　　　　　－平均７回 以下

要素数 比較最大回数

10 10

100 100

1000 1000

10000 10000

100000 100000

1000000 1000000

10000000 10000000

リニアサーチ バイナリサーチ 2

7 10 14 17 20 24

バイナリサーチの効率（２）

バイナリサーチの効率（３）

バイナリサーチ

の比較回数 検索できる範囲

1 2

2 4

3 8

4 16

5 32

6 64

7 128

0 1

2^ 比較回数

ようするに

「２の巾乗」

が検索できる範囲 になる。

２の巾乗を逆計算する

 問題：

100

答え log2(100) = 6.644

切り上げて 7 回

8.3 効率を比較する



8.3.1 BigO

検索の効率を比較する



N

リニアサーチの場合

比較の回数は　　　－最小の場合で 1 回

　　　　　　－最大の場合で N 回 　　　　　　－平均 N/2 回

バイナリサーチの場合

比較の回数は　　　－最小の場合で１回 　　　　　　－最大の場合で log2(N) 回

　　　　　　－平均 log2(N)

N に比例

Log2(N) に比例

効率を比べる一般的な記法



BigO

 BigO 記法は、その名の通り、大文字の O を使いますが、 order( 次数 ) の意味です。

O(N)

bigO 記法

O(LogN) O(N^2)

N に比例

Log2(N) に比例 N の２乗に比例

BigO のグラフ化

0 5 10 15 20 25 30 35 40

1 2 3 4 5 6 7 8 9 10 11 12 13

O(N) O(N )＾２ O(logN) O(1)

8.4 アルゴリズムを

比較するプログラムの設計

 リニアサーチとバイナリサーチを比較 するプログラムの設計をしましょう

 リニアサーチとバイナリサーチを使い分け ることができる設計にしたい

 どんなプログラムを書いたらよいです か？

案Ⅰ：メソッドを分ける

 メソッド分けするのは基本

I temTypeLi st + add()

+ l i nearSearch() + bi narySearch()

案Ⅱ：ポリモーフィズム

 ポリモーフィズムを利用してもできそ うです

I t emTypeBi narySear ch Li st

+ add( ) + sear ch( )

I t emTypeLi near Sear ch Li st

+ add( ) + sear ch( ) I t emTypeLi st

+ add( ) + sear ch( )

案Ⅲ： アルゴリズムをオブジェクト

に

 アルゴリズムだけをクラスにする方法

Li near Sear ch + sear ch( )

I t emTypeAr r ayLi st + add( )

+ sear ch( ) + di spl ay( )

Bi nar ySear ch + sear ch( )

さらにポリモーフィズムを使 う

 抽象クラスに対してプログラムすれば

、オブジェクトでアルゴリズムの切り 替えが可能になりますね

Li near Sear ch + sear ch( )

Bi nar ySear ch + sear ch( )

Sear chAl gol i t hm + sear ch( )

I t emTypeLi st + add( )

+ sear ch( )

+ di spl ay( ) 11 11

難しい

 それぞれに利点と欠点がある

 余裕のある人は、議論してみましょう