酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2012年6月28日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html.

Presentation on theme: "酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2012年6月28日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html."— Presentation transcript:

1 酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造 2012年6月28日

2 クイックソート 基準値を決定 10 1 8 3 15 5 32 12 6 24 基準値を決定 10 8 3 5 1 6 15 32 12 24 ＜ 10 整列済み 基準値を決定 5 15 ＜ 3 1 8 6 12 32 24 10 5 15 ＜ 3 1 8 6 12 32 24 10 10 1 8 3 15 5 32 12 6 24

3 public class QuickSort {
public static <E extends Comparable<E>> int sort(E[] array) { return sort(array, 0, array.length - 1); } private static <T extends Comparable<T>> T getPivot(T[] array, int start, int end) { return array[start]; private static <T extends Comparable<T>> int sort(T[] array, int start, int end) { int n = 0; if ((end - start) < 1) return n; // データが1個以下のとき、ソート完了 T pivot = getPivot(array, start, end); int left = start; // start以上、left未満が仕分け済 int right = end; // rightより上、end以下が仕分け済 split: while (left <= right) { for (; left <= right; left++) { n++; if (pivot.compareTo(array[left]) > 0) continue; // pivot以上の値を探せた for (; left <= right; right--) { if (pivot.compareTo(array[right]) < 0) continue; // pivot以下の値を探せた if (left < right) { T temp = array[left]; array[left++] = array[right]; array[right--] = temp; continue split; } else break split; } } } n += sort(array, start, left - 1); n += sort(array, right + 1, end); return n; }}

4 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 27
private final static String[] test_data_string = { "東京", "北海道", "高知", "兵庫", "鹿児島", "沖縄", "青森"}; private final static Integer[] test_data_int = { 47, 18, 8, 7, 2, 4, 9, 0, 72, 88, 2, 5, 9, 10}; public static void main(String[] args) { int n; StringBuffer sb = new StringBuffer(); String[] data1 = test_data_string.clone(); n = sort(data1); for (String e : data1) { sb.append(e).append(", "); } sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n'); Integer[] data2 = test_data_int.clone(); n = sort(data2); for (Integer e : data2) { System.out.print(sb.toString()); 兵庫, 北海道, 東京, 沖縄, 青森, 高知, 鹿児島, compareTo()を呼んだ回数 27 0, 2, 2, 4, 5, 7, 8, 9, 9, 10, 18, 47, 72, 88, compareTo()を呼んだ回数 79

5 クイック ソート （最悪の 場合） 32 24 15 12 10 8 6 5 3 1 5 24 15 12 10 8 6 3 1 ＜ 32 5 15 12 10 8 6 3 1 ＜ 32 24 5 12 10 8 6 3 1 ＜ 15 32 24 5 10 8 6 3 1 ＜ 15 12 32 24 5 8 6 3 1 ＜ 10 15 32 12 24 5 6 3 1 ＜ 10 8 15 32 12 24 5 3 1 ＜ 10 8 15 32 12 6 24 3 1 ＜ 10 8 15 5 32 12 6 24 1 ＜ 10 8 3 15 5 32 12 6 24 10 1 8 3 15 5 32 12 6 24

6 再帰的アルゴリズム 再帰は重要なアルゴリズムの概念である．
とくに参照型を用いた柔軟なデータ構造を扱う場合には，基本的に再帰的アルゴリズムを用いるしかない． ここでは，再帰的アルゴリズムを詳細に検討し，その動作の理解をする

7 漸化式からの計算 階乗 フィボナッチ数列 いずれも再帰的に関数を呼ぶ形に書ける 再帰呼び出しの場合 f(0)やf(1)といった 　　　　　数列の最初の値のところで停止

8 末尾再帰なので再帰呼び出しをループに変換することは容易
階乗を求めるプログラム public class Factorial { // 再帰版 public static int factorial(int aTarget) { System.out.println("factorial(" + aTarget + ")に入ります"); if(0 == aTarget){ System.out.println("factorial(0) から出ます: 1"); return 1; } int total = aTarget * Factorial.factorial(aTarget - 1); System.out.println("factorial(" + aTarget + ") から出ます: " + total); return total; // ループ版 public static int factorialWithoutRecursion(int aTarget) { int total = aTarget; for(int count = aTarget - 1; 0 < count; count--){ total *= count; 末尾再帰なので再帰呼び出しをループに変換することは容易

9 f(0)から順にたどれば結果を求めることができる
フィボナッチ数を求めるプログラム public class Fibonatti { // 再帰版 public static int fibonatti(int aTarget) { System.out.println("fibonatti(" + aTarget + ") に入ります"); if((0 == aTarget) || (1 == aTarget)){ System.out.println("fibonatti(" + aTarget + ") から出ます: 1"); return 1; } int total = fibonatti(aTarget - 2) + fibonatti(aTarget - 1); System.out.println("fibonatti(" + aTarget + ") から出ます: " + total); return total; // ループ版 public static int fibonattiWithoutRecursion(int aTarget) { int old1 = 1, old2 = 1, total = 0; for(int count = 2; count <= aTarget; count++){ total = old1 + old2; old2 = old1; old1 = total; f(0)から順にたどれば結果を求めることができる f(x)に必要とされるのはf(x-1)とf(x-2)なので変数を2つ追加すれば足る

10 [sakai@star 13]$ java FactorialTest
720 factorial(6)に入ります factorial(5)に入ります factorial(4)に入ります factorial(3)に入ります factorial(2)に入ります factorial(1)に入ります factorial(0)に入ります factorial(0) から出ます: 1 factorial(1) から出ます: 1 factorial(2) から出ます: 2 factorial(3) から出ます: 6 factorial(4) から出ます: 24 factorial(5) から出ます: 120 factorial(6) から出ます: 720 13]$ 13]$ java FibonattiTest 8 fibonatti(5) に入ります fibonatti(3) に入ります fibonatti(1) に入ります fibonatti(1) から出ます: 1 fibonatti(2) に入ります fibonatti(0) に入ります fibonatti(0) から出ます: 1 fibonatti(2) から出ます: 2 fibonatti(3) から出ます: 3 fibonatti(4) に入ります fibonatti(1) に入ります fibonatti(1) から出ます: 1 fibonatti(2) から出ます: 2 fibonatti(3) に入ります fibonatti(2) に入ります fibonatti(0) に入ります fibonatti(0) から出ます: 1 fibonatti(3) から出ます: 3 fibonatti(4) から出ます: 5 fibonatti(5) から出ます: 8 13]$

11 通りがけ順の走査 二分木を次のルールで走査 自分の左部分木をたどる 自分を訪ねる 自分の右部分木をたどる 親の頂点に戻る
二分探索木を走査すると 横倒しの木を表示できる 29 29 20 20 32 32 14 14 24 24 30 30 48 48 7 7 19 19 21 21 31 31

12 木の根が左にある、 左から右へ生えている木を表示するプログラム
public void printTreeRecursive() { this.printTreeRecursive(this.root, 0); } private void printTreeRecursive(MyNode aLocalRootNode, int depth) { if(null == aLocalRootNode) return; this.printTreeRecursive(aLocalRootNode.getRight(), depth+1); for(int i=0; i < depth; i++){ System.out.print("\t"); System.out.println(aLocalRootNode.getData().toString()); this.printTreeRecursive(aLocalRootNode.getLeft(), depth+1); 再帰呼び出し 再帰呼び出し版 木の根が左にある、 左から右へ生えている木を表示するプログラム (29, "リンゴ") (20, "ミカン") (14, "サクランボ") (32, "バナナ") (30, "イチゴ") (24, "ブルーベリー") ( 7, "グレープフルーツ") (21, "レモン") (48, "メロン") (31, "スイカ") (19, "ナシ") (17, "モモ") (23, "マンゴー") (28, "ブドウ") (48'メロン) (32'バナナ) (31'スイカ) (30'イチゴ) (29'リンゴ) (28'ブドウ) (24'ブルーベリー) (23'マンゴー) (21'レモン) (20'ミカン) (19'ナシ) (17'モモ) (14'サクランボ) (7'グレープフルーツ)

13 this.printTreeRecursive((17, "モモ"), 4); 右部分木探索中
(48'メロン) (32'バナナ) (31'スイカ) (30'イチゴ) (29'リンゴ) (28'ブドウ) (24'ブルーベリー) (23'マンゴー) (21'レモン) (20'ミカン) (19'ナシ) (17'モモ) (14'サクランボ) (7'グレープフルーツ) this.printTreeRecursive((17, "モモ"), 4); 右部分木探索中 this.printTreeRecursive((23, “マンゴー”), 4); 左部分木探索中 this.printTreeRecursive((23, "マンゴー"), 4);出力 this.printTreeRecursive((23, "マンゴー"), 4); 右部分木探索中 this.printTreeRecursive((17, “モモ”), 4); 左部分木探索中 this.printTreeRecursive((17, "モモ"), 4);出力 this.printTreeRecursive((31, “スイカ”), 3); 左部分木探索中 this.printTreeRecursive((28, "ブドウ"), 3);出力 this.printTreeRecursive((31, "スイカ"), 3);出力 this.printTreeRecursive((19, "ナシ"), 3);出力 this.printTreeRecursive((31, "スイカ"), 3); 右部分木探索中 this.printTreeRecursive((19, “ナシ”), 3); 左部分木探索中 this.printTreeRecursive((28, "ブドウ"), 3); 右部分木探索中 this.printTreeRecursive((28, “ブドウ”), 3); 左部分木探索中 this.printTreeRecursive((19, "ナシ"), 3); 右部分木探索中 this.printTreeRecursive(( 7, "グレープフルーツ"), 3);出力 this.printTreeRecursive(( 7, "グレープフルーツ"), 3); 右部分木探索中 this.printTreeRecursive(( 7, “グレープフルーツ”), 3); 左部分木探索中 this.printTreeRecursive((21, “レモン”), 3); 左部分木探索中 this.printTreeRecursive((21, "レモン"), 3);出力 this.printTreeRecursive((21, "レモン"), 3); 右部分木探索中 this.printTreeRecursive((24, “ブルーベリー”), 2); 左部分木探索中 this.printTreeRecursive((48, "メロン"), 2); 右部分木探索中 this.printTreeRecursive((24, "ブルーベリー"), 2); 右部分木探索中 this.printTreeRecursive((14, "サクランボ"), 2); 右部分木探索中 this.printTreeRecursive((30, "イチゴ"), 2); 右部分木探索中 this.printTreeRecursive((14, “サクランボ”), 2); 左部分木探索中 this.printTreeRecursive((30, “イチゴ”), 2); 左部分木探索中 this.printTreeRecursive((24, "ブルーベリー"), 2);出力 this.printTreeRecursive((48, "メロン"), 2);出力 this.printTreeRecursive((30, "イチゴ"), 2);出力 this.printTreeRecursive((14, "サクランボ"), 2);出力 this.printTreeRecursive((48, “メロン”), 2); 左部分木探索中 this.printTreeRecursive((20, “ミカン”), 1); 左部分木探索中 this.printTreeRecursive((20, "ミカン"), 1); 右部分木探索中 this.printTreeRecursive((20, “ミカン”), 1); 出力 this.printTreeRecursive((32, “バナナ”), 1); 左部分木探索中 this.printTreeRecursive((32, "バナナ"), 1); 右部分木探索中 this.printTreeRecursive((32, “バナナ”), 1); 出力 this.printTreeRecursive((29, “リンゴ”), 0); 左部分木探索中 this.printTreeRecursive((29, "リンゴ"), 0);出力 this.printTreeRecursive((29, "リンゴ"), 0); 右部分木探索中

14 再帰呼び出しの除去 再帰呼び出しでは同じ関数を呼ぶ 一時変数は、名前が同じだけで、実体は別 最も最後に呼ばれた関数が最初に抜ける
実体は関数エントリ時に確保される 関数から抜けるときに開放される 最も最後に呼ばれた関数が最初に抜ける つまりLIFO、スタック 一時変数や途中経過を退避する領域が あればループにより実現できる

15 退避すべきデータ 部分木の根 今何をしているか？ ループに変換するにはこれをスタックに退避
再帰呼び出しでは、プログラムの流れとして 保持していた。つまりCPUのプログラムカウンタ 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る ループに変換するにはこれをスタックに退避 探索中の頂点の深さは計算できるので退避不要

16 木の根が左にある、 左から右へ生えている木を表示するプログラム
public void printTreeLoop() { MyNode node, currentRootNode = this.root; int depth = 0, todo = 0; Stack stack = new Stack(); while(true){ switch(todo++){ case 0: node = currentRootNode.getRight(); if(node != null){ stack.push(currentRootNode); currentRootNode = node; stack.push(new Integer(todo)); todo = 0; depth++; } break; case 1: for(int i=0; i < depth; i++){ System.out.print("\t"); System.out.println(currentRootNode.getData().toString()); // 続く… ループ版 木の根が左にある、 左から右へ生えている木を表示するプログラム

17 一時退避場所にはスタックを使っている 次にすべきこと、部分木の根、を保持する 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る
case 2: node = currentRootNode.getLeft(); if(node != null){ stack.push(currentRootNode); currentRootNode = node; stack.push(new Integer(todo)); todo = 0; depth++; } break; case 3: if(stack.empty()){ return; todo = ((Integer)stack.pop()).intValue(); currentRootNode = (MyNode)stack.pop(); depth--; 一時退避場所にはスタックを使っている 次にすべきこと、部分木の根、を保持する 右部分木の訪問 自分の値の表示 左部分木の訪問 親の頂点に戻る

18 JDK5での拡張forループ 配列・リスト・Setといった集合を楽に扱うための拡張 for(要素型名 要素型変数: 集合型変数){
for(要素型名　要素型変数: 集合型変数){ for文本体; } ListやSetや配列を表す変数 public static void main(String[] args) { int n; StringBuffer sb = new StringBuffer(); String[] data1 = test_data_string.clone(); n = sort(data1); for (String e : data1) { sb.append(e).append(", "); } sb.append("\ncompareTo()を呼んだ回数 ").append(n).append('\n'); System.out.print(sb.toString()); 総称型については、次回にでも…