Search on the blog

2013年2月26日火曜日

Octaveメモ(3)

やばい、熱中しすぎて夜更かししてしまった。
2次元空間に点をプロットする方法をメモっときます。
octave> x1 = rand(10, 1);
octave> y1 = rand(10, 1) + 0.7 * x1;
octave> x2 = rand(10, 1);
octave> y2 = rand(10, 1) - 0.7 * x2;
octave> hold on;
octave> plot (x1, y1, 'ro', 'markersize', 10);
octave> plot (x2, y2, 'bo', 'markersize', 10);
とすると、



 のようなグラフが表示されます。
gnuplotですね。

Octaveメモ(2)

ファイルに定義した関数をロードして使用する方法。

[hello.m]
function hello()
    printf("Hello, world!\n");
endfunction
[cube.m]
function ret = cub(x)
    ret = x * x * x;
endfunction;

addpath関数を使って関数ファイルが格納されているディレクトリにパスを通す。今回の例では~/programming/octaveに上の2つのファイルがあるとする。
octave> addpath("~/programming/octave");
octave> hello();
Hello, world!
octave> cube(9)
ans =  729

Octaveメモ(1)

GNU Octaveをインストールした。
当初quadratic programmingのソルバーにCGALを使う予定だったが、OctaveにもQPのソルバーが入ってるようなのでこちらを使うことにした。学生時代に使っていたMATLABと似ているのでOctaveの方が個人的には使いやすい。

インストール
ubuntu universeのレポジトリに含まれているのでapt-getで。
sudo apt-get install octave


QPを解いてみる
とりあえず手計算でも解ける簡単な問題から。
ソルバーの使い方はここ

octave> X0 = [0;0;0];
octave> H = [2,0,0;0,2,0;0,0,2];
octave> Q = [0;0;0];
octave> A = [1,1,1];
octave> B = [1];
octave> LB = [];
octave> UB = [];
octave> A_LB = [];
octave> A_IN = [1,1,1];
octave> A_UB = [];
octave> [X, OBJ, INFO, LAMBDA] = qp (X0, H, Q, A, B, LB, UB,A_LB, A_IN, A_UB);
octave> X
X =

   0.33333
   0.33333
   0.33333

octave> OBJ
OBJ =  0.33333
octave> LAMBDA
LAMBDA =  0.66667
いいですねぇ、使いやすいです。

2013年2月25日月曜日

Facebook Hacker Cup 2013 Digits War

問題概要
数字iと数字jが戦争状態にある場合、iとjは隣接することはできない。またiとjの間に1つしか別の数字がないという状況も許されない。 このような状況で、桁数がk以下の数字は何通り作ることができるか?

解法
動的計画法&行列の累乗の計算(繰返二乗法)。初見は簡単と思ったけど、leading zeroの扱いがややこしかった。

ソースコード
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<long long> > matrix;

long long MOD = 1000000007;
int war[10][10];

matrix operator* (const matrix &x, const matrix &y) {
    int n = x.size();
    matrix ret(n, vector<long long>(n, 0));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++) {
                ret[i][j] += x[i][k] * y[k][j] % MOD;
                ret[i][j] %= MOD;
            }

    return ret;
}

vector<long long> operator* (const matrix &x, const vector<long long> &y) {
    int n = y.size();
    vector<long long> ret(n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            ret[i] += x[i][j] * y[j] % MOD;
            ret[i] %= MOD;
        }
    return ret;
}

long long solve() {
    long long k;
    cin >> k;

    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            cin >> war[i][j];

    matrix A(101, vector<long long>(101));
    for (int k = 0; k < 10; k++)
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++)
                if (!war[i][k] && !war[k][j] && !war[i][j])
                    A[10*i+k][10*k+j] = 1;

    for (int i = 1; i < 10; i++)
        for (int j = 0; j < 10; j++)
            A[100][10*i+j] = 1;
    A[100][100] = 1;

    vector<long long> x(101);
    x[100] = 9;
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            if (!war[i][j])
                x[10*i+j] = 1;

    --k;
    while (k > 0) {
        if (k & 1)
            x = A * x;
        k >>= 1;
        A = A * A;
    }
    
    return x[100];
}

int main() {
    int t;
    scanf("%d", &t);

    for (int i = 0; i < t; i++) {
        printf("Case #%d: ", i+1);
        long long ret = solve();
        cout << ret << endl;
    }

    return 0;
}

2013年2月17日日曜日

トランザクション内のselectについて

 勉強不足のため間違ったことを書いているかもしれません。間違いがあれば、ご指摘いただければと思います。

それでは本題に入ります。

常識なのかもしれないですが、MySQL(engine = InnoDB)でトランザクションを使っていて気付いたこと。

「トランザクション内でselectを使う場合、もしselectしたデータを変更するのであれば、for updateを必ずつけないといけない。」

 トランザクション内のselect文にfor updateをつけないと、dirty readと呼ばれる現象が発生することがあります。例えば、

id account_no name deposit
1 12345678 yamada taro 1000
2 77777777 sato hanako 400000

のようなテーブルがあったとします。

今id=1の口座の預金額(deposit)が1, 000円だったとします。
トランザクションAが開始され、id = 1の口座から1, 000円引きます。トランザクションAは、まだcommitされていない状態とします。

このとき別のトランザクションBがid = 1の口座の預金額を参照すると、1, 000円になります。トランザクションAはコミットされていないので、他のトランザクションから見ると、預金額は0円ではなく1,000円となります。

ここでトランザクションBが、「id=1の口座から500円引く」とう処理を行うと1,000 - 500 = 500円がid=1の口座の預金額になりおかしなことになってしまいます。(トランザクションAの処理が無かったことになる。)

このようにコミットされる前の古いデータを読んでしまうことをdirty readと言います。

(↑この部分は自信がありません。
MySQLのInnoDBのデフォルトのisolation levelはrepeatable readでこのisolation levelではdirty readは発生しない[参照1]。とあるので、上の現象はdirty readと呼ばないのか?それとも更新のために使うselectにはfor updateをつける前提で話をしているのか?)

これを防止するためには、トランザクションBでデータを取得するときにselect for update文を使います。for updateを付けると、トランザクションAがcommit/rollbackされるまでデータは取得されません。



2013年2月16日土曜日

Learn iBATIS(1)

iBATISを使ってみました。

設定
Mavenを使ってjarファイルを取得しました。データベースはMySQLを使用します。
<dependencies>
    <dependency>
        <groupId>org.apache.ibatis</groupId>
        <artifactId>ibatis-sqlmap</artifactId>
        <version>2.3.4.726</version>
    </dependency>
    <dependency>
        <groupId>mysql</groupId>
        <artifactId>mysql-connector-java</artifactId>
        <version>5.1.6</version>
    </dependency>
</dependencies>


サンプル
基本的なCRUD属性の処理を一通り試してみました。

まず、iBATISの設定ファイルです。
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE sqlMapConfig PUBLIC "-//iBATIS.com//DTD SQL Map Config 2.0//EN"
 "http://www.ibatis.com/dtd/sql-map-config-2.dtd">

<sqlMapConfig>
    <settings useStatementNamespaces="true" />
    
    <transactionManager type="JDBC">
        <dataSource type="SIMPLE">
            <property name="JDBC.Driver" value="com.mysql.jdbc.Driver" />
            <property name="JDBC.ConnectionURL" value="jdbc:mysql://localhost:3306/sample" />
            <property name="JDBC.Username" value="user" />
            <property name="JDBC.Password" value="password" />
        </dataSource>
    </transactionManager>

    <sqlMap resource="ibatis/employee-mapping.xml" />

</sqlMapConfig>
DBの設定とマッピングファイルのパスを指定します。

次に、マッピングファイルです。
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE sqlMap PUBLIC "-//ibatis.apache.org//DTD SQL Map 2.0//EN" "http://ibatis.apache.org/dtd/sql-map-2.dtd">
<sqlMap namespace="employee">

    <select id="select" resultClass="Employee">
        <![CDATA[
            select 
                id, 
                name,
                age,
                department
            from
                employee
            where id = #value#
        ]]>
    </select>

    <select id="selectAll" resultClass="Employee">
        <![CDATA[
            select 
                id, 
                name,
                age,
                department
            from
                employee
        ]]>
    </select>

    <update id="update" parameterClass="Employee">
        <![CDATA[
            update
                employee
            set
                name = #name#,
                age = #age#,
                department = #department#
            where
                id = #id#
        ]]>
    </update>

    <insert id="insert" parameterClass="Employee">
        <![CDATA[
            insert into
                employee(name, age, department)
            values(#name#, #age#, #department#)
        ]]>
    </insert>
    
    <delete id="delete" parameterClass="Employee">
        <![CDATA[
            delete from 
                employee
            where
                name = #name# and
                age = #age# and
                department = #department#        
        ]]>
    </delete>
</sqlMap>

おっと、忘れてました。
データベースには以下のテーブルを作成しておきます。

CREATE TABLE `employee` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `department` varchar(32) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB

で、上のDBがマッピングされるEntity Beanを作成します。

public class Employee {
    public int id;
    public String name;
    public int age;
    public String department;
    public int getId() {
        return id;
    }
    public Employee(){}
    public Employee(String name, int age, String department) {
        this.name = name;
        this.age = age;
        this.department = department;
    }
    
    public void setId(int id) {
        this.id = id;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    public String getDepartment() {
        return department;
    }
    public void setDepartment(String department) {
        this.department = department;
    }
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(id);
        sb.append(" ");
        sb.append(name);
        sb.append(" ");
        sb.append(age);
        sb.append(" ");
        sb.append(department);
        return sb.toString();
    }
}

最後に、メインクラスです。

import java.io.Reader;
import java.util.List;

import com.ibatis.common.resources.Resources;
import com.ibatis.sqlmap.client.SqlMapClient;
import com.ibatis.sqlmap.client.SqlMapClientBuilder;

public class Main {
    public static void main(String[] args) throws Exception {
        Reader reader = Resources.getResourceAsReader("ibatis/ibatis-config.xml");
        SqlMapClient sqlMap = SqlMapClientBuilder.buildSqlMapClient(reader);

        /*
         * select an employee by his/her id
         */
        Employee employee = (Employee) sqlMap.queryForObject("employee.select", 1);
        System.out.println(employee);
        
        /*
         * select all employees
         */
        List<Employee> employees = sqlMap.queryForList("employee.selectAll");
        
        /*
         * update the selected employee
         */
        employee.setAge(employee.getAge()+1);
        sqlMap.update("employee.update", employee);
        
        /*
         * insert a new employee
         */
        sqlMap.insert("employee.insert", new Employee("nichole", 22, "Finance"));
        employees = sqlMap.queryForList("employee.selectAll");
        
        /*
         * delete an employee
         */
        sqlMap.delete("employee.delete", new Employee("nichole", 22, "Finance"));
        employees = sqlMap.queryForList("employee.selectAll");
    }
}
シンプルで使いやすいですね。

tomcatのクラスパスにmaven dependenciesを含める

前回悩んでいたことが解決したので、メモしておきます。

mavenのライブラリ管理
pom.xmlに使用したいライブラリおよびバージョンを記述すると、自動的にライブラリをダウンロードしクラスパスの設定をしてくれます。依存するライブラリも自動的にダウンロードしてくれます。
さらに、クラスファイルとソースコードの紐付けまで自動でやってくれます。(Attach Source不要)

Tomcatのクラスパスにmaven dependenciesを含める方法
Eclipse上で対象のプロジェクトを右クリック -> properties -> Deployment Assembly -> Add -> Java Build Path Entries -> Maven Dependencies

これだけです。

2013年2月13日水曜日

Learn Struts(9)

ついにここまで来たー!
ようやくStruts1とSpringを連携させることが出来ました。

設定
mavenで追加したライブラリをtomcatのクラスローダに認識させる方法が分からずに手作業でやりました。(プラグイン使うとうまくクラスパスの設定ができるようなので、後で調べたいと思います。)
以下の2つのjarファイルをWEB-INF/libに追加します。
  • spring.jar
  • spring-webmvc-struts.jar
これだけです。

サンプル
簡単なサンプルを書きました。インスタンスの生成する処理も、DIコンテナからBeanを取得する処理も、ソースコード上にはありません。インスタンスの生成はDIコンテナが、Beanの取得はDelegatingActionProxyが行います。DelegatingActionProxyの内部処理は、単純ですが多態性と移譲をうまく使っていてなかなかおもしろいです。それではサンプルを見ていきましょう。

 まずstrutsの設定ファイル。ポイントは、plug-inタグでspringのプラグインをインポートするところです。あと/hogeへのリクエストをDelegatingActionProxyが受けているところも要チェック。
<?xml version="1.0" encoding="ISO-8859-1" ?>
<!DOCTYPE struts-config PUBLIC
          "-//Apache Software Foundation//DTD Struts Configuration 1.3//EN"
          "http://struts.apache.org/dtds/struts-config_1_3.dtd">

<struts-config>

    <action-mappings>
        <action path="/hoge" type="org.springframework.web.struts.DelegatingActionProxy"/>
    </action-mappings>

    <message-resources parameter="MessageResources" />
    
    <plug-in className="org.springframework.web.struts.ContextLoaderPlugIn">
        <set-property property="contextConfigLocation" value="/WEB-INF/applicationContext.xml" />
    </plug-in>

</struts-config>
次に、Springの設定ファイル。これはいつもどおりに書けばOKです。
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
       xmlns:context="http://www.springframework.org/schema/context"
       xmlns:aop="http://www.springframework.org/schema/aop"
       xsi:schemaLocation="
        http://www.springframework.org/schema/beans 
        http://www.springframework.org/schema/beans/spring-beans-2.5.xsd
        http://www.springframework.org/schema/context
        http://www.springframework.org/schema/context/spring-context-2.5.xsd
        http://www.springframework.org/schema/aop 
        http://www.springframework.org/schema/aop/spring-aop-2.5.xsd">

    <context:component-scan base-package="main.java.controller" />
    <context:component-scan base-package="main.java.service" />
</beans>
次にコントローラークラス。リクエストを処理するパスと同じ名前のBean名をつけます。
package main.java.controller;

import java.io.PrintWriter;

import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

import main.java.service.CalcService;

import org.apache.struts.action.Action;
import org.apache.struts.action.ActionForm;
import org.apache.struts.action.ActionForward;
import org.apache.struts.action.ActionMapping;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Controller;

@Controller("/hoge")
public class HogeAction extends Action {
    @Autowired
    CalcService service;
    
    @Override
    public ActionForward execute(ActionMapping mapping, ActionForm form,
            HttpServletRequest request, HttpServletResponse response)
            throws Exception {
        
        int x = 10;
        int y = 2;
        
        PrintWriter writer = response.getWriter();
        writer.write(x + " + " + y + " = " + service.add(x, y) + "<br/>");
        writer.write(x + " - " + y + " = " + service.sub(x, y) + "<br/>");
        writer.write(x + " * " + y + " = " + service.mul(x, y) + "<br/>");
        writer.write(x + " / " + y + " = " + service.div(x, y) + "<br/>");
        
        return null;
    }
}
最後に、サービスクラス。コントローラーから@Autowiredで注入される機能です。
package main.java.service;

public interface CalcService {
    public int add(int x, int y);
    public int sub(int x, int y);
    public int mul(int x, int y);
    public int div(int x, int y);
}
package main.java.service;

import org.springframework.stereotype.Service;

@Service
public class CalcServiceImpl implements CalcService {

    @Override
    public int add(int x, int y) {
        return x + y;
    }

    @Override
    public int sub(int x, int y) {
        return x - y;
    }

    @Override
    public int mul(int x, int y) {
        return x * y;
    }

    @Override
    public int div(int x, int y) {
        return x / y;
    }

}
これで、MVCフレームワークとDI×AOPフレームワークの連携ができました。次の目標はORMとの連携です。

2013年2月12日火曜日

Learn Spring Framework (4)

 昨日のAOPをアノテーションで書いてみました。
最近は、xml→アノテーションってのが主流なんですかね。Tomcatも7.0からアノテーションによるサーブレット、フィルター、リスナーの定義ができるようになってますし。

それではサンプルを説明していきます。
まず、xmlファイルです。ここにはAOPの定義は書かずに、aop:aspectj-autoproxyというタグを記述しておきます。
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
       xmlns:context="http://www.springframework.org/schema/context"
       xmlns:aop="http://www.springframework.org/schema/aop"
       xsi:schemaLocation="
        http://www.springframework.org/schema/beans 
        http://www.springframework.org/schema/beans/spring-beans-2.5.xsd
        http://www.springframework.org/schema/context
        http://www.springframework.org/schema/context/spring-context-2.5.xsd
        http://www.springframework.org/schema/aop 
        http://www.springframework.org/schema/aop/spring-aop-2.5.xsd">

    <aop:aspectj-autoproxy />
    <context:component-scan base-package="main.java.component" />
    <context:component-scan base-package="main.java.aop" />
</beans>
次に、アドバイスクラス。まず@ComponentでBean定義します。そして、@Aspectを付与することでこのクラスをアドバイスクラスとして使うことをSpringに教えてあげます。メソッドに@After、@Before、@Aroundを付与することで、それぞれAfter Advice、Before Advice、Around Adviceとして動作させることができます。
@Afterの中の"PointCutDefine.allComponentDir()"ですが、これはポイントカットが定義されているメソッドを指します。ちょっとややこしいですが、ポイントカットそのものではなく、ポイントカットが定義されているメソッドを指します。
package main.java.aop;

import org.aspectj.lang.ProceedingJoinPoint;
import org.aspectj.lang.annotation.After;
import org.aspectj.lang.annotation.Around;
import org.aspectj.lang.annotation.Aspect;
import org.aspectj.lang.annotation.Before;
import org.springframework.stereotype.Component;

@Aspect
@Component
public class AdviceExample {
    /*
     * before advice
     */
    @Before("PointCutDefine.allComponentDir()")
    public void before() {
        System.out.println("AdviceExample#before()");
    }
    
    /*
     * after advice
     */
    @After("PointCutDefine.allComponentDir()")
    public void after() {
        System.out.println("AdviceExample#after()");
    }
    
    /*
     * around advice
     */
    @Around("PointCutDefine.allComponentDir()")
    public Object around(ProceedingJoinPoint method) throws Throwable {
        Object ret = null;
        System.out.println("AdviceExample#around() -- begin");
        ret = method.proceed();
        System.out.println("AdviceExample#around() -- end");        
        return ret;
    }
}
最後に、ポイントカットを定義しているクラスです。ポイントカットの定義は各アドバイスの中で個別に定義することもできますが、ポイントカット定義のためのクラスを作成し共通で使用されるポイントカットを一ヶ所にまとめておくとスッキリすると思います。
package main.java.aop;

import org.aspectj.lang.annotation.Pointcut;

public class PointCutDefine {

    @Pointcut("execution(* main.java.component.*.*(..))")
    public void allComponentDir() {}
    
    @Pointcut("execution(* main.java.service.*.*(..))")
    public void allServiceDir() {}

    @Pointcut("execution(* main.java.controller.*.*(..))")
    public void allControllerDir() {}
    
}
あくまでも個人的な意見ですが、アノテーション使った方が美しいですね。