CoDB Light改
sub_827.icon Fable5が使える間になにかやっておけないかなと思ってさせてみた。Fableじゃなくてもできたかもしれないけど…。
生成を1回捨てたあとの7回分を使う
(player * 8) + teamで0 ~ 23の数値にエンコード
7回分のキーとseedをペアにして、キーでソートする
1～5回目の結果をエンコードした値を1回目 << 20, 2回目 << 15, 3回目 << 10, 4回目 << 5 , 5回目 << 0で詰める
以下が変更点
6回目と7回目はソートのみに使い、ファイルに保存しない
ファイルには、コードと開始時のseed上位16bitをペアにして保存する
旧形式では生成後のseedを保存して、現在seedが直接引けるようになっていた
検索時は、格納されているseed上位16bitから下位16bitを全探索して7回分の生成を回し、生成結果が入力と一致するものを返す
ほとんどは早期に枝刈りされるので実行コストもいうほどはかからない
5回目入力時点で裏で検索を走らせて、残りは候補にフィルタをかけていくようにするのがUX的にベストだと思われる
DBファイルには、16bit * （1回目の生成を捨てた直後のseedの総数）と、短縮されたキーが格納される
1回目の生成を捨てた直後のseedの総数は128095165個でした。
128095165 / 4294967296 = 0.02982...で、これだけでseed総数の約3%まで減っている
さらにキーの格納方法も工夫した
エントリはキー昇順でソートされているため、そのまま持つ必要ないよね
「キーPの値を持つエントリの個数」を累積和で持っておくことにより、キーPの値を持つエントリのインデックスの範囲を2回のアクセスで特定できる
この累積和データの持ち方が2パターン考えられる
A：累積和のデータをそのまま格納する
インデックステーブルのサイズは大きくなる（31.85MB）が、検索時にファイルへのアクセス2回だけで済むため、実行時メモリは追加で使わない
B：個数データをそのまま格納する
個数は最小1最大43であることがわかっているため、高々6bit。単純に詰めても5.97MB。
ファイルに詰めるときに符号化して圧縮すればもっと減らせる
個数の分布は、16近傍の釣鐘型で、隣接相関は0.011（ほぼ独立)
なので、ライス符号でもハフマン符号でもそんなに変わらない
実装的にはライス符号のほうが単純で軽い
ロード時に検索用のデータ構造をメモリ上に持つ必要がある
そのまま累積和にしてしまうとメモリを結構食うことになる
6bitをそのまま並べたバイト列にしてしまい、一定区間ごとにチェックポイントを置いて、なんかいい感じにする
Fableくんによる見積もり
6bitそのまま
5.97MB
理論的な下限値
平均4.0498bit、合計4.03MB
ハフマン符号
平均4.0937bit、合計4.07MB
zigzag-encoding + ライス符号
平均4.1439bit、合計4.12MB
パラメータ見積もり
総エントリ数N = 128095165
Prefixとして保存するコード数 p
部分seedとして保存するbit数 b
とするとき、クエリコストは$ 2^{32−b} \times \frac{n}{24^p}に比例する。
$ \frac{n}{24^p}が候補となるエントリ数で、$ 2^{32−b}がseedの探索数
クエリ時間を一定に保つ条件下でpを減らすとbを増やす必要があり、なんやかんやでp=5のときサイズが最小になる
また、b=16条件下でのクエリが約0.8secで、割とギリギリ
結果として、260MBくらいまで小さくなった
これ以上は無理。生成を2回捨てるとかしない限り。