うるう年判定のアルゴリズム

質問

javaでうるう年判定のプログラムを作成しています。
プログラム自体はサーバにアップするときに実行結果が正しいかどうかテストされます。
仕様としては、
1.時間に関するAPIなどは一切使わずに完全に自作
2.入力される値はLong型の"秒"数(APIで提供されているのはミリ秒ですが)
3.60537895631062456L などの入力値に対して、年/月/日 (曜日) 時:分:秒 yday=元旦からの経過日数 を出力

最初は以下の関数を使用してループをかけていたのですが、仕様3の入力値に対して50秒近くかかってしまい、上手くいきませんでした。

public static int isLeap(int year){
if(year%4==0 && (year%100!=0 || year%400==0)) return 1;
return 0;
}

問題点はループ回数が多いことで、作る時点で分かってはいたのですが、ここまで遅くなるとは思っても見ませんでした。
これを使わない方法としては、一回だけうるう年(=n)を見つけ、その後は「(n+4)との比較+100で割り切れず400で割り切れる場合は別」という処理を行うことによって、処理時間を30秒付近にまで短縮することができたのですが、どうも10～15秒以内で終わらせなければテストにパスすることができないようです。

なんとか色々考えてはみたものの、上手いアルゴリズムは思いつきませんでした。
うるう年を処理するための"高速な"アルゴリズムはないのでしょうか。
お知恵を貸してください。よろしくお願いします。

回答No.2

amru05 · ベストアンサー

ちょっと考えてみましたが。。。（以下の数値の信頼性は疑問なので検算下さい）

１）秒を日に変える
　　60537895631062400 秒/86400=700670088322日(A)

２）それを４００年の日数でわる
　　400年＝365*303+366*97=146097日(B)
３）(A)/(B)の整数部分=4795923 (C)
４）(C)＊400年=1918369200年(D)
５）(A)-(B)*(C) ＝125791日(E) あまりの日数
６）(E)の日数について質問者のアルゴリズムで
　　年月日を求め、年＋(D)を加えたのが答えになる。

＝＝＞
　４００年の日数は決まっているので、４００年の何倍＋残りの日数にして、残りの日数についてのみ詳細に調べれば、どんなに大きな数字にしても、処理時間は最大でも４００年までの計算ですむ。。のでは。

＝＝＞
　この４００年についても、１００年、２００年、３００年などの日数を予め計算しておくと速いかも！！！

お礼

ありがとうございました。

400年周期を上手く利用する方法は考え付きませんでした。
実行時間は、9223372036854775807Lの入力値を10万回繰り返して平均8秒程度でした。

劇的な改善に驚いています。
本当にありがとうございました。

回答No.3

BLUEPIXY

#1補>このメソッドをループで回してしまうと、1京(!?)という回数をしようすることになり
なんでそんなことになるのかがわからんのです。
1970～ということなので扱う年数はたかだか４０年もないですよね。
全ての年で呼び出したとしても、そんなループにはなりません。
経過年数を求める所でループで処理しているというような意味なんでしょうが、その部分を補足していただきたいのです。
閏年を求める部分で大量に時間を消費しているとは思えないので、
その部分を別のアルゴリズムで置き換えたとしてもたいして意味はないと思います。
例えば、繰り返し、呼び出すということであれば、閏年は、最低４の倍数の年ですからそれ以外は呼び出さないということが有効かと思います。
なんにしても、プログラムを補足していただけませんか？

補足

先ほどまで作っていたものをそのまま移します。
改善前のソースコードです。
質問で書いた改善策はこのコードの約2.5倍程に膨れ上がっていましたので、消してしまいました。

このコードでは、大量にループが回ってしまいます。そのために困っていました。
(勉強不足で申し訳ありませんでした)

public class MyGmtimeTest {
public static void main(String[] args) {
TmStruct ts = new TmStruct();
long data[]={
0L,
1000000L,
946700000L,
978300000L,
1000000000L,
2000000000L,
10000000000L,
12345678901L,
13569380800L,
522332112440454L,
18377479112012556L,
22292847980662392L,
26365538581446204L,
28222145418915608L,
29231852447760948L,
44281340590217136L,
45014422379252560L,
54871114056418944L,
60537895631062456L,
Long.MAX_VALUE,
};
long start = System.currentTimeMillis();
for(int i=0; i<data.length; i++){
ts = GmtimeCalculator.gmtime(data[i]);
System.out.println(i+"|t="+data[i]+" : ");
System.out.println(i+"|"+(ts.getYear()+1900)+"/"+ts.getMon()+"/"+ts.getMDay()+""
+" ("+ts.getWDay()+") "
+ts.getHour()+":"+ts.getMin()+":"+ts.getSec()
+" yday="+ts.getYDay()+" isdist="+ts.getIsDst());
}
long stop = System.currentTimeMillis();

}
};

public class GmtimeCalculator {
public static TmStruct gmtime(long t) {
int m_day[][]={
{31,28,31,30,31,30,31,31,30,31,30,31,365},
{31,29,31,30,31,30,31,31,30,31,30,31,366},
};
TmStruct tm = new TmStruct();

/** 秒を処理 */
tm.setSec((int)(t%60L));
t /= 60L;

/** 分を処理 */
tm.setMin((int)(t%60L));
t /= 60L;

/** 時を処理 */
tm.setHour((int)(t%24L));
t /= 24L;

/** 曜日を処理 */
tm.setWDay((int)((t+4L)%7L));

/** 年を処理 */
int leap=0;
int y=1970;
for(;0<=(t-m_day[isLeap(y)][12]);y++){
t-=m_day[isLeap(y)][12];
}

tm.setYear(y-1900);

/** 元日からの経過日数を処理 */
tm.setYDay((int)t);
/** 経過日数から日付に変更 */
t++;

/** 月日を処理 */
int i;
for(i=0; 0<(t-(long)m_day[isLeap(y)][i]); i++){
t -= (long)m_day[isLeap(y)][i];
}
tm.setMDay((int)t);
i%=12; //月は0-11の範囲のため、剰余をとる
tm.setMon(i);

// 夏時間の設定(今回は使用しないため、0とする)
tm.setIsDst(0);
return tm;
}//TmStruct ここまで。
public static int isLeap(int year){
if((year%4==0)&&(year%100!=0 || year%400==0))
return 1;
return 0;
}
};

回答No.1

BLUEPIXY

閏年じたいの判定は
return (0 == year % 400)||((0 == year % 4)&&(0 != year % 100));
で良いと思います。
これをこれ以上速くすることはできないと思いますので、
問題は、このyear を求めている部分なんだと思いますが
どのようにされているのですか？

補足

早速の回答ありがとうございます。

このメソッド自体の処理速度を向上させたいわけではないのです。

作成しようと考えているプログラムは、入力値としてLong型を取り、時/分/秒を取り出した後、残った値(1970年1月1日からの経過日数)を処理し、経過年数,その年の月,その年の日を得たいのです。

私も
return (0 == year % 400)||((0 == year % 4)&&(0 != year % 100));
は使用していたのですが、このメソッドをループで回してしまうと、1京(!?)という回数をしようすることになり、実行時間を短縮することはできないのです。

というわけで、この方法を用いないアルゴリズムを探しているのです。ご存じないでしょうか。