game-engineer:classes:2022:game-programing-1:first-term:9:9-09-12

探索(Searching)

・有限のデータの中から、目的のデータを探す事 

	例：配列を走査して、目的の値を見つける
	　 int iarray[10]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0};
	                   0  1  2  3  4  5  6  7  8  9 ← index
           キー値６を探せ！　indexの０からたどっていき、index7でキー値6を見つけたよ。
　　　　　　探索結果　＝＞　iarray[7]が６に一致
  • 著名な探索アルゴリズム
    • 線形探索
    • 二分探索
    • ハッシュ法

性能（場合による）＝　探索の速さ　＝　処理の少なさ ⇐ 繰り返し数と比較数
ハッシュ法 ＞　二分探索　＞　線形探索

データ形式：
配列：

配列＝＞同じ型のデータが複数あり、名前とインデックスで表現されたもの
(double a[5]; => a[0] ～a[4]がdouble型で用意される）

レコード：

　　 （キー項目）|  （キーに付属した情報)
	商品番号 |     商品名      | 単価
	  A001   |  ハンバーガー   | 200 
	  A003   | チーズバーガー　| 260    <=　レコード形式（固定幅データ）
	　A005   | エッグサンド    | 240
          A007   | アイスコーヒー　| 120
          …　　 |    　…　	   |  …

表＝テーブル(table)

「線形探索法」(逐次探索法：Linear Search Algorithm)

・データ列（レコード、配列など）を先頭から順番に一個ずつ逐次、キー値（探索値）と比較して、 　見つかるまで走査する方法

　例題６－１ 

　　　レコード
      index| CarNo |  CarName　　
        0  | 1003  | "MarkⅡ"
        1  | 1012  | "Chaser"
        2  | 1053  | "Mr2"
        3  | 1031  | "Rx-7"
        4  | 1021  | "Minica"
        5  | 1075  | "Legacy"

　・CarNoで探して、車種名を出力する探索
	変数として必要なもの　→　indexをたどるためのカウンタ変数 i 
　　　　　　　　　　　　　　　　　探すCarNoを保存しておく変数（キー値＝探索キー）var=1053
	例）探索キーが１０５３で入力されたとき（P９２）　結果"Mr2"と表示される
	    
	    if(var == 1053 && i<=最大データ数)
	    {
               carNameを出力
   	    }

・番兵法 

	    if(var == 1024 && i<=最大データ数（Ｎ）)　//アルゴリズムとしては、比較回数は２
	    {
               carNameを出力
   	    }
   ・データが見つからなかったときは最大データ数Ｎｘ２回の比較が必要
　 ・最大データ数を１増やしておいて、最後に番兵を配置することで、比較回数を減らす作戦（ストラテジー）

　　  index| CarNo |  CarName　　
        0  | 1003  | "MarkⅡ"
        1  | 1012  | "Chaser"
        2  | 1053  | "Mr2"
        3  | 1024  | "Rx-7"
        4  | 1021  | "Minica"
        5  | 1075  | "Legacy"   
　　　  … |  … 　|   …   
        N  |  XXX  | "XXXXX"
       N+1 | 1024  | -------    
             ＝探索キー＝番兵

	while(var != 1024)　//アルゴリズムとしては、比較回数は１
	{
           carNameを出力
	   i = i + 1;
   	}
	
	if(i==N+1){
	   データが見つからなかったときの処理;
	}else{
	   データが見つかった時の処理
	}
	//(N+1) x 1 Nは０以上

ーーーーーーーーーーー【複合条件】ーーーーーーーーーーーーーーーーーーーーーーーーーー

・比較の時に複数の条件を組み合わせて真偽値を決める
i>0
i<=10
・ＡＮＤ →　且つ　　両方同時に成り立てば真　 C/C++では　&& (shift+6)
　　　　　　 例：ｘが０以上６未満（数学だと０≦ｘ＜６）
	　　　　 ｘが０以上　且つ　６未満　 x >= 0  &&  x < 6					

・ＯＲ　 →　又は　　どちらかが成り立てば真　 C/C++では　|| (shift+\(バックスペースの左）)
             例：xが０以下　または、ｘが６より大きい（数学だと x ≦ 0, x ＞ 6）
　						       x <= 0 || x > 6

・Ｎｏｔ　→　～でない　条件を否定して真偽を逆転させる
	     not(x>=0) ＝＞ x < 0と同値　　C/C++では　!(x >= 0) と書く
　　　　　　  !(x >= 0) == (x < 0)

剰余の演算子 % → x%3 xを３で割ったあまりが結果
割り切れる＝余りが０

変数int ｘにおいて、
・３で割り切れて、かつ５で割り切れる　x%3==0 && x%5==0  
・３で割り切れる、正ではない整数      !(x>=0) && x%3==0
				          x<0 && x%3==0
・３でも、５でも割り切れない	      !(x%3==0) && !(x%5==0)

このような複合条件が１度に書けるようになる。
ーーーーーーーーーーー【複合条件】ーーーーーーーーーーーーーーーーーーーーーーーーーーー

順次
選択（条件分岐）
繰り返し（継続条件、終了条件）　2%3==0 -> 2%3=2 -> 2==0? -> false 条件＝真偽値です。
・相手にしているデータ→整列済みデータ(昇順化、降順に並んだデータ）
サンプルデータ[3, 5, 6, 8, 12, 34, 36, 37, 45, 49] 
　　　　　　　 0  1  2  3   4   5   6   7   8   9
例）
・探索キー＝３７
サンプルデータ[3, 5, 6, 8, 12, 34, 36, 37, 45, 49] 
　　　　　　　 0  1  2  3   4   5   6   7   8   9
サンプルデータ[                34, 36, 37, 45, 49] 
　　　　　　　                  5   6   7   8   9
サンプルデータ[                34, 36, 37, 45, 49] 
　　　　　　　                  5   6   7   8   9
サンプルデータ[                34, 36, 37        ] 
　　　　　　　                  5   6   7  
サンプルデータ[                34, 36, 37　      ] 
　　　　　　　                  5   6   7  
サンプルデータ[               　　　　 37　      ]  37発見
　　　　　　　                  　　　　7

アルゴリズムの評価法

番兵法と比較回数とビッグオー記法

 int iarray[10]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0};
	         0  1  2  3  4  5  6  7  8  9 ← index
           キー値６を探せ！　indexの０からたどっていき、index7でキー値6を見つけたよ。
　　　　　　探索結果　＝＞　iarray[7]が６に一致
配列数を num
探索値を key
int i = 0;
while( i < num )　①条件その１：配列数はオーバーしていないか？
{
　iarray[i]はkeyですか？  ②条件その２：keyは見つかったか？
　　Yes： indexを出力（返す：ループを抜ける）
　　 No： 何もしない(i = i+1)
}

複合条件で一緒に書いてみよう！

while(i<num && iarray[i] != key )
{
	i = i+1;(i++;)	
}
if(i == num)
   Yes: keyは見つかってない
    No: return( i ); //iでkeyが見つかってループ抜けてる

これをさらに、スタイリッシュに書く！
 int iarray[10]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0};
	         0  1  2  3  4  5  6  7  8  9 ← index
 int   temp[11]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0, ???};
                 0  1  2  3  4  5  6  7  8  9  10 ← index

keyが見つかる場合
 keyを一番最後に代入します。
 int   temp[11]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0, 6};
                 0  1  2  3  4  5  6  7  8  9  10 ← index


while(iarray[i] != 6) //配列オーバーのチェックがいらなくなる　比較回数１/２
{
  i = i+1;(i++;)	
}
if(i == num)
   Yes: keyは見つかってない
    No: return( i ); //7でkeyが見つかってループ抜けてる

keyが見つかる場合
 keyを一番最後に代入します。
 int   temp[11]={2, 5, 8, 1, 4, 7, 3, 1, 9, 0, 6};
                 0  1  2  3  4  5  6  7  8  9  10 ← index


while(iarray[i] != 6) //配列オーバーのチェックがいらなくなる　比較回数１/２
{
  i = i+1;(i++;)	
}
if(i == num)
   Yes: keyは見つかってない //i==num (10)でループを抜けている
    No: return( i ); 

一般化
 keyを一番最後に代入します。
 int   temp[11]={2, 5, 8, 1, 4, 7, 3, 6, 9, 0, key}; temp[num-1]←key　番兵
                 0  1  2  3  4  5  6  7  8  9  10 ← index


while(iarray[i] != key) //配列オーバーのチェックがいらなくなる　比較回数１/２
{
  i = i+1;(i++;)	
}
if(i == num)
   Yes: keyは見つかってない
    No: return( i ); //iでkeyが見つかってループ抜けてる

「配列の最後に、番兵を置いておくことで線形探索の配列オーバーのチェックが必要なくなり、
各ステップでの比較が半分になる」

アルゴリズムの評価
　・早い（いろんな意味で速い、早い）
　　・少ないプログラムステップで終わる（CPUの動作ステップが少ない）
　・効率がいい（同じ動きをする者の中で一番コストが低い）
　　・メモリの使用量が少ない
　・一般性が高い（いつでも同じように動く）
　　・いつどんな状況でやっても安定して同じような結果を返す
　・理解のしやすさ（美しさ）
　　・誰でも実装できそうか？簡便で賢い方法か？

ビッグオー記法で大体のアルゴリズムの効率を表す

for(i=0 i<l;i++)
  for(j=0;j<m;j++)
    for(k=0;k<n;k++)
       //なんやかんや
  l=m=n=N  N*N*N  N^3の繰り返しの回数　O(N^3) Nの３乗に支配されてアルゴリズムが動く

for(i=0 i<l;i++)
  for(j=0;j<m;j++)
     //なんだかんだ
　   N*N  O(N^2) オーダN二乗のアルゴリズム

 for(j=0;j<m;j++)
　　　N回　O(N)のアルゴリズム

ハッシュ法
　　　１回　O(1)のアルゴリズム
　

基本情報技術者H14秋　午前　問１３

A[i](i=1～n) n個の要素があるよ
（１）A[] ={XX,XX,XX,XX ... XX}
    i=1～nまでを探索して、最小値の要素を探す
   min = A[0]
   min_i = 1;
   for(i=1;i<=n;i++)
    if(min < A[i]) ←比較
    {
            min = A[i];
            min_i = i;
     } 
　 swap(A[1], A[min_i]);

O(N)×O(N) = O(N^2)
①５回比較
|1 2 3 4 5  index  
|3 4 6 1 2  要素数5
min_i = 4
min = 1
swap(1,4)
②４回比較
1 |2 3 4 5  index  
1 |4 6 3 2  
min_i = 5
min = 2
swap(2,5) indexで交換
③３回
1 2 |3 4 5  index  
1 2 |6 3 4  
min_i = 4
min = 3
swap(3,4)
④２回
1 2 3 |4 5  index  
1 2 3 |6 4
min_i = 5
min = 4
swap(4,5)
1 2 3 4 |5  index  
1 2 3 4 |6

バブルソート
1 2 3 4 5  index  
3 4 6 1 2  要素数5
3 4 1 6 2  要素数5
3 4 1 2 |6  要素数5

3 4 1 2 |6  要素数5
3 1 4 2 |6  要素数5
3 1 4 2 |6  要素数5
3 1 2 |4 6  要素数5

3 1 2 |4 6  要素数5
1 3 2 |4 6  要素数5
1 2 |3 4 6  要素数5

1 2 3 4 6 最良　O(n)
 
6 4 3 2 1 最悪  O(n^2) ←平均計算量

選択ソート
最悪　最良　平均　O(n^2)←平均計算量

挿入ソート

書いてみて
最悪の場合
最良の場合
平均　O(n^2)←平均計算量

マージソート
最悪、最良、平均　O(n・log(n))

クイックソート
最悪　O(n^2) ソート済みに近い状態が遅い
最良　O(nlogn)　
平均　O(nlogn)
logの底は2又は１０
https://qiita.com/kokorinosoba/items/1c7400ca6c740fe9f1ee
https://karippu.com/stability_sort_algorithm/
  • game-engineer/classes/2022/game-programing-1/first-term/9/9-09-12.txt
  • 最終更新: 3年前
  • by root