投稿者: Hong Chen

Webアプリケーション作成（コーディング・テスト、デバッグ、仕上げ）、全員発表する

発表課題： オープンデータの取得と利用
使用言語：processing もしくは Java
発表時間：５分程度

課題：

オープンデータの取得と利用

1. オープンデータの材料選び
2. オープンデータの取得 (URL)
3. オープンデータの利用 (processing もしくは Java)
4. オープンデータ応用のWEB公開 (Google sitesに埋め込み)

ヒント：

これまで演習したプログラムの組み合わせが必要です。

nextbus, java参考例：

import java.util.Calendar;

class busapp{

        public static void main(String args[]){

                String[] data = {
                        "00:00",
                        "8:30",
                        "9:10",
                        "10:00",
                        "11:00",
                        "12:15",
                        "14:15",
                        "15:15",
                        "16:15",
                        "17:15",
                        "18:15",
                        "19:15",
                        "20:15",
                        "23:59"
                };

                Calendar calendar = Calendar.getInstance(); //現在（実行時点）時刻でCalendarのインスタンス生成
                int hourOfDay = calendar.get(Calendar.HOUR_OF_DAY);   // 0..23
                int minute = calendar.get(Calendar.MINUTE);      // 0..59

                int cnt = 0;

                for (String value: data) {
                        String[] hhmm = value.split(":");
                        int hh = Integer.parseInt(hhmm[0]);
                        int mm = Integer.parseInt(hhmm[1]);
                        if (hh > hourOfDay || hh == hourOfDay && mm > minute) {
                                System.out.println(hh + ":" + mm + ">" + hourOfDay + ":" + minute);
                                System.out.println("\n");
                                if (++cnt >= 3) break;
                        }

                }
        }
}

nextbus, java実行例：

$ javac api-json-nextbus-sample.java
$ java api-json-nextbus-sample
16:15
17:15
18:15

Processing で作る場合、下記のバスの絵も入れて、よりリアルなアプリができます。

3台のバスを描く（自分で定義した関数を使って）

int h=60; // ボディの高さ、幅の基準
int d=30; // 車輪の直径の基準

void setup() {
  size(400, 400);
  noLoop(); // 繰り返さない
}

void draw() {
  drawBus(200, 200); //中央のバス
  drawBus(100, 100); //左上のバス
  drawBus(300, 300); //右下のバス
}

void drawBus(int x, int y) {
  rectMode(CENTER);
  rect(x, y, h*2, h); // ボディ
  ellipse(x-35, y+h/2, d, d); // 後輪・外側
  ellipse(x+35, y+h/2, d, d); // 前輪・外側
  ellipse(x-35, y+h/2, d-10, d-10); // 後輪・内側
  ellipse(x+35, y+h/2, d-10, d-10); // 前輪・内側
  rectMode(CORNER);
  rect(x+45, y-20, h/4, h/3); // 窓・前
  rect(x-5, y-20, h/2, h/3); // 窓・中
  rect(x-50, y-20, h/2, h/3); // 窓・後
}

REST

RESTは「REpresentational State Transfer」の略で、大まかに言えば、アドレス（URL）とHTTPのメソッド（GETなど）を組み合わせて、サーバー上のデータを操作する仕組みです。

RESTは、Roy Fieldingという方が、2000年に発表した博士論文で提唱されたアーキテクチャスタイルです。Roy FieldingさんはHTTP仕様の策定者の一人であったことから、HTTPはRESTの基準をよく満たしています。

RESTの例として、WordPress JSON REST API (WP API, http://wp-api.org/) あります。それを利用して、Javaなどから最新の記事の取得、記事の投稿、写真の添付などが可能です。

JSON

JSON（ジェイソン、JavaScript Object Notation）は、JavaScriptにおけるオブジェクトの表記法をベースとした軽量なデータ記述言語である。

JSONの紹介
http://www.json.org/json-ja.html

このフォーマットの特徴は、

1. 名前/値のペアで表記される、連想配列のような構造
2. カンマで区切られたリスト（配列）のような構造

オブジェクト

オブジェクトは中括弧({ , })で囲み、中の要素は文字列/値で表現します。複数の要素を利用する場合は、カンマで区切り、続けて記述します。

{文字列:値,文字列:値,..文字列：値}

配列

配列は大括弧([ , ])で囲み、中の要素を値の連続（0個以上）で表現します。複数の要素を利用する場合は、カンマで区切り、続けて記述します。

[ 値, 値, ..., 値]

値

値は以下の7種類です

• 文字列
• 数値
• オブジェクト
• 配列
• true
• false
• null

文字列は2重引用符(“)で囲まれます。

学バス時刻表の取得

JSONArray json = loadJSONArray("http://busapp.wasedaonline.com/api/getvalue/?tag=20");
JSONObject content = json.getJSONObject(2);
String data = content.getString("post_content");
println(data);

参考

• http://labo.mamezou.com/special/sp_013/sp_013_001.html — RESTのコンセプトと特徴
• http://www.agilegroup.co.jp/technote/java-rest-client01.html — JavaでRESTクライアントを作成する【第一回】
• http://thinkit.co.jp/article/70/1/page/0/1 — JSONってなにもの？
• http://d.hatena.ne.jp/seinzumtode/20130426/1366934641 — JavaでJSONを使う
• http://gootara.org/library/2014/04/javaapijsonjdk1618.html — Java SEの標準APIだけでJSONを扱うサンプル（JDK 1.6以降、1.8も対応）

Webアプリケーション作成に必要な概念を理解する

Web Service

Webサービスとは、大まかにいえば、Webの通信の仕組みを利用して、コンピュータ同士でさまざまなデータをやり取りし、分散処理を行うシステムです。

通信手順の取り決めのことを、「プロトコル」（Protocol）と呼びます。Webの世界では、「HTTP」（HyperText Transfer Protocol）というプロトコルで、通信が行われています。

HTTPは、WebブラウザなどのクライアントがWebサーバーにデータを要求し、それにWebサーバーが答える、という形のプロトコルです。

API

アプリケーションプログラミングインタフェース (API、英: Application Programming Interface) とは、ソフトウェアコンポーネントが互いにやりとりするのに使用するインタフェースの仕様である。APIには、サブルーチン、データ構造、オブジェクトクラス、変数などの仕様が含まれる。

Webサービス大まかに言えば、以下のような流れで処理を進めます。

（1）クライアントからサーバーに対して、HTTPで接続して処理を要求します。
（2）サーバーは処理結果をクライアントに送信します。
（3）クライアントは（2）の結果を受信し、必要に応じて各種の処理を行います。

「HTTPで通信する」上位層に位置するプロトコル

1. 「XML-RPC」
2. 「SOAP」（Simple Object Access Protocol）
3. 「REST」（REpresentational State Transfer） :  REST and JSON

Open Data

open-data

お天気Webサービスの利用

お天気Webサービス（Livedoor Weather Web Service / LWWS）は、現在全国142カ所の今日・明日・あさっての天気予報・予想気温と都道府県の天気概況情報を提供しています。

（例）「福岡県・久留米の天気」を取得する場合

• http://weather.livedoor.com/forecast/webservice/json/v1?city=400040

学バス時刻表

Javaを利用して、学バスの時刻表取得と処理を行う

• http://busapp.wasedaonline.com/
• http://busapp.wasedaonline.com/api/getvalue/?tag=20  — 日曜・祝日　キャンパス行き

課題：

オープンデータを利用したWebアプリの作成(1)

1. オープンデータの選択
   1. 郵便番号検索
   2. 天気予報検索
   3. その他
2. オープンデータをブラウザで確認

Map構造 コレクションクラス

Map構造は、キーと値をセットにしたものを１つの要素として管理するデータ構造です。
「HashMap」「TreeMap」の２種類があります。

要素がキーと値で管理されているので、キーを指定して値の取得や更新、削除を行います。

Map構造は、キーによって値を管理するためキーの重複は不可です。
（同じキーがセット(put)された場合は上書きされます。）

マップ（HashMap）

HashMap hm = new HashMap();

hm.put("Brian Kernighan","A REGULAR EXPRESSION MATCHER");
hm.put("Karl Fogel","SUBVERSION'S DELTA EDITOR: INTERFACE AS ONTOLOGY");
hm.put("Jon Bentley","THE MOST BEAUTIFUL CODE I NEVER WROTE");
hm.put("Tim Bray","FINDING THINGS");

println("Get a Element > " + hm.get("Brian Kernighan") );
println("Get a Element > " + hm.get("Jon Bentley") );

マップ（TreeMap）

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

HashMap hm = new HashMap();
Map m;
m = hm;
m.put("Brian Kernighan","A REGULAR EXPRESSION MATCHER");
m.put("Karl Fogel","SUBVERSION'S DELTA EDITOR: INTERFACE AS ONTOLOGY");
m.put("Jon Bentley","THE MOST BEAUTIFUL CODE I NEVER WROTE");
m.put("Tim Bray","FINDING THINGS");

HashMap hm2 = new HashMap();
m = hm2;
m.put(1,123);
m.put(2,223);
m.put(3,323);

m = hm;
println("Get a Element from Interface m > " + m.get("Tim Bray") );
m = hm2;
println("Get a Element from Interface m > " + m.get(2) );

m = hm;
Set s = m.keySet();
for(Object o : s){
  println("Element is " + m.get(o) );
}
m = hm2;
s = m.keySet();
for(Object o : s){
  println("Element is " + m.get(o) );
}

List構造 コレクションクラス

List構造は、要素を順番付けして管理するデータ構造です。
「ArrayList」「LinkedList」の２種類があります。

要素がインデックス（番号）順に並んでいるので、番号を指定して要素の取得、挿入、更新、削除ができます。また、Iteratorや拡張for構文を使って先頭から順番に要素を取得することも出来ます。

ArrayListは要素の取得が早いが挿入や削除が遅い、LinkedListは要素の挿入や削除は早いが取得が遅いという特徴があります。
List構造は、要素の重複は可能です。

リスト（ArrayList）

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

String n[] = {"Tim Bray",
              "Brian Kernighan",
              "Jon Bentley",
              "Karl Fogel"};
ArrayList<String> names = new ArrayList(Arrays.asList(n));


//配列と同様の方法，添字で要素にアクセスします。
println("* Access with FOR *");
for(int i = 0; i<names.size(); ++i){
  println(names.get(i));
}

names.add(1,"Eliotte Rusty Harold"); // 2番目位置に要素を挿入します。
names.remove(2); // 3番目の要素を削除します。

//コレクションクラスならではの方法で要素にアクセスします。
println("* Access with ITERATOR *");
Iterator<String> it = names.iterator();
while(it.hasNext()){
  println(it.next());
}

リスト（LinkedList）

リスト（Vector）

文字列を検索する – indexOf／lastIndexOfメソッド

文字列に含まれる部分文字列を検索するには、indexOfメソッドを利用します。indexOfメソッドは、指定された部分文字列が最初に登場した位置を、文字列の先頭を0としたインデックス番号で返します。文字列が見つからなかった場合、戻り値は-1となります。
第2引数で、検索開始位置を指定することもできます。

部分文字列を文字列の末尾から検索するならば、lastIndexOfメソッドを利用してください。

match()　正規表現を使った検索

　正規表現を使って、文字列(String)を検索します。結果は文字列の配列として返されます。
【構文】
match(str, regexp)
【パラメータ】
str 検索対象の文字列
regexp 検索条件をあらわす正規表現
【戻り値】
String[]　(一致する文字がないときはnull)

　次の例は文字列からデータを取り出します。

String t = "本日の気温は28度です";
String[] m = match(t, "([0-9]+)度");	// 「度」の前の数値を取り出す

if(m != null) {
  println("t=" + m[1]);				// 検索結果(m[1])を出力
  println(m[0]);						// 一致した文字全体(m[0])を出力
} else {
  println("不一致");
}

参考：

• http://java-code.jp/187
• http://www.technotype.net/processing/reference/String.html

Set構造は、要素を順番付けしないで管理するデータ構造です。
「HashSet」「TreeSet」の２種類があります。

Listのような順番付けや、Mapのようなキー管理もないため、要素の取得にはIteratorや拡張for構文で取得します。
このようなことからHashSetは要素の取得順は保証されませんが、TreeSetは自動ソートされて管理されるのでソートされた順番で要素が取得されます。
また、HashSetは要素にnullを使用する事が可能ですが、TreeSetはnullを使用する事ができません。
Set構造は、要素の重複は不可です。（同じキーがセット(add)された場合は上書きされます。）

セット（HashSet）

HashSet も配列を扱いますが、要素の重複が許されない、順序の保障が無い点が ArrayList や LinkedList と異なります。要素を参照する際には Iterator を用います。

import java.util.*;

class HashSetTest {
    public static void main(String[] args) {
        HashSet set = new HashSet();
        set.add("AAA");
        set.add("BBB");
        set.add("CCC");
        set.add("AAA");
        Iterator it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

実行結果は下記のようになります。AAA を 2回 add() していますが、重複要素がひとつにマージされます。結果の順序は add() した順序に関係なくバラバラになります。

C:java>java HashSetTest
CCC
AAA
BBB

下記などのメソッドが用意されています。

セット （TreeSet）

import java.util.*;

class TreeSetTest {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        set.add("CCC");
        set.add("AAA");
        set.add("BBB");
        set.add("AAA");
        Iterator it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

C:java>java TreeSetTest
AAA
BBB
CCC

ソートとは

ソートとは，複数のデータを特定の順序に従うよう並べ替える作業のことです。順番の決め方には次の2つがあります。

並べ替えは、主にデータベースなどの大量のデータを処理する必要のあるプログラムで有用です。試験の点数の高い順番に並べ替えて、上位1000人を合格にするなどの場合は、点数による並べ替えが行われます。また、住所録のデータを住所毎にまとめて参照したい場合は、住所（文字列）による並べ替えが行われます。

ソートアルゴリズム

ソートの処理は、さまざまなプログラムの中で頻繁に使われ、そのゆえ、古くからいろいろなアルゴリズムが考案されてきました。

ソートを行うアルゴリズムの例として次のものが挙げられます。

• 基本形
  • 基本交換法：バブルソート
  • 基本選択法：直接選択法
  • 基本挿入法
• 応用形
  • 改良交換法：クイックソート
  • 改良選択法：ヒープソート
  • 改良挿入法：シェルソート

バブルソート

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がと遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）

バブルソートサンプル

final int    NUMBER_OF_RANDOM_DATA = 500;
final String DATA_FILE_NAME        = "RandomData.txt";
final int    DIAMITER              = 5;

ArrayList nums = new ArrayList();
int i = 0; // ソート回数。drawする度にカウントアップ

void setup(){
  //ランダムなデータの読み込み
  loadData();
  //ディスプレイウインドウの設定
  size(500,500);
  background(0,0,0);
  frameRate(60);
  stroke(255,0,0);
}

void loadData(){
  String lines[] = loadStrings(DATA_FILE_NAME);
  for(String val : lines){
    nums.add(int(val));
  }
}

void onePassOfBubbleSort(){
  for ( int j = NUMBER_OF_RANDOM_DATA - 1; j > i; j--){
    if ( nums.get(j) < nums.get(j-1) ){
      int temp = nums.get(j);
      nums.set(j,nums.get(j-1));
      nums.set(j-1,temp);
    }
  }
}

void draw(){
  if (i < NUMBER_OF_RANDOM_DATA - 1){
    //ソート１パス
    onePassOfBubbleSort();
    //結果をプロット
    println("Count " + i);
    clear(); 
    for (int k=0; k < nums.size(); k++) {
      ellipse(k,nums.get(k),DIAMITER,DIAMITER);
    }
    ++i;
  }
}

再帰とは

再帰（Recursion）とは，再帰的な構造を持つアルゴリズムのことです。再帰的な構造とは，自分自身の定義の中に，自分自身を含む構造です。再帰の代表的な例として階乗やユークリッドの互除法の再帰的定義がよく用いられます。それぞれについて学習していきます。

階乗

整数nの階乗は記号!を用いてn!と書きます。実際の計算は次のように行われます。

n! = n × (n-1) × (n-2) × ... × 2 × 1 

この式を再帰的定義に書き換えると，次のようになります。

n! = n × (n-1)!  (ただし，0!=1)

次の階乗のsketch、Factorial.pdeは10の階乗を行う例

1. 繰り返し構文を使ったメソッド　factorial_for
2. 再帰するメソッド　factorial_recursive

// 繰り返し構文を用いたメソッド
long factorial_for(long i){
  if(i < 0){
    println("Error! Invarid input.<using for>");
    return -1;
  } else {
    long result = 1;
    for (int j = 1; j <= i; ++j){
      result *= j;
    }
    return result;
  }
}
// 再帰を用いたメソッド
long factorial_recursive(long i){
  if(i < 0){
    println("Error! Invarid input.<using recursive>");
    return -1;
  } else if(i == 0){
    return 1;
  } else {
    return i * factorial_recursive(i - 1);
  }
}

void setup(){
  long num    = 0;
  // using for
  println("using for       : factorial(" + num + ") = "
           + factorial_for(num) );
  // using recursive
  println("using recursive : factorial(" + num + ") = "
           + factorial_recursive(num) );
  num    = 10;
  // using for
  println("using for       : factorial(" + num + ") = "
           + factorial_for(num) );
  // using recursive
  println("using recursive : factorial(" + num + ") = "
           + factorial_recursive(num) );
  num    = -10;
  // using for
  println("using for       : factorial(" + num + ") = "
           + factorial_for(num) );
  // using recursive
  println("using recursive : factorial(" + num + ") = "
           + factorial_recursive(num) );

}

ユークリッドの互除法

８王妃問題を解く

再帰を活用するメリットとデメリット

再帰を活用するメリットは，「（場合によっては）問題をシンプルに記述できること」です。しかし，再帰は電子計算機で実行するアルゴリズムとしてはやっかいな問題，デメリットを抱えています。

そのデメリットを話す前に，計算量の2つの種類について言及しておきます。計算量は「時間計算量」と「空間計算量」という2つに区別できます。時間計算量は，これまで何度か取り扱って来た計算量の考え方で，そのアルゴリズムの実行にどれだけ手数がかかるかを表す量です。これに対して空間計算量は，そのアルゴリズムの実行にどれだけの記憶容量が必要かを表す量です。

再帰のアルゴリズムは，自分自身を1回呼ぶ度に，自分自身を実行するために必要なメモリを用意します。再帰の回数が多くなれば，必要なメモリ容量も多くなります。つまり，再帰のアルゴリズムのデメリットとは空間計算量が大きくなることです。再帰のアルゴリズムは潤沢にメモリがあることを前提とした手段なのです。

かつて，コンピュータがごくわずかなメモリしか持っていなかった時代のプログラミング言語が，再帰を言語の仕組みとして用意しなかった理由の一つは，再帰が簡単にメモリを食いつぶす方法だったからでしょう。現在，パーソナルコンピュータのメモリは数ギガバイトを持つようになったため，この問題が大きく扱われることはあまりありません。ただ，再帰を使ったプログラムによってはメモリを圧迫しますので，利用にあたっては慎重になりましょう。

そのため，再帰アルゴリズムを使用するべき場合とは，コードを劇的にシンプルにできる場合に限ると考えておくべきです。