地上最速の「大石泉すき」判定コードを書いてみた

# 概要

- よ一ど ♀([@yo_do_53](https://twitter.com/yo_do_53))さんが、[診断メーカー](https://shindanmaker.com/)で「[大石泉すき](https://shindanmaker.com/733464)」診断を作る
  - 「大石泉すき」の5種類の文字から重複順列がランダムに取り出される
  - 「大石泉すき」と並ぶ確率は`1 / (5 ** 5) = 1 / 3125`
- 桜花([@ikmesyk3](https://twitter.com/ikmesyk3))さんが、↑の並びをポーカーに見立てた「[大石泉すきポーカー](https://twitter.com/ikmesyk3/status/1043484395653328896)」を提案
- [私が、その役判定プログラムをQiitaに書く](https://qiita.com/YSRKEN/items/262040d07e7e343bc70e)
- 私が、役判定プログラムを高速化する　←New！

※今回書いたプログラムは[Wandbox](https://wandbox.org/permlink/RlbyShFpXNSrSer6)に置いてます

# 判定条件

- そのまま「大石泉すき」という文字列から判定しようとすると**文字コードの闇に叩き込まれてしまう**
- そこで、「大」から「き」までに「0」から「4」の数字を入れて、整数型の配列として入力するとする

# 判定のベースとなるコード

```cpp
#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;

const size_t LOOP_COUNT = 10000;

int judge_hand(const int digit[]) {
    // ロイヤルストレートフラッシュ
    if (digit[0] == 0 && digit[1] == 1 && digit[2] == 2 && digit[3] == 3 && digit[4] == 4)
        return 0;
    // ファイブカード
    if (digit[0] == digit[1] && digit[1] == digit[2] && digit[2] == digit[3] && digit[3] == digit[4])
        return 1;
    // フォーカード
    int count[] = {0, 0, 0, 0, 0};
    for (int i = 0; i < 5; ++i){
        ++count[digit[i]];
    }
    for (int i = 0; i < 5; ++i){
        if (count[i] == 4)
            return 2;
    }
    // ストレートフラッシュ
    bool flg = true;
    for (int i = 0; i < 5; ++i){
        if (count[i] == 0) {
            flg = false;
            break;
        }
    }
    if (flg) {
        return 3;
    }
    // フルハウス
    bool flg_2 = false;
    bool flg_3 = false;
    for (int i = 0; i < 5; ++i){
        if (count[i] == 2) {
            flg_2 = true;
            continue;
        }
        if (count[i] == 3) {
            flg_3 = true;
            continue;
        }
    }
    if (flg_2 && flg_3) {
        return 4;
    }
    // すき
    if (digit[0] == 3 && digit[1] == 4)
        return 5;
    if (digit[1] == 3 && digit[2] == 4)
        return 5;
    if (digit[2] == 3 && digit[3] == 4)
        return 5;
    if (digit[3] == 3 && digit[4] == 4)
        return 5;
    // スリーカード
    if (flg_3) {
        return 6;
    }
    // ツーペア
    if (flg_2) {
        int digit_count = 0;
        for (int i = 0; i < 5; ++i){
            if (count[i] != 0) {
                ++digit_count;
            }
        }
        if (digit_count == 3) {
            return 7;
        }
    }
    return 99;
}

int main()
{
    cout << "ループ回数：" << LOOP_COUNT << "回" << endl;

    auto start = system_clock::now();
    volatile int result = 99;
    int digit[] = {0, 0, 0, 0, 0};
    for (size_t n = 0; n < LOOP_COUNT; ++n) {
        for (size_t i1 = 0; i1 < 5; ++i1){
            digit[0] = i1;
        for (size_t i2 = 0; i2 < 5; ++i2){
            digit[1] = i2;
        for (size_t i3 = 0; i3 < 5; ++i3){
            digit[2] = i3;
        for (size_t i4 = 0; i4 < 5; ++i4){
            digit[3] = i4;
        for (size_t i5 = 0; i5 < 5; ++i5){
            digit[4] = i5;
            result = 99;
        }}}}}
    }
    auto dur = system_clock::now() - start;
    auto nanosec = std::chrono::duration_cast<std::chrono::nanoseconds>(dur).count();
    cout << "ループ自体の時間：" << nanosec << "ナノ秒(" << (1.0 * nanosec / LOOP_COUNT / 5 / 5 / 5 / 5 / 5) << "ナノ秒/回)" << endl;

    start = system_clock::now();
    for (size_t n = 0; n < LOOP_COUNT; ++n) {
        for (size_t i1 = 0; i1 < 5; ++i1){
            digit[0] = i1;
        for (size_t i2 = 0; i2 < 5; ++i2){
            digit[1] = i2;
        for (size_t i3 = 0; i3 < 5; ++i3){
            digit[2] = i3;
        for (size_t i4 = 0; i4 < 5; ++i4){
            digit[3] = i4;
        for (size_t i5 = 0; i5 < 5; ++i5){
            digit[4] = i5;
            result = judge_hand(digit);
        }}}}}
    }
    dur = system_clock::now() - start;
    auto nanosec2 = std::chrono::duration_cast<std::chrono::nanoseconds>(dur).count() - nanosec;
    cout << "計算時間：" << nanosec2 << "ナノ秒(" << (1.0 * nanosec2 / LOOP_COUNT / 5 / 5 / 5 / 5 / 5) << "ナノ秒/回)" << endl;
}
```

このコードを使い、
- Wandboxのclang HEAD 8.0.0にOptimizationを付け、C++1a基準でコンパイルする
- 5回測った平均を見る
ことを行ったところ、**1回の判定につき28.0246ナノ秒**掛かりました。言い換えると**毎秒3568万回**判定できることになります。ここからどんどん加速させていきます。

# アルゴリズムの改良

元の判定コードは長ったらしいので、より簡潔にできないかを考えてみました。
これの平均タイムは**17.6106ナノ秒/回**となります。計算速度が1.6倍になったことになりますね。

```cpp
int judge_hand_fast(volatile int digit[]) {
    // 各数字の出現回数
    int count[] = {0, 0, 0, 0, 0};
    for (int i = 0; i < 5; ++i)
        ++count[digit[i]];
    // 出現回数の出現回数
    int count2[] = {0, 0, 0, 0, 0, 0};
    for (int i = 0; i < 5; ++i)
        ++count2[count[i]];
    // 判定
    if (count2[1] == 5) {
        if (digit[0] == 0 && digit[1] == 1 && digit[2] == 2 && digit[3] == 3 && digit[4] == 4)
            // ロイヤルストレートフラッシュ
            return 0;
        else
            // ストレートフラッシュ
            return 3;
    }
    // ファイブカード
    if (count2[5] == 1)
        return 1;
    // フォーカード
    if (count2[4] == 1)
        return 2;
    // フルハウス
    if (count2[3] == 1 && count2[2] == 1)
        return 4;
    // すき
    if (digit[0] == 3 && digit[1] == 4)
        return 5;
    if (digit[1] == 3 && digit[2] == 4)
        return 5;
    if (digit[2] == 3 && digit[3] == 4)
        return 5;
    if (digit[3] == 3 && digit[4] == 4)
        return 5;
    // スリーカード
    if (count2[3] == 1)
        return 6;
    if (count2[2] == 2)
        return 7;
    return 99;
}
```

また、出現頻度が高い役の判定を先に持ってきた方が高速に処理できますので、少し工夫を施しました。
ただ、これだと平均**17.5577ナノ秒/回**と、思ったような改善ができませんでした。

```cpp
int judge_hand_fast2(volatile int digit[]) {
    // 各数字の出現回数
    int count[] = {0, 0, 0, 0, 0};
    for (int i = 0; i < 5; ++i)
        ++count[digit[i]];
    // 出現回数の出現回数
    int count2[] = {0, 0, 0, 0, 0, 0};
    for (int i = 0; i < 5; ++i)
        ++count2[count[i]];
    // 判定
    // ツーペア・すき
    if (count2[2] == 2){
        // すき
        if (digit[0] == 3 && digit[1] == 4)
            return 5;
        if (digit[1] == 3 && digit[2] == 4)
            return 5;
        if (digit[2] == 3 && digit[3] == 4)
            return 5;
        if (digit[3] == 3 && digit[4] == 4)
            return 5;
        // ツーペア
        return 7;
    }
    // スリーカード・すき・フルハウス
    if (count2[3] == 1){
        // すき
        bool sukiFlg = false;
        if (digit[0] == 3 && digit[1] == 4)
            sukiFlg = true;
        else if (digit[1] == 3 && digit[2] == 4)
            sukiFlg = true;
        else if (digit[2] == 3 && digit[3] == 4)
            sukiFlg = true;
        else if (digit[3] == 3 && digit[4] == 4)
            sukiFlg = true;
        // フルハウス
        if (count2[2] == 1)
            return 4;
        if (sukiFlg)
            return 5;
        // スリーカード
        return 6;
    }
    // すき
    bool sukiFlg = false;
    if (digit[0] == 3 && digit[1] == 4)
        sukiFlg = true;
    else if (digit[1] == 3 && digit[2] == 4)
        sukiFlg = true;
    else if (digit[2] == 3 && digit[3] == 4)
        sukiFlg = true;
    else if (digit[3] == 3 && digit[4] == 4)
        sukiFlg = true;
    // ストレートフラッシュ・ロイヤルストレートフラッシュ
    if (count2[1] == 5) {
        if (digit[0] == 0 && digit[1] == 1 && digit[2] == 2 && digit[3] == 3 && digit[4] == 4)
            // ロイヤルストレートフラッシュ
            return 0;
        else
            // ストレートフラッシュ
            return 3;
    }
    // フォーカード
    if (count2[4] == 1)
        return 2;
    // ファイブカード
    if (count2[5] == 1)
        return 1;
    if (sukiFlg)
        return 5;
    return 99;
}
```

開き直って配列に格納する方法もあります。平均**0.32019ナノ秒/回**と爆速ですが、ベンチマーク的に考えるとインチキそのものなのが難点。

```cpp
int cache[3125] = {};

// 判定用関数
int judge_hand_fast3(const int digit[]) {
    return cache[digit[0]*5*5*5*5+digit[1]*5*5*5+digit[2]*5*5+digit[3]*5+digit[4]];
}

// 使用前の初期化
for (size_t i1 = 0; i1 < 5; ++i1){
    digit[0] = i1;
for (size_t i2 = 0; i2 < 5; ++i2){
    digit[1] = i2;
for (size_t i3 = 0; i3 < 5; ++i3){
    digit[2] = i3;
for (size_t i4 = 0; i4 < 5; ++i4){
    digit[3] = i4;
for (size_t i5 = 0; i5 < 5; ++i5){
    digit[4] = i5;
    cache[i1*5*5*5*5+i2*5*5*5+i3*5*5+i4*5+i5] = judge_hand(digit);
}}}}}
```

# SIMDに手を出す

と言ってもIntrinsicを使うのではなく、ただのビット演算になりました。
だって1文字が5通り、つまり3ビット分しかないので5文字合っても15ビットしか使わないんだもの……。
ただ、試したところかえって遅くなってしまいましたorz

```cpp
inline uint32_t calc_bitboard(const int index){
    return 1 << (index * 3);
}

int judge_hand_fast4(const int digit[]) {
    // 各数字の出現回数をビットボードを利用してカウント
    uint32_t count_board = 0;
    count_board += calc_bitboard(digit[0]);
    count_board += calc_bitboard(digit[1]);
    count_board += calc_bitboard(digit[2]);
    count_board += calc_bitboard(digit[3]);
    count_board += calc_bitboard(digit[4]);
    const int count_0 = count_board & 0x7;
    const int count_1 = (count_board >>  3) & 0x7;
    const int count_2 = (count_board >>  6) & 0x7;
    const int count_3 = (count_board >>  9) & 0x7;
    const int count_4 = (count_board >> 12) & 0x7;
    
    // 各数字の出現回数の出現回数をビットボードを利用してカウント
    count_board = 0;
    count_board += calc_bitboard(count_0);
    count_board += calc_bitboard(count_1);
    count_board += calc_bitboard(count_2);
    count_board += calc_bitboard(count_3);
    count_board += calc_bitboard(count_4);
    const int count2_0 = count_board & 0x7;
    const int count2_1 = (count_board >>  3) & 0x7;
    const int count2_2 = (count_board >>  6) & 0x7;
    const int count2_3 = (count_board >>  9) & 0x7;
    const int count2_4 = (count_board >> 12) & 0x7;
    const int count2_5 = (count_board >> 15) & 0x7;
        
    // 判定
    // ツーペア・すき
    if (count2_2 == 2){
        // すき
        if (digit[0] == 3 && digit[1] == 4)
            return 5;
        if (digit[1] == 3 && digit[2] == 4)
            return 5;
        if (digit[2] == 3 && digit[3] == 4)
            return 5;
        if (digit[3] == 3 && digit[4] == 4)
            return 5;
        // ツーペア
        return 7;
    }
    // スリーカード・すき・フルハウス
    if (count2_3 == 1){
        // フルハウス
        if (count2_2 == 1)
            return 4;
        // すき
        bool sukiFlg = false;
        if (digit[0] == 3 && digit[1] == 4)
            return 5;
        else if (digit[1] == 3 && digit[2] == 4)
            return 5;
        else if (digit[2] == 3 && digit[3] == 4)
            return 5;
        else if (digit[3] == 3 && digit[4] == 4)
            return 5;
        // スリーカード
        return 6;
    }
    // ストレートフラッシュ・ロイヤルストレートフラッシュ
    if (count2_1 == 5) {
        if (digit[0] == 0 && digit[1] == 1 && digit[2] == 2 && digit[3] == 3 && digit[4] == 4)
            // ロイヤルストレートフラッシュ
            return 0;
        else
            // ストレートフラッシュ
            return 3;
    }
    // フォーカード
    if (count2_4 == 1)
        return 2;
    // ファイブカード
    if (count2_5 == 1)
        return 1;
    // すき
    if (digit[0] == 3 && digit[1] == 4)
        return 5;
    else if (digit[1] == 3 && digit[2] == 4)
        return 5;
    else if (digit[2] == 3 && digit[3] == 4)
        return 5;
    else if (digit[3] == 3 && digit[4] == 4)
        return 5;
    return 99;
}
```

# 計測結果の詳細
|コード|1回目|2回目|3回目|4回目|5回目|平均|
|----|----|----|----|----|----|----|
|デフォ|28.2191|27.0735|30.0721|26.8518|27.9063|28.0246|
|fast|16.9103|17.5591|18.2040|17.1986|18.1810|17.6106|
|fast2|17.5094|17.6602|17.6207|17.1255|17.8726|17.5577|
|fast3|0.240192|0.475264|0.345120|0.279904|0.260448|0.320186|