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

概要

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

※今回書いたプログラムはWandboxに置いてます

判定条件

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

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

#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倍になったことになりますね。

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ナノ秒/回と、思ったような改善ができませんでした。

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ナノ秒/回と爆速ですが、ベンチマーク的に考えるとインチキそのものなのが難点。

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

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