プログラミングゼミ短■ (第6回スタートアップゼミ？) 2012年9月11日(火) M1伊藤創太a 、データ構造とアルゴリズム駒場教養の「情報科学」(理系準必修？)のカリキュラム・数の計算と関数・条件分岐と繰り返し・関数から計算へ・アルゴリズムと計算量•数値計算・パターン認識・レコードとオブジェクト・再帰データ構造・いろいろなプログラミング言語ih ータ構造とアルゴリズムプログラムの実装データ構造データをどのようにコンピュータのメモリに並べるかという方式・形式アルゴリズムデータを操作する手続きアルゴリズムの理解→プログラミング適切なアルゴリズム・データ構造の選択→計算の高速化・汎用化探索：配列データからの検索(例)郵便番号リスト（ソート済み）からの住所の検索郵便番号1130033の住所は？線形探索配列の順番に見つかるまで調べていく0010000北海道札幌市北区・・・ちがう！ ・・・ちがう！ ・・・ちがう！ ➥ ···あった！ 1130032東京都文京区弥生1130033東京都文京区本郷1130034東京都文京区湯島9998531山形県飽海郡遊佐町菅里知りたい答えが見つかったら、探索終了。
import java.io.*; //java.ioパッケージを使うpublic class Main { public static void main(String[] args) { //データをうまく読み込めるときtry { String inputfile = “./input/input-sep1.csv”;     //インプットファイル名//データ数は123325(今回は固定) int dataN = 123325; BufferedReader br = new BufferedReader(new FileReader(inputfile)); //1行ごとに読み込む変数を用意String line = null; //郵便番号表の格納配列String[][] yubin = new String[dataN][2]; //郵便番号データ格納に必要なポインタint i = 0; //最終行になるまで読み込むwhile ((line = br.readLine()) != null) { / /カンマ区切りで分割String[] splitline = line.split(“,”); //1列目に郵便番号yubin[i][0] = splitline[0]; //2列目に住所yubin[i][1] = splitline[1]; i++; } br.close;); System.out.println( addressmatch("1130033", yubin) );郵便番号データの格納採案実行結果表示parseint
} / /データをうまく読み込めないときcatch( IOException e ) {                } System.out.println(“データ入力失敗”); → } static String addressmatch(String num, String[][] yubin) { for (int i = 0; i < yubin.length; i++ ){          //順番に検索対象と一致するか調べるif(Integer.parseInt(yubin[i][0]) == Integer.parseInt(num)){ //一致したら住所を返すreturn yubin[i][1]; → } return “なし”; } }実行結果東京都文京区本郷例外別詳緑形緑緑アルゴリズム//一致するものがない場合は「なし」を返す二分探索前半と後半にわけて絞っていき、検索対象を見つけ出す0010000北海道札幌市北区6078402京都府京都市山科区御陵黒岩6078403京都府京都市山科区御陵大岩61662件9998531山形県飽海郡遊佐町菅里0010000北海道札幌市北区3540015埼玉県富士見市東みずほ台3540016埼玉県富士見市榎町30381件6078402京都府京都市山科区御陵黒岩1つに絞られるまで繰り返す。データは昇順にソートされている必要がある。
二分探索アルゴリズムの実装
・二分探索法で郵便番号リストから住所を検索する・郵便番号がString型になっていることに注意（0から始める番号がある都合上。purseIntやvalueOfでint型に直せる） (ヒント) ·探索範囲の上限と下限の変数を導入することとして、 upper=yubin.length、lower=0のようにして始めて、upperとlowerが一致したらそれが答え・・・みたいな感じ。 static String addressmatch2(String num, String[][] yubin) { ? ? ? ? } 2つの探索方法の比較計算時間（同一の1000件の検索を行った所要時間）線形探索・・・4.674秒二分探索・・・0.087秒→二分探索の方が速いアルゴリズムの計算量をどう評価するか計算時間はコンピュータやコンパイラの性能によって違う使うデータによっても計算時間は違う→計算の繰り返し処理の回数の、最大回数で比較→データ数による繰り返し回数の増加でだいたい計算量の差がわかる計算量の評価– O表記法あるアルゴリズムについてn個のデータに対して必要な計算量のオーダーを示す。線形探索の場合・・・最悪の場合、1番目からn番目まで全て比較する→ O(n) (最良の場合は1回で済むが、最大計算量で比較する)二分探索の場合・・・比較を行う回数は、n個のデータのときlog₂n回→ O(log₂n)計算量の評価– O表記法データ数nが増えると、オーダーの違いによる差は大きくなる
おもなデータ構造・配列・ハッシュテーブル・連結リスト・二分木・グラフ···int[]など···Hashmap、Hashtableクラス(前回プログラミングゼミ参照)データ構造により計算量が大きく変わることも多いlif配列で表す二分木木の構造と配列の要素を対応させてデータを格納する何が嬉しいか親子関係を配列で表せるどの部分でも配列添え字の関係が同じヒープ構造親の要素は子の要素より小さい木の根の要素は最小の要素何が嬉しいか(8)常に根がその木の中の最小値を格納している→最小値取り出しの計算量はO(1)要素の挿入木の最後（配列の最後に追加）親と比較して親が大きければ入れ替え—ブホ要素の取り出し最後の要素を先頭に入れ、子の方が小さければ入れ替え
import java.io.*; import java.util.ArrayList; //java.ioパッケージを使う//ArrayListを使うpublic class Main { public static void main(String[] args) { ArrayList<Integer> heapnode = new ArrayList<Integer>(); insert(3,heapnode); //ここでは3,2,1を挿入してみているinsert(2,heapnode); insert(1,heapnode); System.out.println(draw(heapnode));    //根の要素を取り出して結果を表示} static void insert(int x, ArrayList<Integer> heap){  //新しい要素の挿入の関数//配列の最後に入れるheap.add(x); int n = heap.size() - 1; //親ノード((n-1)/2)との比較while(heap.get((n-1) / 2) > heap.get(n)){ //要素の入れ替えint a = heap.get((n-1) / 2); heap.set((n-1) / 2, heap.get(n)); heap.set(n, a); n = (n-1) / 2; } }
//根の要素の取り出しの関数static int draw(ArrayList<Integer> heap){ //いったん根の要素を保管int minimum = heap.get(0); //最後尾の要素を根に持ってくるheap.set(0, heap.get(heap.size() - 1)); //最後尾要素を消去heap.remove(heap.size() - 1); int n = 0; while(2*n+1 < heap.size() && heap.get(n) > heap.get(2*n+1)){ //子(左側)との比較int a = heap.get(n); heap.set(n, heap.get(2*n+1)); heap.set(2*n+1, a); n = 2*n+1; } while(2*n+2 < heap.size() && heap.get(n) > heap.get(2*n+2)){ //子(右側)との比較int a = heap.get(n); heap.set(n, heap.get(2*n+2)); heap.set(2*n+2, a); n = 2*n+2; } return minimum; } }
//根の要素の取り出しの関数static int draw(ArrayList<Integer> heap){ //いったん根の要素を保管int minimum = heap.get(0); //最後尾の要素を根に持ってくるheap.set(0, heap.get(heap.size() - 1)); heap.remove(heap.size() - 1); //最後尾要素を消去int n = 0; while(2*n+1 < heap.size() && heap.get(n) > heap.get(2*n+1)){ //子(左側)との比較int a = heap.get(n); heap.set(n, heap.get(2*n+1)); heap.set(2*n+1, a); n = 2*n+1; } while(2*n+2 < heap.size() && heap.get(n) > heap.get(2*n+2)){ //子(右側)との比較int a = heap.get(n); heap.set(n, heap.get(2*n+2)); heap.set(2*n+2, a); n = 2*n+2; } return minimum; } }
▼ダイクストラ法グラフの最短距離･経路を求めるアルゴリズムダイクストラ(蘭)が1958年に考案(例) AからEまで行く最短距離は？そしてその経路は？ 0リンクのコストOダイクストラ法▼ダイクストラ法の考え方くわかった最短経路から確定させていく> 【Step1】出発点から各点の距離の暫定値を設定(赤色:確定済のノード・値、灰色:未確定)出発点AからAまでの！ :距離は0で確定! Aから各点までの距離の! |暫定値を書き込む場所|
【Step2】確定済の点から経路をたどり暫定値を更新』例えば現時点でのAからDの！ :最短距離は4 【Step3】未確定の中で最小距離の点を確定させるA-Cの最短経路も確定｜
【Step4】確定済の点から経路をたどり暫定値を更新A-Dの4よりA-C-Dの3の方が|小さいため、3に更新【Step5】未確定の中で最小の点を確定させる
【Step6】確定済の点から経路をたどり暫定値を更新! A-C-Dの3よりA-B-Dの5の方が¡大きいため更新されず【Step7】未確定の中で最小の点を確定させる
【Step8】確定済の点から経路をたどり暫定値を更新¦A-C-Eの5よりA-C-D-Eの4の方が小さいため更新【Step9】未確定の中で最小の点を確定させる完成| AからEの最短距離は4で!経路はA-C-D-Eダイクストラ法アルゴリズムの実装・ダイクストラ法をjavaで実装・まずはやってみる、可能であればデータの構造やアルゴリズムの工夫で高速化基本的には、nodeとlinkについてそれぞれクラスの型を作って配列で管理、逐次探索するArrayListダイクストラ法アルゴリズムの実装高速化のヒントとして・・・ ·次に探索する可能性のあるノードをヒープ木にするとか・Nodeのデータの中に次に接続可能なNodeを格納して、リンクの長さは行列で管理するとか・・・ ID:"0"探索済:0距離:∞次ノード:1,4,7