1行で書けるうるう年判別法

ある年がうるう年(閏年)であるかどうかの判別は意外と複雑です。

  • 西暦が4で割り切れる年はうるう年
  • ただし、4で割り切れても100で割り切れる年はうるう年でない
  • ただし、100で割り切れても400で割り切れる年はうるう年

つまり、2004年、2008年、…、2096年はうるう年ですが、2100年は100で割り切れるためうるう年でありません(かわいそうなことに、2月29日生まれの人は、2096年から2104年まで、8年間も誕生日がやって来ないわけですね)。しかし、2000年はさらに400で割り切れるのでうるう年となります。

単純な判別

うるう年を単純に判別しようとすると、西暦を格納したyという変数があるとして、2月の日数を表す変数nに28か29を代入するには、

if(y % 4 == 0){
	if(y % 100 == 0){
		if(y % 400 == 0){
			n = 29;
		}else{
			n = 28;
		}
	}else{
		n = 29;
	}
}else{
	n = 28;
}

と、やや煩雑な条件分岐を書かなければなりません(%は余りを求める演算子。a % bはaをbで割った余り)。

1行での判別

上記のような条件判別をしなくても、1行でnを求めてしまう計算式をご紹介しましょう。

n = 28 + (1 / (y % 4 + 1)) * (1 - 1 / (y % 100 + 1)) + (1 / (y % 400 + 1));

これは、整数の割り算が割り切れない場合、切り捨てられることを利用しています。

1 / (y % 4 + 1)

はyが4の倍数の場合のみ1になりますよね。これを組み合わせて上の式になります。

四則演算のみでの判別

さらに、a % bはa - a / b * bで表せるという性質を使って、四則演算だけで上記の式を書き換えてみます。

n = 28 + (1 / (y - y / 4 * 4 + 1)) * (1 - 1 / (y - y / 100 * 100 + 1))
	+ (1 / (y - y / 400 * 400 + 1));

結論

2月の日数は条件分岐を使わなくても、上記のような計算式で簡単に求めることができます。

形態素解析ライブラリSenのエラーと原因究明方法

Java形態素解析ライブラリSenを使ってプログラムを書いていたのですが、実行環境を変えると急に動かなくなってしまいました。メモ代わりに対処法を残しておきます。

エラーメッセージとその原因など

私の場合、発生したエラーメッセージは

java.lang.IllegalArgumentException: unknown protocol: c

java.lang.IllegalArgumentException: Tokenizer Class: net.java.sen.ja.JapaneseTokenizer is invalid.

などです。例外が発生しているのはライブラリの奥深く、エラーメッセージも意味不明のため、どうしていいのかわかりません。


こんなときに頼りになるのがGoogle先生です!しかし、そもそも形態素解析Javaでやっている人の母数が小さいためか、Google先生もあまりこの問題には詳しくないようです。

それでも出てきた情報をまとめると次のようになります。

  • System.setProperty("sen.home", senHome)を忘れずに(senHomeはSenのディレクトリへのパス)。
  • VMのメモリ不足が原因の場合がある。
    • 実行時のオプションで-Xms(初期ヒープサイズ)、-Xmx(最大ヒープサイズ)を指定(例:最大ヒープサイズを256MBにするには、-Xmx256mを指定)
  • Program Filesのような、スペースを含むパスを指定するとエラーになるおそれあり(移行前のマシンでは動いたのに移行後はエラー発生)
    • スペースを含まないパスで指定できる場所にSenをディレクトリごと移動
  • SenはIllegalArgumentExceptionを投げまくる(別の例外をcatchした上で、IllegalArgumentExceptionを投げているケースが多い)
    • IllegalArgumentExceptionが投げられる前に発生した例外の中身を見ることができれば原因究明できる可能性あり

原因究明方法

上記の最後の項についてですが、Senにはソースがついている(SEN_HOMEのsrc/javaの中)ので、sen.jarを使わずに、そのソースのプログラムを書き換えて使うことで、本当の原因となっている例外のメッセージやスタックトレースを表示できます。


例えば、

java.lang.IllegalArgumentException: unknown protocol: c
at net.java.sen.StringTagger.readConfig(StringTagger.java:310)
at net.java.sen.StringTagger.init(StringTagger.java:145)
at net.java.sen.StringTagger.(StringTagger.java:95)
at net.java.sen.StringTagger.getInstance(StringTagger.java:13
(以下省略)

というエラーメッセージの場合は、StringTagger.javaの310行目でIllegalArgumentExceptionがスローされています。この部分を見てみると、

        } catch (IOException e) {
            throw new IllegalArgumentException(e.getMessage());
        }

となっており、実はIOExceptionが発生していることがわかります。そこで、このIOExceptionのエラーメッセージを見るために

        } catch (IOException e) {
            e.printStackTrace();
            throw new IllegalArgumentException(e.getMessage());
        }

のようにソースを書き換えてしまいます。


このようにして、意味不明のエラーメッセージの裏側で、実は何が起こっているのかを調べることができます。

(ちなみに、私の場合はパス中の「Program Files」のスペースがよくなかったようです。移行前の環境では(Windows XP同士の移行なのに)動いていたので謎です)

参考サイト

調べた中で特に役立ったものを挙げておきます。特に、原因究明の方法は二つ目のブログのやり方そのままです。

Google Chrome(V8)のベンチマーク(Firefox、Safariとの比較)

先日Googleブラウザ「Google Chrome」のベータ版が公開されました。速い速いと言われているChromeJavaScriptエンジン「V8」がどの程度速いのか、ベンチマークテストでためしてみました。


(グラフの縦軸はChromeを1としたときの実行時間です)

環境

OS Windows XP SP2
CPU Pentium 4 3.33GHz
Memory 1.49GB
ブラウザ バージョン
Chrome 0.2.149.27
Firefox 3.0.1
Safari 3.1.2

結果の詳細

Chrome
Firefox
Safari


IEは、このマシンにIE6しか入ってなかったので比較からはずしましたが、参考までに、ChromeはIE6の約50倍速いという結果が出ました。

結論

やはりChromeのV8は相当速いみたいですね。正規表現が遅いのがやや気になりますが、他に関しては、日付処理で他エンジンと同等であるのを除いて圧倒的なスピードのようです。Firefox

HashMapの注意点

HashMapを使う上での注意点について説明します。

Map型変数を使う

HashMapオブジェクトを格納するには、HashMap型変数ではなくMap型変数を使います

// HashMapオブジェクトの生成
Map<String, String> map = new HashMap<String, String>();

HashMapはMapの実装の一つに過ぎません。HashMapをMapとして使っているのであればMap型変数に格納した方が自然です。また、パフォーマンス上の問題で他のマップ(TreeMapなど)と差し替えることが容易になるなど、プログラムの汎用性が上がります。HashMap独自の操作が必要である場合(あまり思いつきませんが)を除いてMap型変数を使いましょう。

初期容量と負荷係数

HashMap生成時のパラメータとして、初期容量負荷係数があります。


初期容量は、HashMapが内部的に保持しているハッシュテーブル自体のサイズ(デフォルトで16)です(ハッシュテーブルの仕組みについてはhttp://www.geocities.jp/ky_webid/algorithm/014.htmlを参照)。格納する要素の数に対してテーブルのサイズが著しく小さいと、ハッシュテーブルのパフォーマンスが劣化してしまいます。そのため、ハッシュテーブルがある程度いっぱいになると、自動的にハッシュテーブルの拡張(新たに大きなテーブルを生成して、要素を格納しなおす作業)が行われます。ハッシュテーブルがどの程度埋まるとテーブルの拡張を行うかという割合を表したものが負荷係数(デフォルトで0.75)です。

なぜハッシュテーブルがいっぱいになってから拡張を行わないのかというと、ハッシュテーブルのキーとなるハッシュ値は基本的に重複するものだからです。サイズ100のハッシュテーブルに100個の要素を挿入したとしても、ハッシュテーブルがすべて埋まることはまずありません*1ハッシュ値の重複が起こっても要素が置き換えられるようなことは起こりませんが、パフォーマンスが劣化します。そのため、ハッシュテーブルがある程度埋まってきた段階でテーブルを拡張する必要があります。


基本的には初期設定のまま*2で使って問題ありません。

// 初期容量16、負荷係数0.75でHashMapを生成
Map<String, String> map = new HashMap<String, String>();


大量の要素を挿入したい場合は、初期容量を挿入する要素数 * 4 / 3に設定すると良いでしょう。この要素数 * 4 / 3というのは、この値に負荷係数0.75をかけたときにちょうど1となる値です。要素数が大体でしかわからない場合は、少し大きい目の値 * 4 / 3を目安にすると良いでしょう。

// 挿入する要素数n
int n = 100000;

// 初期容量n * 4 / 3、負荷係数0.75でHashMapを生成
Map<String, String> map = new HashMap<String, String>(n * 4 / 3);


挿入する要素の数がわかっていて、それ以上の要素を追加することがないのであれば負荷係数を大きく設定しても良いでしょう。

// 挿入する要素数n
int n = 100000;

// 初期容量n、負荷係数1.0でHashMapを生成
Map<String, String> map = new HashMap<String, String>(n, 1.0f);

ハッシュテーブルのサイズとIterator

ハッシュテーブルの性質を考えると、メモリが許せば容量を大きく設定しておけばパフォーマンスが高くなるように思えます。しかし、そこに落とし穴があります。

ハッシュテーブルから全要素を取り出す場合(Iteratorなどを用いる場合)、要素数に比べてハッシュテーブルのサイズが著しく大きいと、パフォーマンスが著しく低下します。これは、ハッシュテーブルから全要素を取り出すためにはテーブル全体を走査しなければならないためです。


ですので、初期容量を要素数に対して大きく設定しすぎない*3ように注意が必要です。挿入(put)、参照(get)、削除(remove)しか行わないのであれば、少々初期容量が大きくてもパフォーマンスに大きな劣化はありません。

同期化(スレッドセーフなHashMap)

Collections.synchronizedメソッドを用いることでスレッドセーフなHashMapを得ることができます。同期化を目的としてHashtableを使うのは望ましくありません詳細はこちら)。

Map<String, String> map = Collections.synchronizedMap(new HashMap<String, String>());

TreeMapとの性能比較

基本的にHashMapはTreeMapより速いです。TreeMapの性質(要素をソートして取り出す)が必要にならない限り、HashMapを用いた方が良いでしょう。パフォーマンス比較の結果については
ハッシュは二分木(ツリー)より速い(ハッシュとツリーの速度比較)
をご覧下さい。

自作クラスをキーにする場合(equalsメソッドとhashCodeメソッドのオーバーライド)

PHP連想配列などと違い、HashMapのキーはStringでなければならないわけではありません。Javaでは任意のクラスのインスタンスをキーにとることができます。ただし、正確かつ高速な動作を期待するためには、equalsメソッドとhashCodeメソッドを適切にオーバーライドすることが必要となります。


hashCodeメソッドとequalsメソッドはObjectクラスで定義されているメソッドで、すべてのクラスが持っているメソッドです(すべてのクラスはObjectを継承しています)。

equalsメソッド(戻り値はboolean)は、二つのインスタンスが同一のものである場合にtrueを返すように定義(オーバーライド)する必要があります。例えば、Stringクラスでは、同一の文字列に対してtrueを、Integerクラスでは同一の値に対してtrueを返すように定義されています。

hashCodeメソッド(戻り値はint)はハッシュ値*4を返すメソッドで、equalsメソッドがtrueを返す(同一の内容を表す)インスタンス同士は必ず同じ値を返す必要があります。ただし、equalsメソッドがfalseを返す(異なる内容を表す)インスタンス同士が同じ値を返しても構いません。あくまで、同一の内容を表すインスタンス同士が同じ値を返すことが規定されているだけです。とはいえば、異なる内容を表すインスタンス同士は異なるハッシュ値を返した方がHashMapのパフォーマンスが向上します。


例えば、年と月(2008年8月など)を表すクラス、YearMonthを考えてみましょう。年と月が等しいYearMonthは同一の内容を表すYearMonthとなります。equalsメソッドとhashCodeメソッドは次のように定義すれば良いでしょう。

// 年、月を表すクラス
class YearMonth {
	// 年
	private int year;
	// 月
	private int month;

	public YearMonth(int year, int month) {
		this.year = year;
		this.month = month;
	}

	// 自分自身とobjが同じYearMonthである場合のみtrueを返す。
	public boolean equals(Object obj) {
		// 対象がYearMonthオブジェクトか判別する。
		if (obj instanceof YearMonth) {
			// YearMonth型にキャストする。
			YearMonth yearMonth = (YearMonth) obj;
			// year、month共に等しい場合のみtrueを返す。
			return this.year == yearMonth.year && this.month == yearMonth.month;
		} else {
			// YearMonthオブジェクトでなければ異なるオブジェクトなのでfalseを返す。
			return false;
		}
	}

	// equalsメソッドがtrueになる二つのYearMonthオブジェクトは必ず同じ値を返す。
	// ただし、equalsメソッドがfalseとなる二つのYearMonthオブジェクトが
	// 必ず異なる値を返さなければならないわけではない。
	public int hashCode() {
		// このようにすれば、異なるYearMonthでは異なるハッシュ値を返す。
		return year * 12 + month;
	}
}

結論

  • HashMapオブジェクトはできるだけMap型変数に格納する。
  • 初期容量と負荷係数を適切に設定する。
  • 同期化を行う場合はCollections.synchronizedメソッドを用いる。
  • 自作クラスをキーにする場合には、equalsメソッドとhashCodeメソッドのオーバーライドを忘れずに。

*1:ハッシュテーブルの仕組みについてはhttp://d.hatena.ne.jp/jamey_star/20080225/1203879426http://www.yuge.ac.jp/home/~nagao/teaching/algo_2003/Search/hash/http://d.hatena.ne.jp/jamey_star/20080225/1203879426などが参考になる。

*2:引数なしコンストラクタでHashMapを生成すると、初期容量16、負荷係数0.75となる。

*3:一概にこのくらいとは言えないが、要素数の10倍、20倍になるような設定は良くないだろう。要素数が事前にわかっているのであれば要素数 * 4 / 3が望ましい。

*4:厳密には、hashCodeメソッドをさらに操作した値がHashMap内部で計算され、ハッシュテーブルのキーとして用いられている。

Javaで多重継承する方法

Javaでは言語仕様的に多重継承が許されていません。これは、メソッド名が重複した場合の処置など、多重継承が様々な問題を引き起こしやすいからです(C++でプログラムを書くとよくわかります)。とはいえ、どうしても多重継承をしたい場合というのもあります。そこで、Javaではインタフェースを使って擬似的に多重継承ができるようになっています(PHPでも同じ)。

(このエントリーはクラス、継承、抽象クラスなどについて最低限の知識のある人を対象としています)


以下、インタフェースを用いた擬似的多重継承の方法を説明します。

ClassAとClassB

まず、次のような二つのクラス、ClassAとClassBを考えます。

class ClassA {
	private int a;

	public ClassA(int a) {
		this.a = a;
	}

	public int getA() {
		return this.a;
	}
}
class ClassB {
	private int b;

	public ClassB(int b) {
		this.b = b;
	}

	public int getB() {
		return this.b;
	}
}


この二つのクラスを継承したClassABを作りたい場合を考えてみましょう。↓のようにできれば良いのですが、これはできません。

class ClassAB extends ClassA, ClassB {
...
}

ClassBのinterfaceを作り、実装する

次に、擬似的な多重継承のためにClassBのインタフェースを作ります。インタフェースとは、抽象メソッドしか持たない抽象クラスのようなものです(違いについては後記)。

interface InterfaceB {
	public int getB();
}

「クラスを継承する」のに対して「インタフェースを実装する」と言います。クラスを多重継承することはできませんが、インタフェースは多重実装することができます(抽象メソッドしか持たない抽象クラスを多重継承することはできませんが、インタフェースは多重実装できるという意味で抽象メソッドしか持たない抽象クラスと異なります)。

インタフェースは抽象メソッドしか持たないことが保障されているので、メソッド名の重複が起こっても、その処理の方法を必ずプログラマが記述することになります。


ClassBはInterfaceBを実装して次のようにします(implements InterfaceBが増えただけ)。

class ClassB implements InterfaceB {
	private int b;

	public ClassB(int b) {
		this.b = b;
	}

	public int getB() {
		return this.b;
	}
}

ClassAB(ClassAとClassBを多重継承したクラス)

まず解説より先に多重継承のソースを示します。

class ClassAB extends ClassA implements InterfaceB {
	// 多重継承したいClassBのインスタンスを保持する。
	private ClassB instanceB;

	public ClassAB(int a, int b) {
		super(a);

		// ClassBのインスタンスを、与えられた引数で生成。
		this.instanceB = new ClassB(b);
	}

	// InterfaceB#getBメソッドを実装する必要がある。
	// 動作の中身はinstanceB(ClassB)に完全に任せてしまう。
	public int getB() {
		return this.instanceB.getB();
	}
}

やっていることは、

  • InterfaceBを実装
  • ClassBのインスタンスをprivateフィールド(instanceB)に保持
  • メソッドの中身はinstanceBに丸投げ

です。

以下、順に解説します。

InterfaceBを実装

ClassABにはInterfaceBを実装させます。インタフェースはいくつでも実装できるので、ClassAを継承していようがInterfaceBを実装することができます。

class ClassAB extends ClassA implements InterfaceB {
ClassBのインスタンスをprivateフィールド(instanceB)に保持

次に、多重継承したいクラス(この場合ClassB)のインスタンスを保持するprivateフィールドを作成します。

// 多重継承したいClassBのインスタンスを保持する。
private ClassB instanceB;
メソッドの中身はinstanceBに丸投げ

あとは、すべてをinstanceBに丸投げしてしまいます。例えば、ClassABで実装しなければならないgetBメソッドは

public int getB() {
	return this.instanceB.getB();
}

です。instanceBに仕事をさせて、その結果を返しているだけです。この例ではInterfaceBが持っているメソッドが一つしかありませんが、もし仮に10個のメソッドがあれば、これと同じような丸投げの処理を10個書きます。


このようにすれば、InterfaceBのメソッドをすべて持つことを強制された、しかし、その動作はClassBによって決められたClassABを作ることができます。見かけ上は、ClassBを継承しているのと同じです*1

実行例

ClassABは次のようにして使えます。外から見ると、まるでClassBも継承されているようです。

public class MultipleInheritance {
	public static void main(String[] args) {
		ClassAB instanceAB = new ClassAB(100, 200);

		System.out.println(instanceAB.getA()); // 100と表示
		System.out.println(instanceAB.getB()); // 200と表示
	}
}

結論

このようにして、Javaでは擬似的な多重継承ができます。もちろん、ClassAとClassBを入れ替えても(InterfaceAを作ってそれを実装しても)問題ありません。

*1:厳密には、ClassABはClassAやInterfaceBとしては扱えるがClassBとしては扱えないという意味で違う。

PHPで多重継承する方法

PHPでは言語仕様的に多重継承が許されていません。これは、メソッド名が重複した場合の処置など、多重継承が様々な問題を引き起こしやすいからです(C++でプログラムを書くとよくわかります)。とはいえ、どうしても多重継承をしたい場合というのもあります。そこで、PHPではインタフェースを使って擬似的に多重継承ができるようになっています(Javaでも同じ)。

(このエントリーはクラス、継承、抽象クラスなどについて最低限の知識のある人を対象としています)


以下、インタフェースを用いた擬似的多重継承の方法を説明します。

ClassAとClassB

まず、次のような二つのクラス、ClassAとClassBを考えます。

<?php
class ClassA {
	private $a;

	public function __construct($a){
		$this->a=$a;
	}

	public function getA(){
		return $this->a;
	}
}

class ClassB {
	private $b;

	public function __construct($b){
		$this->b=$b;
	}

	public function getB(){
		return $this->b;
	}
}
?>


この二つのクラスを継承したClassABを作りたい場合を考えてみましょう。↓のようにできれば良いのですが、これはできません。

<?php
class ClassAB extends ClassA, ClassB {
...
}
?>

ClassBのinterfaceを作り、実装する

次に、擬似的な多重継承のためにClassBのインタフェースを作ります。インタフェースとは、抽象メソッドしか持たない抽象クラスのようなものです(違いについては後記)。

<?php
interface InterfaceB {
	public function getB();
}
?>

「クラスを継承する」のに対して「インタフェースを実装する」と言います。クラスを多重継承することはできませんが、インタフェースは多重実装することができます(抽象メソッドしか持たない抽象クラスを多重継承することはできませんが、インタフェースは多重実装できるという意味で抽象メソッドしか持たない抽象クラスと異なります)。

インタフェースは抽象メソッドしか持たないことが保障されているので、メソッド名の重複が起こっても、その処理の方法を必ずプログラマが記述することになります。


ClassBはInterfaceBを実装して次のようにします(implements InterfaceBが増えただけ)。

<?php
class ClassB implements InterfaceB {
	private $b;

	public function __construct($b){
		$this->b=$b;
	}

	public function getB(){
		return $this->b;
	}
}
?>

ClassAB(ClassAとClassBを多重継承したクラス)

まず解説より先に多重継承のソースを示します。

<?php
class ClassAB extends ClassA implements InterfaceB {
	// 多重継承したいClassBのインスタンスを保持する。
	private $instanceB;

	public function __construct($a, $b){
		parent::__construct($a);

		// ClassBのインスタンスを、与えられた引数で生成。
		$this->instanceB=new ClassB($b);
	}

	// InterfaceB#getBメソッドを実装する必要がある。
	// 動作の中身は$instanceB(ClassB)に完全に任せてしまう。
	public function getB(){
		return $this->instanceB->getB();
	}
}
?>

やっていることは、

  • InterfaceBを実装
  • ClassBのインスタンスをprivateフィールド($instanceB)に保持
  • メソッドの中身は$instanceBに丸投げ

です。

以下、順に解説します。

InterfaceBを実装

ClassABにはInterfaceBを実装させます。インタフェースはいくつでも実装できるので、ClassAを継承していようがInterfaceBを実装することができます。

<?php
class ClassAB extends ClassA implements InterfaceB {
?>
ClassBのインスタンスをprivateフィールド($instanceB)に保持

次に、多重継承したいクラス(この場合ClassB)のインスタンスを保持するprivateフィールドを作成します。

<<?php
// 多重継承したいClassBのインスタンスを保持する。
private $instanceB;
?>
メソッドの中身は$instanceBに丸投げ

あとは、すべてを$instanceBに丸投げしてしまいます。例えば、ClassABで実装しなければならないgetBメソッドは

<?php
public function getB(){
	return $this->instanceB->getB();
}
?>

です。$instanceBに仕事をさせて、その結果を返しているだけです。この例ではInterfaceBが持っているメソッドが一つしかありませんが、もし仮に10個のメソッドがあれば、これと同じような丸投げの処理を10個書きます。


このようにすれば、InterfaceBのメソッドをすべて持つことを強制された、しかし、その動作はClassBによって決められたClassABを作ることができます。見かけ上は、ClassBを継承しているのと同じです*1

実行例

ClassABは次のようにして使えます。外から見ると、まるでClassBも継承されているようです。

<?php
$instanceAB=new ClassAB(100, 200);
print($instanceAB->getA()."\n"); // 100と表示
print($instanceAB->getB()."\n"); // 200と表示
?>

結論

このようにして、PHPでは擬似的な多重継承ができます。もちろん、ClassAとClassBを入れ替えても(InterfaceAを作ってそれを実装しても)問題ありません。

*1:厳密には、ClassABはClassAやInterfaceBとしては扱えるがClassBとしては扱えないという意味で違う。

ストリートビューを滑らかに歩く

ストリートビューで街中をスムーズに移動するためのアプリケーションを作りました。

SmoothWalk powered by Google Maps Street View


Googleマップストリートビューは非常に興味深い機能ですが、繰り返し矢印を押して移動するのは結構面倒です。そこで、一本道では自動で進み続け、交差点に差しかかると進む道を選べるようなアプリケーションがあれば便利なんじゃないかと考えました。昨日の夜にちょっとだけ時間があったので早速実装してみました。

まだ機能も豊富でないし、使い勝手やデザインもイマイチですが、とりあえず動くようになったのでおいておきます。今日は時間がないので、機能追加などは後日。