はじめに
そもそものきっかけは、ベイズ推定とは何？という程度の知識レベルで、AtcoderのAH030を解こうとすると、適当なロジックで試行錯誤して、時間を浪費したところで大してスコアも伸びずギブアップするだけなので、ゼロから手を動かして知識を得たい。
一方で、従来型の独学での自習は限度があるので、NotebookLMを使うとどのようなメリットがあるのか試してみようかと思いました。
- NotebookLMを初めて使っての気づき 【NotebookLM編】
- AHC030に関する気づき
とっても参考になる題材はこちら→AHC典型解法シリーズ第3弾「ベイズ推定」
javaぽく修正
6.なんちゃってテキスト変換ツールでcppソースをjavaソースに変換では、vector<vector<bool>>を機械的にArrayList<ArrayList<Boolean>>をラップしたBoolListListクラスにしたが、ざっと見渡すと、最初からサイズの分かっている固定長配列と、サイズが不明な可変長配列の両方がvectorとなっているので、まずコンストラクタで分別する。
ただし、コンストラクタでサイズは指定しているが、デフォルト値がなく、後からaddで追加するタイプ（最初にメモリ確保のみする＝javaと同じ）のものは可変長配列として扱う。
- BoolAry : boolean[] aryをラップ。
- BoolAryAry : boolean[][] aryをラップ。
- DoubleAry : double[] aryをラップ。
- DoubleAryList : ArrayList listをラップ。
- IntAry : int[] aryをラップ。
- IntAryAry : int[][] aryをラップ。
- IntListAry : ArrayList[] aryをラップ。
- LongAry : long[] aryをラップ。
- PairDoubleListAryAry : PairDoubleList[][] aryをラップ。
- PairIntListAryAry : PairIntList[][] aryをラップ。
byteをintに変更
uint8_tをbyteにしたが、何気に128から255の値を攻めてくるテストデータがあり、int v=(b & 0xFF)+aのように符号なし8ビットにしてからintで足すとかわざわざ修正したが、全部intに統一する。ByteListやByteListListは不要になった。
ハッシュ計算の修正
ハッシュをXORで計算すると、同じ形のシェイプの同じ左上座標の場合、どの座標でも2つのXORが0となる。このため、XORでなく、加算減算に修正する。
evalのDoubleListをdouble[]に変更
evalが最も呼ばれ、そのたびにListで一時的に計算すると、大量のDoubleインスタンスが生成されるため、ここだけ余裕を持ったバッファサイズ(total+60)の固定長配列にする。
修正前後でseed0から99を計測したら、この変更の効果が大きかった。
スコア比較
1st ランダムな占いを元にベイズ推定で配置を推定
2nd 相互情報量を最大化する占い
3rd 数を絞ったランダムなプールを用いることでM=3以上に対応
4th 焼きなましで尤度の高いプールを生成
5th 近傍を工夫した焼きなまし
6th 記事公開後に作った延長戦2位コード
java98 このソース
java99 機械的に変換したソース
cpp オリジナル
| # | java98 | java99 | cpp | 特記 |
|---|---|---|---|---|
| 1st | 129,881,331 | 212,750,845 | 221,821,513 | 20件のみ |
| 2nd | 522,875,404 | 1,376,675,024 | 1,580,626,704 | 20件のみ |
| 3rd | 10,911,281,012 | 10,319,181,275 | 9,983,567,060 | 100件 |
| 4th | 5,828,286,456 | 6,957,714,565 | 7,125,422,476 | 100件 |
| 5th | 3,142,705,682 | 5,343,967,217 | 5,769,632,783 | 100件 |
| 6th | 3,857,612,262 | 8,077,839,780 | 1 | 100件 |
意外にもjava99とcppが同程度で、java98は速度アップを目的に修正したので効果が出ている。
5thより6thが悪化しているのは、チューニングがcppで行われているため。
比較しようと思ったが、これだけビルドできなかった。
gcの状況
AIがやたらとYoungGCと言うものだから、GCログを出してみた。
giveupして、一番メモリを使っていそうなのが、seed63(N=18,M=10,eps=0.20)。
[0.009s] Using G1
[0.010s] ConcGCThreads: 3 offset 22
[0.010s] ParallelGCThreads: 10
[0.010s] Initialize mark stack with 4096 chunks, maximum 524288
[0.141s] GC(0) Pause Young (Normal) (G1 Evacuation Pause) 23M->17M(254M) 9.574ms
[0.173s] GC(1) Pause Young (Normal) (G1 Evacuation Pause) 31M->30M(254M) 8.644ms
[0.192s] GC(2) Pause Young (Normal) (G1 Evacuation Pause) 39M->38M(254M) 4.146ms
[0.222s] GC(3) Pause Young (Normal) (G1 Evacuation Pause) 57M->53M(254M) 5.852ms
[0.511s] GC(4) Pause Young (Normal) (G1 Evacuation Pause) 88M->61M(444M) 4.860ms
[0.862s] GC(5) Pause Young (Normal) (G1 Evacuation Pause) 117M->63M(444M) 2.449ms
[2.871s] GC(6) Pause Young (Normal) (G1 Evacuation Pause) 328M->65M(444M) 1.767ms
!log giveup because timeup
!Time = 2.917
!log miss 0
!cost = 207.40018898737785
ソース置き場
- 98 java完成版
-
g++でビルドできなかった。 ↩