Page List

Search on the blog

2013年2月10日日曜日

Learn Spring Framework (1)

Springについて復習しました。最近はアノテーションで楽に設定ができるようになりましたが、まずは基本からということでxml設定ファイルを利用したDIについてまとめます。

Setter Injection
一番基本的なインジェクションです。

Setter Injectionの説明に入る前に、Spring FrameworkからBeanを取得するためのファクトリークラスを作っておきます。
package com.kenjih.java.main;

import org.springframework.context.ApplicationContext;
import org.springframework.context.support.ClassPathXmlApplicationContext;

public class BeanFactory {
    private static final String BEAN_CONFIG_FILE = "beans.xml";
    
    public static Object getBean(String name) {
        ApplicationContext context = new ClassPathXmlApplicationContext(BEAN_CONFIG_FILE);
        return context.getBean(name);
    }
}
以下のサンプルでは上記のクラスを使ってBeanを取得することとします。

それでは、Setter Injectionのサンプルに入ります。 まず、Beanの定義ファイルから。
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://www.springframework.org/schema/beans
           http://www.springframework.org/schema/beans/spring-beans-2.5.xsd">

    <bean id="DISample" class="com.kenjih.java.main.DISample">
        <property name="service">
            <ref bean="helloService" />
        </property>
    </bean>

    <bean id="helloService" class="com.kenjih.java.main.HelloServiceImpl">
    </bean>

</beans>
次に、クライアントクラス。HelloServiceインターフェースを実装したクラスを使用しますが具体的なクラス名をコード上から排除しています。ポイントはsetServiceメソッドです。IoCによって、Spring Frameworkからこのメソッドが呼ばれBeanが注入されます。
package com.kenjih.java.main;

public class DISample {
    private HelloService service;
    
    public void setService(HelloService service) {
        this.service = service;
    }
    
    public void doSomething() {
        service.say();
    }
    
    public static void main(String[] args) {
        DISample bean = (DISample) BeanFactory.getBean("DISample");
        bean.doSomething();
    }
}
次に、サービスクラスのインターフェース。
package com.kenjih.java.main;

public interface HelloService {
    public void say();
}
そんでもって、サービスクラスの実装とテスト用のモッククラス。クライアントクラスにはどの実装を用いるか書いてないので、ソースコードを変更することなくどちらのクラスを使用するか切り替えることができます。
package com.kenjih.java.main;

public class HelloServiceImpl implements HelloService {

    @Override
    public void say() {
        System.out.println("Hello, world!");
    }

}
package com.kenjih.java.test;

import com.kenjih.java.main.HelloService;

public class HelloServiceMock implements HelloService {

    @Override
    public void say() {
        System.out.println("Hello, world! -- mock -- ");
    }

}
Constructor Injection
コンストラクタを使ってインジェクションすることもできます。
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://www.springframework.org/schema/beans
           http://www.springframework.org/schema/beans/spring-beans-2.5.xsd">

    <bean id="DISample" class="com.kenjih.java.main.DISample">
        <constructor-arg>
            <ref bean="helloService" />
        </constructor-arg>
    </bean>

    <bean id="helloService" class="com.kenjih.java.main.HelloServiceImpl">
    </bean>

</beans>
のように設定ファイルを書き換えます。コンストラクタを通じてBeanを注入するので、コンストラクタでサービスクラスを受け取るようにします。
package com.kenjih.java.main;

public class DISample {
    private HelloService service;
    
    public DISample(HelloService service) {
        this.service = service;
    }
    
    public void doSomething() {
        service.say();
    }
    
    public static void main(String[] args) {
        DISample bean = (DISample) BeanFactory.getBean("DISample");
        bean.doSomething();
    }
}
Factory Method Injection
Staticなファクトリーメソッドを使ってBeanを生成する場合も、Constructor Injectionと同様にインジェクションが行えます。 設定ファイルは以下のようにします。beanタグのfactory-method属性でどのメソッドをファクトリーメソッドとして使用するか指定します。
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://www.springframework.org/schema/beans
           http://www.springframework.org/schema/beans/spring-beans-2.5.xsd">

    <bean id="DISample" class="com.kenjih.java.main.DISample" factory-method="createInstance">
        <constructor-arg>
            <ref bean="helloService" />
        </constructor-arg>
    </bean>

    <bean id="helloService" class="com.kenjih.java.main.HelloServiceImpl">
    </bean>

</beans>
こんな感じで使えます。
package com.kenjih.java.main;

public class DISample {
    private HelloService service;
    
    private DISample() {
        
    }
    
    public static DISample createInstance(HelloService service) {
        DISample obj = new DISample();
        obj.service = service;
        
        return obj;
    }
        
    public void doSomething() {
        service.say();
    }
    
    public static void main(String[] args) {
        DISample bean = (DISample) BeanFactory.getBean("DISample");
        bean.doSomething();
    }
}
Lookup Method Injection
これは知らなかったのですが、面白いです。DIコンテナ配下にあるBeanのメソッドの戻り値を書き換えることができます。djUnitの仮想モックオブジェクトに似てると思います。
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://www.springframework.org/schema/beans
           http://www.springframework.org/schema/beans/spring-beans-2.5.xsd">

    <bean id="DISample" class="com.kenjih.java.main.DISample">
        <lookup-method name="getService" bean="helloService" />
    </bean>

    <bean id="helloService" class="com.kenjih.java.test.HelloServiceMock" scope="prototype"/>
</beans>
のように設定すると、あら不思議。ソースコード上ではgetServiceでImplクラスを返しているのに、実行するとモッククラスが返されます。
package com.kenjih.java.main;

public class DISample {
    public HelloService getService() {
        return new HelloServiceImpl();
    }
    
    public static void main(String[] args) {
        DISample bean = (DISample) BeanFactory.getBean("DISample");
        
        HelloService service = bean.getService();
        service.say();
    }
}

HackerCup 2013 Round2 Permutations

問題概要
N個の整数と、それらの整数に関するN-1個の二項関係が与えられる。すべての二項関係を満たすN個の整数の順列のパターン数(MOD 1000000007)を求めよ。

解法
動的計画法を用いる。dfs(v, p)の解res[i]は節点vに対応する整数がi番目に現れる順列のパターン数を返す。
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

const long long MOD = 1000000007;
vector<pair<int, int> > edge[1024];
long long comb[1024][1024];

vector<long long>dfs(int v, int p = -1) {
    vector<long long> x(1, 1);

    REP (k, edge[v].size()) {
        int u = edge[v][k].first;
        if (u == p)
            continue;
        vector<long long> y = dfs(u, v);
        if (edge[v][k].second) {   // v < w
            for (int i = (int)y.size()-1; i > 0; i--)
                y[i-1] = (y[i] + y[i-1]) % MOD;
            y.push_back(0);
        } 
        else {                     // v > w
            for (int i = 1; i < (int)y.size(); i++)
                y[i] = (y[i] + y[i-1]) % MOD;
            y.insert(y.begin(), 0);
        }

        vector<long long>tmp = vector<long long>(x.size() + y.size() - 1);
        REP (i, x.size()) REP (j, y.size()) {
            long long p = x[i] * y[j] % MOD;
            long long q = comb[i+j][j] * comb[x.size()-1-i+y.size()-1-j][y.size()-1-j] % MOD;
            tmp[i+j] = (tmp[i+j] + p * q % MOD) % MOD;
        }
        x = tmp;
    }
    return x;
}

long long solve() {
    REP (i, 1024) 
        edge[i].clear();

    int n, a, b;
    char c;
    cin >> n;
    REP (i, n-1) {
        cin >> a >> c >> b;
        edge[a].push_back(make_pair(b, c=='<'));
        edge[b].push_back(make_pair(a, c=='>'));
    }

    vector<long long> res = dfs(0);

    long long ret = 0;
    REP (i, n)
        ret = (ret + res[i]) % MOD;
    return ret;
}

void init() {
    comb[0][0] = 1;
    REP (i, 1024-1) REP (j, i+1) {
        comb[i+1][j] = (comb[i+1][j] + comb[i][j]) % MOD;
        comb[i+1][j+1] = (comb[i+1][j+1] + comb[i][j]) % MOD;
    }
}

int main() {
    int T;
    cin >> T;
 
    init();
    REP (i, T) {
        cerr << "solving #" << (i+1) << "...." << endl;
        long long ret = solve();
        cout << "Case #" << (i+1) << ": " << ret << endl;
    }

    return 0;
}

2013年2月9日土曜日

Learn Struts(8)

openid4javaを使ってJavaでOpen ID認証をやってみました。せっかくなのでStrutsのDispatchActionを使って処理するようにしてみました。

インストール
公式サイトからtarをダウンロード。

解凍して、openid4java-x.x.x.jarをWEB-INF/libに配置。
依存するライブラリが、openid4java-x.x.x.xxx/libディレクトリに入っているので、これも必要に応じてWEB-INF/libに投入。

作ったもの
ほとんどQuickStartにあったものをつなぎあわせただけです。
userSuppliedStringが謎でしたが、http://www.ibm.com/developerworks/java/library/j-openid/を見ると、

The RP normalizes the User-Supplied Identifier to determine which OP to contact for authentication and how to contact it.

とあったので、Providerの認証URIを指定しました。

とりあえずアクションクラスだけ載せときます。
jspとかアクションフォームとかsturts-configとかも見たい人はgistへ。

[AuthAction.java]
public class AuthAction extends DispatchAction {
    private ConsumerManager manager;
    private static final String RETURN_URL = "http://localhost:8080/OpenId/auth.do?event=verify";

    public AuthAction() {
        manager = new ConsumerManager();
    }

    @SuppressWarnings("rawtypes")
    public ActionForward redirect(ActionMapping mapping, ActionForm form,
            HttpServletRequest request, HttpServletResponse response)
            throws Exception {

        OpenIdInfoForm f = (OpenIdInfoForm) form;
        String provider = f.getProvider();

        List discoveries = manager.discover(provider);
        DiscoveryInformation discovered = manager.associate(discoveries);

        HttpSession session = request.getSession();
        session.setAttribute("discovered", discovered);

        AuthRequest authReq = manager.authenticate(discovered, RETURN_URL);

        response.sendRedirect(authReq.getDestinationUrl(true));

        return null;
    }

    public ActionForward verify(ActionMapping mapping, ActionForm form,
            HttpServletRequest request, HttpServletResponse response)
            throws Exception {

        ParameterList openidResp = new ParameterList(request.getParameterMap());

        HttpSession session = request.getSession();
        DiscoveryInformation discovered = (DiscoveryInformation) session
                .getAttribute("discovered");

        StringBuffer receivingURL = request.getRequestURL();
        String queryString = request.getQueryString();
        if (queryString != null && queryString.length() > 0)
            receivingURL.append("?").append(request.getQueryString());

        VerificationResult verification = manager.verify(
                receivingURL.toString(), openidResp, discovered);

        Identifier verified = verification.getVerifiedId();
        
        if (verified == null) {
            ActionMessages errors = new ActionMessages();
            errors.add("authError", new ActionMessage("errors.authError"));
            saveErrors(request, errors);
            return mapping.findForward("failure");
        }
        
        OpenIdInfoForm f = (OpenIdInfoForm)form;
        f.setId(verified.getIdentifier());
        return mapping.findForward("success");
    }
}

2013年2月8日金曜日

JavaでCookie使うときの注意

 以下のプログラムは、クッキーを使ってカウントアップしていくプログラムです。しかし、問題があります。何がまずいでしょうか?
import java.io.IOException;
import javax.servlet.ServletException;
import javax.servlet.http.Cookie;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

public class Test extends HttpServlet {
    private static final long serialVersionUID = 1L;

    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        
        Cookie[] cookies = request.getCookies();
        Cookie cookie = null;
        
        if (cookies != null) {
            for (int i = 0; i < cookies.length; i++) {
                if ("counter".equals(cookies[i].getName())) {
                    cookie = cookies[i];
                    response.getWriter().write(cookie.getValue());
                    break;
                }
            }
        }
        
        if (cookie == null) {
            cookie = new Cookie("counter", "0");
            cookie.setPath("/");
            cookie.setMaxAge(60*60);
        } else {
            int counter = Integer.valueOf(cookie.getValue());
            counter++;
            cookie.setValue(Integer.toString(counter));
        }
        response.addCookie(cookie);
    }

}
実は上のプログラムだと、クッキーが2つできてしまいます。

設定したい名前のクッキーが存在するときは、その値をインクリメントして値を更新して、レスポンスに書く。という処理をしていますが、これだけでは足りません。

int counter = Integer.valueOf(cookie.getValue());
counter++;
cookie.setPath("/");
cookie.setMaxAge(60*60);
cookie.setValue(Integer.toString(counter));
のように最大寿命、パスを再設定してあげないといけません。 最初のソースコードでは、newしたクッキーのパスは"/"、更新するときのクッキーのパスはnullとなっていて、パスが異なるため同じ名前のクッキーが2つ出来てしまいます。
「なんだこの仕様面倒くさいなー。何でパスとか最大寿命とか再設定しないといけないの?サーブレットコンテナの中で管理してよ。」と思いましたが、よくよく考えるとHTTPリクエストのヘッダーにはクッキーの名前、値しか乗らないので、あたり前の仕様ですね。

[Request Headers]
Cookie: counter=5

[Response Headers]
Set-Cookie:counter=6; Expires=Fri, 08-Feb-2013 18:05:16 GMT; Path=/

のようにサーバーからのレスポンスには最大寿命とかパスが乗りますが、UAからのリクエストには乗らないので、getCookiesしたときにこれらの値はとれるはず無いですと。なるほど。

2013年2月4日月曜日

CGAL入れてみた。

学生時代のアルバイト仲間で機械学習の勉強会をしようということになったので、c++のCGALというライブラリを入れてみました。
忘れないようにメモっときます。

インストール
以下のページを参考にインストール。
https://parasol.tamu.edu/~amato/Courses/620/cgal/CGAL-Linux.html

sudo apt-get install libcgal-dev

QPを解いてみる
サンプルソースを入手して、以下のコマンドでコンパイル。
g++ -o test test.cpp -lCGAL -lgmp

実行結果。
status:          OPTIMAL
objective value: 8/1
variable values:
  0: 2/1
  1: 3/1
とりあえず、ソルバーさえあれば簡単なSVMは組めるので暇なときやってみようっと。

Hacker Cup 2013 Round1

全問正解で、なんとかRound 2進出です。

Card Game
ソートして、組み合わせの数を数えました。数字が大きかったのでフェルマーの小定理使おうと思いましたが、自宅PC使えるのでメモリ2Gまでいけるなと気付いてパスカルの三角形を使いました。

Security
順列、辞書順最小の時点で「あ、フロー系だな。」と気付きました。貪欲に選んでいく方法をどうするか迷って、最小費用流か?と脇道にそれつつも、なんとかGreedyに文字を固定しながら二部グラフの完全マッチングすればいいと気付いて、解けました。

Dead Pixels
最初は、二次元BITかセグメントツリー系の問題かなと思いました。が、メモリ足りないなと気付いて、booleanだったらメモリに乗るな。となって、座標圧縮して画素がつぶれているかどうかをbooleanで持てばメモリ的にはいけそうだなと気付きました。それでも時間計算量的にはNGだったのですが、よほど作為的なケースじゃない限り現実的な時間で解けそうな気がしたので思い切ってテストケースDL。無事時間内にsubmitできました。
とりあえず解けたもののアルゴリズムの選択が正しかったのか正確には理解できていません。

2013年2月2日土曜日

Learn log4j(3)

log4jなかなか面白いですねー。
ロガーの名前階層(logger hierarchy)を確認するために簡単なコードを書いてみました。
package a.b.c.d;

import org.apache.log4j.Logger;

public class Main {
    public static void main(String[] args) {
        Logger logger = Logger.getLogger(Main.class);
        logger.info("test!");
    }
}
ロガーの設定はこんな感じ。
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE log4j:configuration SYSTEM "log4j.dtd">

<log4j:configuration xmlns:log4j="http://jakarta.apache.org/log4j/">
    <appender name="console1" class="org.apache.log4j.ConsoleAppender">
        <param name="Target" value="System.out" />
        <layout class="org.apache.log4j.PatternLayout">
            <param name="ConversionPattern" value="package a : %m%n" />
        </layout>
    </appender>
    <appender name="console2" class="org.apache.log4j.ConsoleAppender">
        <param name="Target" value="System.out" />
        <layout class="org.apache.log4j.PatternLayout">
            <param name="ConversionPattern" value="package a.b : %m%n" />
        </layout>
    </appender>
    <appender name="console3" class="org.apache.log4j.ConsoleAppender">
        <param name="Target" value="System.out" />
        <layout class="org.apache.log4j.PatternLayout">
            <param name="ConversionPattern" value="package a.b.c : %m%n" />
        </layout>
    </appender>
    <appender name="console4" class="org.apache.log4j.ConsoleAppender">
        <param name="Target" value="System.out" />
        <layout class="org.apache.log4j.PatternLayout">
            <param name="ConversionPattern" value="package a.b.c.d : %m%n" />
        </layout>
    </appender>

    <logger name="a">
        <level value="info" />
        <appender-ref ref="console1" />
    </logger>
    <logger name="a.b">
        <level value="info" />
        <appender-ref ref="console2" />
    </logger>
    <logger name="a.b.c">
        <level value="info" />
        <appender-ref ref="console3" />
    </logger>
    <logger name="a.b.c.d">
        <level value="info" />
        <appender-ref ref="console4" />
    </logger>

</log4j:configuration>
これを実行すると、
package a.b.c.d : test!
package a.b.c : test!
package a.b : test!
package a : test!
となります。

a.b.c.d.Mainという名前のロガーを作ると、ログを出力する際にその親である

  • a.b.c.d
  • a.b.c
  • a.b
  • a
という名前のロガーにも「ログを出力せよ」という命令が伝わります。

もし自分より上の親たちには命令を伝えたくないという場合はadditivity属性をfalseにすればOKです。
<logger name="a">
    <level value="info" />
    <appender-ref ref="console1" />
</logger>
<logger name="a.b">
    <level value="info" />
    <appender-ref ref="console2" />
</logger>
<logger name="a.b.c" additivity="false">
    <level value="info" />
    <appender-ref ref="console3" />
</logger>
<logger name="a.b.c.d">
    <level value="info" />
    <appender-ref ref="console4" />
</logger>
とすると出力は、
package a.b.c.d : test!
package a.b.c : test!
のようになります。