「2番ペゲーロをみんなでやってみる」ために計算量と戦った話 #bpstudy

ありがたいことに、前回に引き続き今回も、Baseball Play Studyで発表させて頂く機会をいただきました。

私の発表

Twitter, 私の発表近辺
twitter.com

Twitter, 全体のまとめ
togetter.com

計算量との戦い

今回、「シミュレータ」をグルグルまわして最適な打順を探す　ということを行ったのですが、計算量がネックになりました。

今回のシミュレータでは、何種類かのループを回す必要がありました。

1 1シーズン、143試合分の試合を実行
2 1を、確率を収束させて精度を上げるために一定回数以上実行
3 2を、想定される打順の組み合わせ分だけ実行

さらに、同様のシミュレーションを、各球団の選手、かつ各球団ごとの打順分布に当ててみる となると、

4 3を、12球団分の選手に対して実行
5 4を、12球団それぞれの打点分布にたいして実行

が、必要となります。

ちょうど「本業」でも似たような課題を抱えており、勉強も兼ねて挑戦してみることにしました。

ループ回数を減らす

結果の精度を落とすことと引き換えに、繰り返し回数を減らすアプローチです。発表中に「ズル」と言っていたものです。

確率の収束を諦める

今回のシミュレータは確率を使っているため、施行のたびに結果が変わる、ブレが大きいものでした。
そのため、ある程度の回数実行して、結果を収束させる必要がありました。
何度か試行錯誤した結果、1000シーズン（= 143 ✕ 1000 試合）だと、年間総得点の誤差が1ー2点に収まるということがわかりました。

しかしながら、これでは数時間かかってしまう状況だったため、今回は速度優先で、100シーズンのループとしました。

施行のパターンを諦める

元々やりたかったことは、9人を並び替えた9!通りの打順をすべて試すこと。（もっというと、支配下選手70人から作られる打順をすべて試すこと）
しかし、1打順1秒としても、9!=362,880秒=丸4日間係る事になってしまってとても終わらない。
そこで、「ありえなそう」なパターンを（強めに）削ることで、55通りの組み合わせまで落としました。

並列化する

今回はJavaで実装していたので、Parallel Streamがある！ということで試してみました。
とても簡単に、かつ確実に速くなりました。
ただ、悩んだのが

このように、外のループと中のループとある場合にどこを並列化するのが良いのか。

例えば4コアCPUの場合、
中のループにParallel Streamを使うとそこだけマルチコアで処理されるため、このように断続的にCPUが100％使われるようになり

外のループに使うと、ほぼ常時CPUが使われるようになる（そのかわり、1巡の処理は先の場合より遅くなる）

そして、外と中と両方に使ってしまうと、既に外のParallel StreamでCPUが使われているため、結局外に使った場合とほぼ同じ

となると思います。（たぶん）

今回のようなバッチ処理の場合は、なるべく外側から並列化したほうがCPUを効率的に使え、処理時間を少しでも短くできそうだなぁ…
と思ったのですが、実際のトコロどうなんだろう。

外に投げる

最後の手段として、世の中にあるもっと高性能なコンピュータを使ってやろうじゃないかということで。
AWS LambdaがJavaも使えるということで試してみました。
qiita.com
こちらを参考にさせてもらいました。

はじめは、全処理をまとめてぽーんと投げてみたのですが

…遅い。とても遅い。

メモリ割り当てをMAXにしても、手元のPCで動かしている方がよっぽど速い。
Parallel Streamもまともに動いていないように見えました。（おそらく1プロセスに割り当てられている、仮想的なコアが1コアなんだと思います）

そこで、方針を転換。
AWS Lambdaは1000並列まで可能とのことで、それならば、多少処理が遅くても、4並列が限界な手元のPCよりはずっとマシだろう！と判断。
とにかく細かい単位で並列に投げまくることにしました。

普通のParallel Streamは可動しているマシンのコア数分しかスレッドが作られないため、この辺を参照。
qiita.com

※ただし、本当に1000並列でタスクを呼び出すためには1000スレッド作るか、Non Brockingな実装にする必要があります。今回はそこまで手を出せなかったので、12並列で終了。

プログラムをImmutableに書いておくの、めっちゃ大事

今回のように「プログラムの途中を外に投げる」ようなことをするにあたって、その箇所のコードが独立していないとなかなか厄介なことになります。
引数をメソッド内でガチャガチャ書き換えるような書き方、ダメ、絶対。

AWSを始めるなら…

この辺読んでから始めたほうがいいです。いろいろ面倒ですが…。
AWS 乗っ取り - Google 検索
従量課金コワイ。

続き書きました。
taichiw.hatenablog.com