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ベストアンサー
- 回答日時:
ちょっと考えてみましたが。
。。(以下の数値の信頼性は疑問なので検算下さい)1)秒を日に変える
60537895631062400 秒/86400=700670088322日(A)
2)それを400年の日数でわる
400年=365*303+366*97=146097日(B)
3)(A)/(B)の整数部分=4795923 (C)
4)(C)*400年=1918369200年(D)
5)(A)-(B)*(C) =125791日(E) あまりの日数
6)(E)の日数について質問者のアルゴリズムで
年月日を求め、年+(D)を加えたのが答えになる。
==>
400年の日数は決まっているので、400年の何倍+残りの日数にして、残りの日数についてのみ詳細に調べれば、どんなに大きな数字にしても、処理時間は最大でも400年までの計算ですむ。。のでは。
==>
この400年についても、100年、200年、300年などの日数を予め計算しておくと速いかも!!!
ありがとうございました。
400年周期を上手く利用する方法は考え付きませんでした。
実行時間は、9223372036854775807Lの入力値を10万回繰り返して平均8秒程度でした。
劇的な改善に驚いています。
本当にありがとうございました。
No.3
- 回答日時:
#1補>このメソッドをループで回してしまうと、1京(!?)という回数をしようすることになり
なんでそんなことになるのかがわからんのです。
1970~ということなので扱う年数はたかだか40年もないですよね。
全ての年で呼び出したとしても、そんなループにはなりません。
経過年数を求める所でループで処理しているというような意味なんでしょうが、その部分を補足していただきたいのです。
閏年を求める部分で大量に時間を消費しているとは思えないので、
その部分を別のアルゴリズムで置き換えたとしてもたいして意味はないと思います。
例えば、繰り返し、呼び出すということであれば、閏年は、最低4の倍数の年ですからそれ以外は呼び出さないということが有効かと思います。
なんにしても、プログラムを補足していただけませんか?
この回答への補足
先ほどまで作っていたものをそのまま移します。
改善前のソースコードです。
質問で書いた改善策はこのコードの約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
- 回答日時:
閏年じたいの判定は
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京(!?)という回数をしようすることになり、実行時間を短縮することはできないのです。
というわけで、この方法を用いないアルゴリズムを探しているのです。ご存じないでしょうか。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・14歳の自分に衝撃の事実を告げてください
- ・架空の映画のネタバレレビュー
- ・「お昼の放送」の思い出
- ・昨日見た夢を教えて下さい
- ・ちょっと先の未来クイズ第4問
- ・【大喜利】【投稿~10/21(月)】買ったばかりの自転車を分解してひと言
- ・メモのコツを教えてください!
- ・CDの保有枚数を教えてください
- ・ホテルを選ぶとき、これだけは譲れない条件TOP3は?
- ・家・車以外で、人生で一番奮発した買い物
- ・人生最悪の忘れ物
- ・【コナン30周年】嘘でしょ!?と思った○○周年を教えて【ハルヒ20周年】
- ・ハマっている「お菓子」を教えて!
- ・最近、いつ泣きましたか?
- ・夏が終わったと感じる瞬間って、どんな時?
- ・10秒目をつむったら…
- ・人生のプチ美学を教えてください!!
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・都道府県穴埋めゲーム
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
UWSCの終了の仕方
-
Escキーを押すと、中断する時と...
-
ループフリー
-
null 参照の例外が実行時に発生...
-
VBAでの一時停止と再開の方法
-
CSVファイルの特定の行だけを読...
-
スリザーリンクの問題をランダ...
-
画面を強制的に再描画させる方法
-
多重ループの抜けだし方
-
VB2010でCSVファイルの読み込み
-
DOSコマンドのループ内のTIMEコ...
-
vb.netからエクセル関数書き込み
-
VBAで3秒だけ時間を止めたい
-
GIFアニメをループさせたくない
-
レインボー色ってどうやって表...
-
.htaccessがループしてる?それ...
-
平方根 ニュートン法について
-
WinAPI「MsgWaitForMultipleObj...
-
ExcelVBAで、index、match関数...
-
イベントの発生を待つ
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
画面を強制的に再描画させる方法
-
DoEventsが必要な理由について
-
UWSCの終了の仕方
-
Escキーを押すと、中断する時と...
-
VBA for i=1 to lastrow
-
vb.netからエクセル関数書き込み
-
GIFアニメをループさせたくない
-
VBAでの一時停止と再開の方法
-
「人を傷つけることは悪いこと...
-
VBAで3秒だけ時間を止めたい
-
DOSコマンドのループ内のTIMEコ...
-
アクティブセルから、A列最終行...
-
CSVファイルの特定の行だけを読...
-
範囲指定したセルを1つずつ飛...
-
ループフリー
-
VBA for文が止まらない
-
null 参照の例外が実行時に発生...
-
vbscriptでIE自動入力(途中で...
-
フラグについて
-
VBA Dir関数でファイルをループ...
おすすめ情報