シャンテン数アルゴリズムの高速化について
「シャンテン数や点数計算をする時間」
ここはどうしても高速化することになるし、重要なところ（個人的には、まだ時期尚早というか、他にやるべきことがあると考えているが）。
最強のシャンテン数計算アルゴリズムなんてよくわからないので、今回考えるのはhttp://mahjong.ara3.net/etc/shanten/index.htm
の高速化。
インデックスを持っておいて、その組み合わせで求めるアルゴリズム、すごく高速っぽいし自分も使わせてもらってるんだけど、一人麻雀練習機に付属してるハッシュ表は、ハッシュ関数がゴミ。
擬似コードを示すと、このようなものを使っている。
int hash(int t[9]) { // t[i]がkなら、i萬がk枚という意味 int ans = 0; for(int i = 0; i < 9; i++) ans = ans * 10 + t[i]; return ans; }
これは10^9くらいの大きさになるので、配列にとっておけなくて（連想配列を配列で実装できない）、平衡二分木を使う必要がある。平衡二分木の検索にはO(logN)かかる。普通はlogなんてそんなに気にすることでもないけど、消せるもんは消そう。*1
また、連想配列のサイズを減らすため、孤立牌を除くのも必要になっていて、コードも長くなるし、遅い。
ハッシュ関数を次のようなものに変更してみる。
int hash(int t[9]) { int ans = 0; for(int i = 0; i < 9; i++) ans = ans * 5 + t[i]; return ans; } }
これなら、ハッシュ値は最大でも5^9=1953125くらいで、余裕で配列に取れる。つまり、O(logN)だった検索部分がO(1)になる。また、孤立牌を消す必要もない。
これは確実にかなり効くと思う。
さらに高速化したいなら、そもそも手牌を(int, int, int)という、そもそもハッシュ化された状態で持つのがいいと思う。
ところでちょっと気に入らないのが、ans*"5"っていうところ。5だと、ビットマスクで取り出せないのでパフォーマンス的に悪そう。(modの遅さは異常)
同じ牌を４枚持ってるってあんまりないので、そこは別の形で持って、ans*"4"にするっていうのも思いついたけど、上手く速くなるか微妙。ってかあんまり速くなる気がしない。
ここから余談
interface Tehai { void add(Pai pai); void remove(Pai pai); int getShanten(); bool isTenpai(); List<Naki> listNaki(Pai pai); }
こんな感じのinterfaceを用意して、それを使ってコーディングしてれば、内部実装をあとで変えるのは簡単にできる。
まずは、
class ArrayTehai implements Tehai { private List<Pai> tehai; public ArrayTehai() { this.tehai = new ArrayList<Pai>(); } public void add(Pai pai) { tehai.add(pai); } (以下略) }
みたいなナイーブな実装でごまかしておく。
*1:ハッシュマップでもいいけど、汎用的なものを使うとどうしてもオーバーヘッドがかかる
