前置きあるいは何したいのかとか。
なにこのタイトル？って思った人は幸せです。
タイトルに書いたような問題って、なにが楽しいのか、問題として出題されることが時々あります。
とある問題で汎用的かつそこそこ速く計算する方法を提出したところ、どうも想定された解き方と違ったようでした。
なので、そのコードを提示し、説明を加えたいと思ったわけです。
論理的試行（≠思考）とか。
わかりやすく4面ダイスをn回振って6で割った余りの数を求めてみます。
1回振った場合、余りを配列化するとN1{0,1,1,1,1,0}となります。
これは、余り0が0個,余り1が1個,余り2が1個,余り3が1子,余り4が0個、余り5が0個あることを表しています。
2回振った場合、このN1{0,1,1,1,1,0}に対して、それぞれ1～4が出た場合の数字の変化を考えます。
1回目の余りが0:N1[0]=0→(1～4)/6のあまりが0なんてありえないので計算しない。{0,0,0,0,0,0}
1回目の余りが1:N1[1]=1→1～4が出た場合、1+1～4それぞれN1[1]に。{0,0,1,1,1,1}
1回目の余りが2:N1[2]=1→1～4が出た場合、MOD(2+2～4,6)それぞれN1[2]に。{1,0,0,1,1,1}
1回目の余りが3:N1[3]=1→1～4が出た場合、MOD(3+2～4,6)それぞれN1[3]に。{1,1,0,0,1,1}
1回目の余りが4:N1[4]=1→1～4が出た場合、MOD(4+2～4,6)それぞれN1[4]に。{1,1,1,0,0,1}
1回目の余りが5:N1[5]=0→0のときと同じでありえないので計算しない。{0,0,0,0,0,0}
これを足し算してあげるとN2{3,2,2,2,3,4}となります。
同様にN3は{0,3,3,3,3,0},{0,0,2,2,2,2},{2,0,0,2,2,2},{2,2,0,0,2,2},{3,3,3,0,0,3},{4,4,4,4,0,0}を足した{11,12,12,11,9,9}となります。
このような処理をn回繰り返すと答えが求まります。
計算量はO(ダイスの面数×割る数×振る回数)です。
プログラム化とか。
プログラムに直すとこうなります。
/**
* 汎用ダイス余り数計算器
* @param dieMax 何面ダイスか
* @param dieCount 何回振るのか
* @param divNum どんな数字で割るのか
* @param modNum 余り幾つの数を求めるのか
* @return 結果
* dieMax面ダイスをdieCount回振り、divNumで割った余りがmodNumとなる数を求めよ問題を解く。
* 例：4面ダイスを10回振り、6で割った余りが3となる数を求めよ。→getDieDivideCount(4,10,6,3)=>174722
*/
private static int getDieDivideCount(
final int dieMax,final int dieCount,final int divNum,final int modNum){
int[]divList=new int[divNum];
//初期設定。
// Arrays.fill(divList,1,1,dieMax);
//dieMax<=divNumのときに誤動作するのを避ける。
for(int i=1;i<=dieMax;++i){
++divList[i%divNum];
}
//ダイスを1回ずつ振ったときのデータに更新し続ける。
for(int n=2;n<=dieCount;++n){
int[]tmp=new int[divNum];
for(int mod=0;mod<divNum;++mod){
for(int die=1;die<=dieMax;++die){
tmp[(mod+die)%divNum]+=divList[mod];
}
}
divList=tmp;
}
return divList[modNum];
}
と、ここまでが前座。
せっかくなのでこれをStream APIで書いてみたいと思います。
似非Stream化とか。
IntStreamはforの代わり！とどっかの偉い人が言ってたので、まずは、そういう クズ お手本のようなコードに直してみます。
private static int getDieDivideCountWithStream(
final int dieMax,final int dieCount,final int divNum,final int modNum){
final int[]divList=new int[divNum];
//初期設定。
IntStream.rangeClosed(1,dieMax).parallel().forEach(i->++divList[i%divNum]);
//ダイスを1回ずつ振ったときのデータに更新し続ける。
IntStream.rangeClosed(2,dieCount)
.forEach(n->{
int[]tmp=new int[divNum];
IntStream.range(0,divNum).forEach(mod->{
IntStream.rangeClosed(1,dieMax).forEach(die->{
tmp[(mod+die)%divNum]+=divList[mod];
});
});
System.arraycopy(tmp,0,divList,0,divNum);
});
return divList[modNum];
}
はい、書き直しました。何の意味もないStream化です。
せめて最後くらいparallel使えよ！って話ですが、これ、parallel化すると正しい結果が得られなくなることがあります。具体的にはdieMax>divNumのとき。ようするに4面ダイスを3で割った余りなとき。1,2,3,4を並行で処理しようとすると、(mod+1)%3と(mod+4)%3がバッティングしてtmp配列を破壊します。
じゃあどうすればいいのかって話なんですが、parallelできない理由はバッティングのせいなので、バッティングしないコードに変えてしまえばいいわけです。
divListをAtomicIntegerArrayにするってのは１つの手段ですが、なんでparallelで得た速度をsynchronizedで落とさなあかんねんて話なのでパス。
バッティングが発生するのは(mod+x)%divNumと(mod+x+divNum*y)%divNumが同じ配列を操作するからですので、これを無くすには、ループそのものをdivNumまでにして、(1%3と4%3のように）同じmod値のものはまとめて加算してあげればいいわけです。
たとえば
IntStream.range(1,divNum).parallel().forEach(div->{
tmp[(mod+div)%divNum]+=divList[mod%divNum]*((dieMax-div+divNum)/divNum);
});
という式にすればparallel化できます。
問題点とか。
さて、このコード、ループをdivNum and dieMaxからdivNum and divNumにしたため、たとえば6面ダイスを20回振って100で割った余り、という処理の場合、ループが100×100となってしまいます。
dieMax>divNumのときを考慮した結果、遅くなるという悲劇が起こっているのです。
dieMax<divNumのときは、dieMaxを使ってシンプルに
private static int getDieDivideCountWithStream(
final int dieMax,final int dieCount,final int divNum,final int modNum){
final int[]divList=new int[divNum];
//初期設定。
Arrays.fill(divList,1,dieMax+1,1);
//ダイスを1回ずつ振ったときのデータに更新し続ける。
IntStream.rangeClosed(2,dieCount)
.forEach(n->{
int[]tmp=new int[divNum];
IntStream.range(0,divNum).forEach(mod->{
IntStream.rangeClosed(1,dieMax).forEach(die->{
tmp[(mod+die)%divNum]+=divList[mod];
});
});
System.arraycopy(tmp,0,divList,0,divNum);
});
return divList[modNum];
}
としたほうが速そうです。
完全Stream化とか。
せっかくですので問題点を解消しつつStream apiで全面書き直してみました。
private static int getDieDivideCountWithStream(
final int dieMax,final int dieCount,final int divNum,final int modNum){
return Stream.iterate(
//初期値
IntStream.concat(
IntStream.of(dieMax/divNum)
,IntStream.range(1,divNum).parallel().map(n->(dieMax+divNum-n)/divNum)).toArray()
//初期値を１回ずつ変えていく。
,beforeDivList->{
int[]tmp=new int[divNum];
IntStream.range(0,divNum).forEach(mod->{
IntStream.rangeClosed(1,Math.min(dieMax,divNum)).parallel().forEach(di->{
tmp[(mod+di)%divNum]+=dieMax>=divNum?
(beforeDivList[mod%divNum]*((dieMax-di+divNum)/divNum))
:beforeDivList[mod];
});
});
return tmp;
}).skip(dieCount-1)//一番最後の結果までスキップ
.mapToInt(div->div[modNum])//配列から余りがmodNumのものを取り出す。
.findFirst()//おまじない
.getAsInt();//おまじない
}
わー短くて読みやすくて速い（棒
結論とか
なんでもかんでもStream apiにすればいいってもんじゃないよね。