前回はNumer0nのルールと，アルゴリズムのお話をしました．
今回は，ざっくりいうと，いかにして高速にEAT/BITEの数を求めるかということについての話．
（下のgifは秘密の数が8725の時の挙動．5回で当てられている．）
成果物はこちら．stdin.rsは見ない方がいいです．
秘密の数(以降SN_3)とコールからEAT/BITEを求めるわけだが，どんな工夫ができるだろうか．
以降，桁数を$n$とする．
1. EATの求め方
EATを求めるには，各桁どうしを比較するだけ．
計算量は
$$\rm{O}(n)$$
各数字がどこにあるかという情報を削ることはできないため，これ以上高速にすることはできなさそう．
（実装では，PACKED DECIMALというデータ表現を用いて少しだけ工夫しているが，やっていることはあまり変わらない．）
2. BITEの求め方
2-1. 単純な求め方
コールされた数の各桁を，SN_3の各桁と比較し，一致した回数をカウントしていく．（各桁について，1回一致したらbreak）
そして最後にEAT数を引く．
単純な2重ループだから，計算量は
$$\rm{O}(n^2)$$
これはもう少し高速にできそう．
かといって，SN_3およびコールを，サイズ$n$の1次元配列と捉えて考える場合は，これより高速な求め方はなさそう．
2-2. 高速な求め方
じゃあどうすればいいかっていうと，データの表現方法を工夫する．
実はBITE数は，データの表現方法を工夫することにより，
$$\rm{O}(1)$$
で求めることができる．
注目したいのは，求めたいのは，あるSN_3の中に，コールされた数に含まれる数字が含まれるかどうかだけであって，どの数字がどの場所にあるかなんてどうでもいいということだ．
そこで，SN_3およびコール数の$n$桁の中に，$0$~$9$の数字に含まれるか含まれないかを，ビット列により表現する．
// 各ビットは，それぞれの数字が含まれているかを表す
// 9 8 7 6 5 4 3 2 1 0
0 0 1 0 1 0 1 0 1 0 // 3517
以降これをビットテーブルと呼ぶ
2-2-1. 通常ルールのNumer0nの場合
ビットテーブルどうしの論理積を求め，それをsとする．
通常ルールの場合は，sにおける，立っているビットの個数から，EAT数を引くだけ．
2-2-2. カスタマイズされたルールのNumer0nの場合
同じように，ビットテーブルどうしの論理積を求め，それをsとする．
カスタマイズされたルールの場合は，同じ数を何度使っても良いため，コール数において，各数字が何個存在するのかというデータが必要になる．
コール数に含まれる数字$i$の個数を$d_i~~(0\leq i\leq 9)$，
sの$i$ビット目を$s_i~~(1\leq i\leq 10)$とすると，BITE数は，
$$\sum_{i=0}^9~(~{ d_i\times s_{i+1}}~)$$
からEAT数を引いた値である．
2-3. まとめ
ちょっとデータ表現を変えるだけで
$$\rm{O}(n^2)~=>~\rm{O}(1)$$
になった．
一応速度を測ったら，4桁の場合は約4倍速くなっていた．
試しに20桁にしてみたら，約10~14倍の差が出た．
桁数が増えれば増えるほど，この差はもっと大きくなる．
データ表現の中に，不要な情報が含まれている場合は，このような手法が有効であることがあるので，頭の片隅に置いておこう．
3. 実装
言語はRust．
数字と，その桁数を引数にとり，そこからビットテーブルを生成する関数．
pub type BitTable = u16;
pub fn from(num: i32, number_of_digits: u32) -> BitTable {
(0..number_of_digits).fold(0u16, |acc, x| acc | (1 << (num / 10i32.pow(x) % 10)))
}
Numer0nの数を扱うための構造体と，実装したメソッドたち．
use super::bit_table;
use crate::bit_table::BitTable;
use super::packed_decimal;
use crate::packed_decimal::PackedDecimal;
#[derive(Copy, Clone)]
pub struct Numer0nItem {
pub packed_decimal: PackedDecimal,
pub overlap_array: [usize; 10],
pub bit_table: BitTable,
}
impl Numer0nItem {
pub fn from(num: i32) -> Self {
Numer0nItem {
packed_decimal: packed_decimal::from(num, 4),
overlap_array: (0..4).fold([0; 10], |mut acc, x| {
acc[num as usize / 10usize.pow(x as u32) % 10] += 1;
acc
}),
bit_table: bit_table::from(num, 4),
}
}
pub fn eat(self, call: &Self) -> usize { // EAT数を求める
let xor = self.packed_decimal ^ call.packed_decimal;
(0..4).fold(0, |et, i| if (xor << (4*i)) >> 12 == 0 { et + 1 } else { et })
}
pub fn eat_bite(self, call: &Self) -> usize { // EAT数 + BITE数を求める
let and = self.bit_table & call.bit_table;
(0..and.count_ones()).fold((0usize, 0usize, and), |(num, eb, and), _| {
let shift = and.trailing_zeros() as usize + 1;
(num+shift, eb + call.overlap_array[num+shift-1], and >> shift)
}).1
}
}
4. おわりに
Numer0nのAIを作るうえで役立ちそうな話を，アルゴリズム編と，データ表現編の2回に分けて説明しました．
ここまで読んでいただきありがとうございました．