気がついたら
しばらく最中限をいじれないでいるうちにすごく高速化されていた。
http://shinh.skr.jp/m/?date=20081028
http://homepage1.nifty.com/herumi/diary/0810.html#30
「vectorを使ってeraseとかしてるのが遅い」って突っ込まれるのはわかっていたので、それを直してから実行時間を比較しようと思っていたのだけどソースコードがCodeReposに上がっているので直す前に添削されちゃった。まぁ公開していなかったらこの面白い高速化話は読めなかったかもしれないので「これを今の状態で出したらつっこまれるんじゃないか」って恐怖心で公開しないことは機会損失なんだなぁ、と思った。
コードを読む。うーん中二病チックなのは素晴らしいから良いとして、 think_[a23]_turns? って関数はメンテしずらいと思うがー
うーん、think_a_turnは最終ターンだから「次のターンに使える手札のリスト」を作成する必要がなく、think_3_turnsはラウンド冒頭だからラウンドスコアが[0, 0, 0]なのでそれにターンで得た得点を足し算をする必要がない。この3つの関数をまとめることはできるけど、無駄なコストを支払わずにまとめる方法はわからなかったのでわけてある。
たぶん、このコードは全探索できてない。
for(size_t i=0; i < N; i++){
cards rest1 = except_one(unknowns, i);
for(size_t j=i+1; j < N; j++){とかでぶんまわしてるけど、これは敵2人が違う点数の場合はそれじゃあかんやろ、と思う。
一番よけいな処理の少ないthink_a_turnで説明しよう。
for(size_t i=0; i < N; i++){ for(size_t j=i+1; j < N; j++){ eval_value s = measure(my, unknowns[i], unknowns[j], round_score); if(my == get_center(my, unknowns[i], unknowns[j])){ // winner is me. score += s * 2; }else{ score += s; score += measure(my, unknowns[j], unknowns[i], round_score); } } }
ターンで自分が真ん中のときには、残りの二人の出した手を入れ替えても結果が変わらない。だから片方の処理だけやって2倍してもかまわない。いっぽう、自分が真ん中でない場合にはペアをひっくり返したバージョンを改めて計算している。約1/3のケースで2回の処理を1回で済ませられる。
ちなみに、速くする方法としては、どうせカードは 52 枚しか無いんだから、読みを開始する前に bool seen[52] とか作っておいて、カード使うたびにこれを false とか true とか切り替えてやるのがまぁあからさまに高速化できると思う。
それってこういうこと?
for(size_t i=0; i < 52; i++){ if (seen[i]) continue; for(size_t j=0; j < 52; j++){ if (seen[j]) continue;
これが速いってそんなにあからさまにわかるものかなぁ。
最終ターンの読み切りにおいて、本当だったら5 * 11 * 10回のループで済むところが52 * 52 * 52回にふくれあがるわけだよね。大半の回では単に配列から値を取り出してjumpするだけの簡単なお仕事とはいえ、この関数は上流から6 * 13 * 12 * 7 * 15 * 14回呼び出されるわけなので、そのコスト増が許容できるかどうか自明じゃない気がする。まぁもちろんvectorを確保し直したりするのは遅いと思う。
順序関係ないから手札[1, 2, 3, 4, 5]で3を使ったときには3と5をswapして[1, 2, 5, 4, 3]にして「手持ちの札は4枚」って情報を持っておくのが速いのかなぁ。