News

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

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

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

キューとスタックは、古典的なデータ構造として広く知られているものですが、 実装上はリストの一種と考えることができます。

キュー

キュー (Queue) は「先入れ先出し (First-In First-Out, FIFO)」を表すデータ構造です。 データを取り出す際、先に格納したものから順に取り出します。

• 銀行や病院やたい焼き屋の待ち行列 (先に並んだ人からサービスを受ける)
• コンピューターでプリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。

データを追加する操作をエンキュー(enqueue)。
データを取り出す操作をデキュー(dequeue)という。

スタック

スタック(Stack)は、 「あと入れ先出し (Last-In First-Out, LIFO)」あるいは「先入れあと出し(First-In Last-Out, FILO)」を表すデータ構造です。 データを取り出す際、最も後に格納したものから順に取り出します。

• 積ん読 (本を重ねて積んでいくと上からしか取れない)
• コンピューターで割込みやサブルーチンを支援するために極めて有用である

スタックにデータを入れる操作をプッシュ(push)という。
スタックからデータを取り出す操作をポップ(pop)という。

キューとスタックの実装

オブジェクトの後入れ先出し（LIFO）スタックを表すStackクラスは、JDK 1.0から導入されていました。これに対して、オブジェクトの先入れ先出し（FIFO）を表す待ち行列（キュー）は、特に用意されていませんでしたが、JDK 5.0からQueueインターフェイスが新たに導入されました。

一例として、LinkedListオブジェクトによるキューと、Stackクラスによるスタックを試すプログラムを作成しました。

import java.util.*;

String[] item = {"Apple", "Banana", "Cocoa"};
Queue q = new LinkedList();
Stack s = new Stack();
for(String i: item) {
  q.offer(i); // enqueue
  s.push(i);  // push
}
while(q.size() > 0) {
  println("QUEUE:" + q.poll());
}
while(s.size() > 0) {
  println("STACK:" + s.pop());
}

キューがスタックに近い形で利用可能になっているのが、実感できます。

参考：

• http://www.atmarkit.co.jp/fjava/javatips/182java064.html　ーーGenericsを用いたスタックとキューのサンプルプログラム

サーチ（Search）とは，複数のデータの中から特定のデータを見つけ出す作業のことです。日本語では探索や検索と呼びます。

サーチのアルゴリズムには，ランダムなデータを取り扱えるものと，ソート済みのデータを取り扱うものとがあります。

リストサーチ（list search）

データのリスト構造とはA, B, C, ……のように，データが次々と連続している構造のことを言います。代表例は配列です。

そのようなリスト構造を持つデータの集合を探索するためのアルゴリズムを，ここではリストサーチと呼びます。

探索のアルゴリズム

• 線形探索
• 二分探索
• ハッシュ法

線形探索

線形探索という言葉は英語のLinear Searchの直訳です。線形探索はリストの先頭から終端に向かって目的の要素を探し出すアルゴリズムです。

目的の要素であるという判定は比較によって行います。

アルゴリズム分析

1. リストの先頭から要素を取り出す
2. 取り出した要素の値と探したい要素の値を比較する
   • 一致すれば探索完了
   • 一致しなければ 1. へ戻り次の要素を取り出す

かなりシンプルで理解し易いアルゴリズムです。

サンプルコード

線形探索のアルゴリズムを実装したsketchは次のとおりです。

// 線形探索   Linear Search
// 番兵無し   No Sentinel

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

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

void setup(){
  //ランダムなデータの読み込み
  loadData();
  //ディスプレイウインドウの設定
  size(NUMBER_OF_RANDOM_DATA,NUMBER_OF_RANDOM_DATA);
  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 linearSearch(){
  if (SEARCHING_VALUE == nums.get(i)) {
    println("Hit!");
    ellipse(i,nums.get(i),DIAMITER*2,DIAMITER*2);
    exit();
  } 
}

void draw(){
  println("Searching value is " + SEARCHING_VALUE);
  if (i < NUMBER_OF_RANDOM_DATA){
    //サーチ１パス
    linearSearch();
    //結果をプロット
    println("Count " + i);
    clear(); 
    for (int k=0; k < nums.size(); k++) {
      if ( k == i ) {
        ellipse(k,nums.get(k),DIAMITER*2,DIAMITER*2);
      } else {
        ellipse(k,nums.get(k),DIAMITER,DIAMITER);
      }
    }
    ++i;
  }
}

参考：

• http://www.codereading.com/algo_and_ds/algo/linear_search.html