Search on the blog

2012年12月31日月曜日

デザインパターン(8) Abstract Factory

まとめ
  • オブジェクト生成のためのデザインパターン。
  • クライアントはabstract factoryを通してオブジェクトの生成を行う。
  • クライアントは生成されたオブジェクトの具体的な実装は知らない。
  • abstract factoryを継承したconcrete factoryをシステム変数やプロパティファイル、実行引数などで指定することにより、使用される具体的な工場を変えることができる。
  • 具体的な工場の種類によって生成されるオブジェクト(concrete object)の具体的な実装は異なる。
  • 新しい種類のconcrete factory / concrete objectをクライアントへの影響なく追加できる。

疑問点
Factory Method Patternとの違いがよく分かっていないような気がする。

参考[2]によると、「Factory methodは単なるメソッド。Factory methodを実装しているクラスの本来の役割はオブジェクトの生成ではない。これに対して、Abstract Factoryはオブジェクト生成のためのクラス。異なる工場では異なる製品が作成される。」とある。

Factory MethodってAbstract Factoryと同じようなことをするイメージを持っていたけど、もっと単純なものという認識でいいのだろうか。。単純にそのクラスで使いたいオブジェクトを生成するときにnewせずにcreateInstanceみたいなメソッドを使うぞ!と決めたらそれがFactory Methodになるんだろうか・・。

 お、いい説明を見つけた。Factory methodのエッセンスは、
Define an interface for creating an object, but let the classes that implement the interface decide which class to instantiate. The Factory method lets a class defer instantiation to subclasses.」 (参考[3])

ふむふむ。なんか分かってきた。逆にAbstract Factoryのエッセンスは、
Provide an interface for creating families of related or dependent objects without specifying their concrete classes.」 (参考[1])

やべっ。超分かりやすい。なんか分かったような気がする。

Factory methodの場合は、使いたいオブジェクトを生成するためのメソッドがスーパークラスで定義されているので、それを実装して具体的にどのクラスを使うか決めてください。オブジェクトを作りたいときは、newじゃなくてそのメソッド(Factory method)を使ってください。

Abstract Factoryの場合は、オブジェクトの使用者クラスは、newしてそのオブジェクトを生成するのではなく、コンストラクタで受け取った(またはグローバルにアクセスできる部分に存在する)factoryさんにオブジェクトの生成を委譲してください。ただしfactoryさんの具体的な実装については使用者は知る必要はありません。実行環境ごとにfactoryさんの具体的な実装は異なっており、生成されるオブジェクトの具体的な実装も異なりますが、使用者はこれを意識する必要はありません。

と、こういうことかな。間違っていたらご指摘いただけると嬉しいです。

参考URL
[1] http://en.wikipedia.org/wiki/Abstract_factory_pattern
[2] http://stackoverflow.com/questions/5739611/differences-between-abstract-factory-pattern-and-factory-method
[3] http://en.wikipedia.org/wiki/Factory_method_pattern

2012年12月29日土曜日

Codeforces Round #152 Robo-Footballer

Problem Statement
A robot is playing soccer. To get a point, the robot shoots the ball in a way that the ball bounces off the wall once and goes into the goal net. If the ball touches goal posts or the wall more than once, it is caught by the opponent's goal keeper. The ball is considered to touch another object if the distance between the object and the center of the ball is less than the radius of the ball. Can the robot make the goal? If so, print the coordinates of the point the robot aims at.

Approach
Look at the figure below. It's self-explaining. The key techniques are:
  1. not consider the reflection -- just go through the wall! --
  2. consider only the "edge" case where the ball almost touches a goal post.


Source Code
#include <iostream>
#include <cstdio>
#include <complex>

using namespace std;

#define EPS (1e-8)
typedef complex<double> point;

double cross(point a, point b) {
    return a.real() * b.imag() - a.imag() * b.real();
}

double distanceLnPt(point a, point b, point c) {
    return abs(cross(b-a, c-a)) / abs(b-a);
}

point intersectionLn(point a1, point a2, point b1, point b2) {
    point a = a2 - a1;
    point b = b2 - b1;
    return a1 + a * cross(b, b1-a1) / cross(b, a);
}

int main() {
    int y1, y2, yw, xb, yb, r;

    cin >> y1 >> y2 >> yw >> xb >> yb >> r;

    yw -= r;
    point a(xb, yb);
    point b(0, 2*yw-(y1+r));
    point c(0, 2*yw-y2);

    double d = distanceLnPt(a, b, c);
    point pw = intersectionLn(a, b, point(0, yw), point(1, yw));

    if (d + EPS > r)
        printf("%.18lf", pw.real());
    else
        puts("-1");

    return 0;
}

2012年12月20日木曜日

Server-side Java(3) Servletのライフサイクル

サーブレットのライフサイクル
ざっくりまとめると、
  • コンテナ上にあるサーブレットのインスタンスは一つだけ
  • リクエスト毎にスレッドを作って処理を実行
  • インスタンスはコンテナが終了した場合(または一定時間アクセスされなかった場合)に破棄される
という感じ(だと理解している)[1]。 言葉だけ聞くとふーんって感じだけど、いろいろ遊べそうなのでごくごく簡単なコードを書いて実験してみた。やったことは、
  1. インスタンスが一つしかないことを確認
  2. スレッドセーフではないようなコードを実行してみる
  3. 2.をスレッドセーフにして動作確認
  4. デッドロックを発生させてみる

1. インスタンスが一つしかないことを確認
以下のサーブレットにアクセスすると、cntがカウントアップされていく。ブラウザを閉じたり、他のブラウザからアクセスしたりした場合もcntの値はどんどんカウントアップされていく。cntはクラス変数では無く、インスタンス変数なのに。。。ということで、インスタンスはコンテナ上に一つしかないのだなと確認できる。
package jp.blogspot.techtipshoge;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class threadTest1
 */
@WebServlet("/threadTest1")
public class threadTest1 extends HttpServlet {
    private static final long serialVersionUID = 1L;

    int cnt;

    @Override
    public void init() {
        cnt = 0;
    }

    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        response.setContentType("text/html; charset=UTF-8");
        PrintWriter out = response.getWriter();

        out.println("<html>");
        out.println("<body>");

        out.println("cnt = " + cnt++);

        out.println("</body>");
        out.println("</html>");
    }
}


2. スレッドセーフではないようなコードを実行してみる
こんなサーブレットを書いて同時アクセスするとどうなるか試した。
package jp.blogspot.techtipshoge;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class threadTest2
 */
@WebServlet("/threadTest2")
public class threadTest2 extends HttpServlet {
    private static final long serialVersionUID = 1L;

    int cnt;

    @Override
    public void init() {
        cnt = 0;
    }

    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        response.setContentType("text/html; charset=UTF-8");
        PrintWriter out = response.getWriter();

        out.println("<html>");
        out.println("<body>");

        out.println("cnt = " + cnt);
        try {
            Thread.sleep(3000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        ++cnt;

        out.println("</body>");
        out.println("</html>");
    }

}
まず、普通に以下のページにアクセスする。表示するのに3秒くらいかかる。
次に2つのタブを開いてサーブレットに(ほぼ)同時アクセスしてみる。「一つ目のスレッドが更新する前に、二つ目のスレッドがcntの値を読み込むので、2つ目のスレッドの表示で2インクリメントされるべきところが1しかインクリメントされない」という状況を予想したが、そうならなかった。(ブラウザはGoogle Chrome 23.0を使用。)
確かスレッドはリクエスト単位じゃなくて、クライアント単位みたいな話をどこかで見たような。。と思ってググってるとそれらしいのを見つけた。
TomcatやJBossではApache httpdのMaxClientsと同じく、リクエスト単位ではなくクライアント単位(ソケット単位)でスレッドを割り当てる。このモデルでは、例えばmaxThreads="20"とかにしたら常に同時に20個のリクエストをさばいてくれる、という仮定は成り立たない。クライアントがkeep aliveで接続している間はスレッドも待ち続けるので、21番目のリクエストは先に接続した20のクライアントがkeep aliveを終了してコネクションを切断するまで処理されない。[2]
おそらく異なるタブでアクセスしても同一のクライアントとして扱われたのでスレッドが生成されなかったのだろう。

じゃ、ChromeとFirefoxでサーブレットに同時アクセスしてみるか。お、出来た。出来た。想定どおりのスレッドセーフではない現象が見られた。

3. 2.をスレッドセーフにして動作確認
以下のサーブレットにChromeとFirefoxを使って同時アクセスしてみた。先にcnt読み込み処理に入ったスレッドがこのサーブレットインスタンスをロックするので、他のサーブレットからはcntにアクセスできなくなってしまう。cntは期待どおりにインクリメントされた。2.のスレッドセーフじゃないバージョンは後から微妙に遅れてサーブレットにアクセスしたUAのレスポンスは3秒くらいだったが、3.のスレッドセーフバージョンの場合は6秒くらい待たされることになる。

package jp.blogspot.techtipshoge;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class threadTest3
 */
@WebServlet("/threadTest3")
public class threadTest3 extends HttpServlet {
    private static final long serialVersionUID = 1L;

    int cnt;

    @Override
    public void init() {
        cnt = 0;
    }

    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        response.setContentType("text/html; charset=UTF-8");
        PrintWriter out = response.getWriter();

        out.println("<html>");
        out.println("<body>");
        
        synchronized (this) {
            out.println("cnt = " + cnt);
            try {
                Thread.sleep(3000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            ++cnt;            
        }

        out.println("</body>");
        out.println("</html>");
    
    }

}


4. デッドロックを発生させてみる
とりあえずデッドロックしそうなコードを苦し紛れに書いてみた。奇数番目のアクセスはhogeから、偶数番目のアクセスはfugaからロックするというふうにしてみた。
ChromeとFirefoxで同時アクセスするとデッドロックした。
package jp.blogspot.techtipshoge;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class threadTest4
 */
@WebServlet("/threadTest4")
public class threadTest4 extends HttpServlet {
    private static final long serialVersionUID = 1L;

    private static class Clazz {
        
    }
    
    Clazz hoge;
    Clazz fuga;
    int flip;
    
    @Override
    public void init() {
        flip = 0;
        hoge = new Clazz();
        fuga = new Clazz();
    }

    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        response.setContentType("text/html; charset=UTF-8");
        PrintWriter out = response.getWriter();

        out.println("<html>");
        out.println("<body>");
        
        ++flip;
        try {
            if (flip % 2 == 1) {
                synchronized (hoge) {
                    out.println("hoge locked.<br/>");
                    out.flush();
                    Thread.sleep(3000);
                    synchronized (fuga) {
                        out.println("fuga locked.<br/>");
                        out.flush();
                        Thread.sleep(3000);
                    }
                }
            } else {
                synchronized (fuga) {
                    out.println("fuga locked.<br/>");
                    out.flush();
                    Thread.sleep(3000);                    
                    synchronized (hoge) {
                        out.println("hoge locked.<br/>");
                        out.flush();
                        Thread.sleep(3000);
                    }
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        
        out.println("</body>");
        out.println("</html>");
    }

}

引用
[1] http://www.javadrive.jp/servlet/ini/index5.html
[2] http://d.hatena.ne.jp/nekop/20120424/1335254637

2012年12月9日日曜日

Server-side Java(2) Servletのフィルタを使う

フィルタとは?
あるServletが実行される直前に別の処理を埋め込む機能。どのServletに対して処理を埋め込むかは、servlet-mappingのurl-patternと同様に正規表現を使って指定することができる。
もともとフィルタの設定はweb.xmlに記述していたが、Servlet 3.0からはアノテーションで設定することができるようになった。
これは便利!AOPとほぼ同じに見えるんだけど、違いは何だろう。。

サンプル
Tomcat Version 7.0.33で動作確認。
/MainServletにアクセスすると、FilterServletの処理が実行されます。その後、MainServletの処理が実行されます。

[MainServlet.java]
import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Servlet implementation class MainServlet
 */
@WebServlet("/MainServlet")
public class MainServlet extends HttpServlet {
    private static final long serialVersionUID = 1L;

    /**
     * @see HttpServlet#doGet(HttpServletRequest request, HttpServletResponse
     *      response)
     */
    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        
        response.setContentType("text/html; charset=UTF-8");
        PrintWriter out = response.getWriter();

        out.println("<html>");
        out.println("<head>");
        out.println("<title>Filter Test</title>");
        out.println("</head>");
        out.println("<body>");

        out.println("<p>MainServletの処理です。</p>");

        out.println("</body>");
        out.println("</html>");
    }
}

[FilterServlet.java]
import java.io.IOException;

import javax.servlet.Filter;
import javax.servlet.FilterChain;
import javax.servlet.FilterConfig;
import javax.servlet.ServletException;
import javax.servlet.ServletRequest;
import javax.servlet.ServletResponse;
import javax.servlet.annotation.WebFilter;

/**
 * Servlet Filter implementation class FilterServlet
 */
@WebFilter(filterName="FilterServlet", urlPatterns="/*")
public class FilterServlet implements Filter {
    /**
     * @see Filter#destroy()
     */
    public void destroy() {
    }

    /**
     * @see Filter#doFilter(ServletRequest, ServletResponse, FilterChain)
     */
    public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain) throws IOException, ServletException {
        response.setContentType("text/html; charset=UTF-8");
        response.getWriter().println("Filterの処理です。");
        chain.doFilter(request, response);
    }

    /**
     * @see Filter#init(FilterConfig)
     */
    public void init(FilterConfig fConfig) throws ServletException {
    }

}

Server-side Java(1) Servletでセッションを使う

使用機能
HttpSession HttpServletRequest#getSession(boolean create) セッションを取得。引数にtrueを指定すると、セッションが取得できなかった場合に新しいセッションを作成する。
void HttpSession#setAttribute(String name, Object value) セッションに値を格納する。
Object HttpSession#getAttribute(String name) セッションから値を取り出す。

サンプル
Tomcat Version 7.0.33で動作確認。アクセス回数をカウントアップしていきます。
import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import javax.servlet.http.HttpSession;

/**
 * Servlet implementation class SessionServlet
 */
@WebServlet("/SessionServlet")
public class SessionServlet extends HttpServlet {
    private static final long serialVersionUID = 1L;
    /**
     * @see HttpServlet#doGet(HttpServletRequest request, HttpServletResponse
     *      response)
     */
    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        
        response.setContentType("text/html; charset=Shift_JIS");
        PrintWriter out = response.getWriter();
        HttpSession session = request.getSession(true);

        out.println("<html>");
        out.println("<head>");
        out.println("<title>Session Test</title>");
        out.println("</head>");
        out.println("<body>");

        int cnt = 1;
        Object visCnt = session.getAttribute("visit");
        if (visCnt != null)
            cnt = (int) visCnt + 1;
        
        out.println(cnt + "-th visit!!");
        session.setAttribute("visit", cnt);

        out.println("</body>");
        out.println("</html>");
    }
}

2012年12月1日土曜日

Dropboxを入れてみた

最近、競技プログラミングの問題をカテゴライズして、各問題ごとに直近で解いた日時、解いた回数を管理するような簡易アプリを作りました。
特にWEB上に公開するようなつもりは無くて、ローカルPCにApacheを入れてLANからのみ見れるようにしました。

1ヶ月間くらい使ってみて、問題がたまってきたので、バックアップを取りたいなと思いました。で、手軽にできるものが無いかなと考えていたところ、Dropboxを使うと簡単にできそうなのでやってみました。

やりたいこと
  • ローカルPCが壊れても、復旧できるようにしたい。
  • バックアップ対象は、DBのデータとPHPのソース。
  • バックアップの頻度は、3日に1回程度。
やったこと
まず、Dropboxをインストール。
すると、HOMEディレクトリにDropboxというディレクトリができる。
ここにファイルを入れるとDropboxのサーバーに自動で保存されるので、バックアップ完了という流れ。

あとは、自動でDBのdumpと、ソースコードをまとめてtar化するようなスクリプトを書けばいいだけ。
#!/bin/sh

data_backup_file="/home/kenjih/Dropbox/backup/procom/data/dump.sql"
src_backup_file="/home/kenjih/Dropbox/backup/procom/src/app.tar"
src_dir="/home/kenjih/dev/procom/src/app"
log="/home/kenjih/Dropbox/backup/procom/backup.log"

today=`date '+%s'`
updated_date=`stat -c '%y' ${data_backup_file}`
expire_date=`date -d "${updated_date} 3 days" '+%s'`

if [ $today -gt $expire_date ]; then
    mysqldump -u usr -ppasswd procom >${data_backup_file}
    tar -cf ${src_backup_file} ${src_dir} 2>/dev/null
    echo "backup files saved at `date '+%Y/%m/%d %T'`." >>${log}
fi

で、cronを設定。
# m h  dom mon dow   command
0 23 * * * /home/kenjih/dev/procom/src/app/Console/backup.sh