計算量とM-1

# はじめに（Introduction）

「M-1グランプリ2021」見ました？
優勝は錦鯉さんでしたが、決勝ネタのトップバッターに出てきたモグライダーの内容が数学（プログラム的）だと、東大王の鶴崎さんが動画で説明していました。
たしかに、$O$（オーダー）の話としてとらえると面白いと感じたので内容を見てみます。

また、実際にプログラム（Java）を書いてみて速度を見てみます。

# 問題（Qestion）

モグライダーのネタを書いてしまうと、ネタバレになってしまうので抽象化して書いてみます。
※：モグライダーのM-1でのネタは**[このリンク](https://www.youtube.com/watch?v=ov7i54_2kWo)**から参照できますので、先にそちらを見た方が分かりやすいと思います。

問題としては、ある人物はYesかNoしか言えません、その人の星座と性別を時間内に当てる（両方Yesと言わせる）というものです。
※：ここで星座は12種類、性別は2種類とします。

ネタとしては以下の順番で試していき、最後で時間内に見つける事ができます。
※：探索の名称は私が勝手に命名しております。

- あてずっぽうで聞いていく⇒時間オーバー（ランダム探索）
- 星座＋性別を順番に聞いていく⇒時間オーバー（総当たり探索）
- まず星座を聞いていく、星座が当たっていたら性別を聞いていく⇒成功（順序探索）


# 時間計算量（Time Complexity）

２つの要素の集合を$M$、$N$とした場合を考えます。

総当たり探索、$O(MN)=O(M\times N)$の計算量となります。
順序探索は、$O(M+N)$の計算量となります。

※：ランダム探索は、$O$では表せない？確率的になるのかな？

鶴崎氏が**[動画内](https://www.youtube.com/watch?v=kY10D5ygbL8)**で、二分探索を使えば$O(\log{M}+\log{N})$の計算量にるが、星座や性別に順番がつけられていて、それ（プロトコル）をお互いが共有している前提が必要であると述べています。

https://e-words.jp/w/%E6%99%82%E9%96%93%E8%A8%88%E7%AE%97%E9%87%8F.html

https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2

# ランダム探索（Random Search）

ランダムで$m$と$n$を選択して、両方一致しているか判定します。
配列に存在しないと永久ループになります。（悪い実装）

```java
    public String[] random() {
        String m = null;
        String n = null;
        while (true) {
            m = mStrings[random.nextInt(mStrings.length)];
            n = nStrings[random.nextInt(nStrings.length)];
            if (this.m.equals(m) && this.n.equals(n)) {
                return new String[] { m, n };
            }
        }
    }
```

# 総当たり探索（Force Search）

$m$と$n$の総当たりの組み合わせに対して、両方一致しているか判定します。

```java
    public String[] force() {
        for (String m : mStrings) {
            for (String n : nStrings) {
                if (this.m.equals(m) && this.n.equals(n)) {
                    return new String[] { m, n };
                }
            }
        }
        return null;
    }
```

# 順序探索（Order Search）

$m$が一致するか判定します。
$m$が一致したら、$n$が一致するか判定します。

```java
    public String[] order() {
        for (String m : mStrings) {
            if (this.m.equals(m)) {
                for (String n : nStrings) {
                    if (this.n.equals(n)) {
                        return new String[] { m, n };
                    }
                }
            }
        }
        return null;
    }
```


# 二分探索

先に、探索用の配列をソートしておく必要があります。
そして大小を判定して探索範囲を狭めていきます。

```java
    private String[] mSort = null;
    private String[] nSort = null;

    public void sort() {
        mSort = Arrays.copyOf(mStrings, mStrings.length);
        Arrays.sort(mSort);
        nSort = Arrays.copyOf(nStrings, nStrings.length);
        Arrays.sort(nSort);
    }

    public String[] binarys() {
        String m = binary(mSort, this.m, 0, mSort.length - 1);
        if (m != null) {
            String n = binary(nSort, this.n, 0, nSort.length - 1);
            if (n != null) {
                return new String[] { m, n };
            }
        }
        return null;
    }

    public String binary(String[] ary, String key, int min, int max) {
        if (max < min) {
            return null;
        } else {
            int mid = min + (max - min) / 2;
            int c = ary[mid].compareTo(key);
            if (c > 0) {
                return binary(ary, key, min, mid - 1);
            } else if (c < 0) {
                return binary(ary, key, mid + 1, max);
            } else {
                return key;
            }
        }
    }
```

# 計測（Measurement）

試行回数毎に毎回一致する$m$と$n$を変更します。
試行回数100万回、$m$が12個、$n$が2個で計測します。

```text
loop : 1,000,000
m    :  12 items
n    :   2 items
random   :    13459 ms
force    :       98 ms
order    :       85 ms
binary   :       85 ms
```

ランダム探索がボロボロです。
ちょっと、ランダム探索に影響されて後半の計測も毎回計測値が変わってまったので、ここからはランダム探索はやらない事にします。

もう一度計測します。
※：試行回数100万回、$m$が12個、$n$が2個

```text
loop : 1,000,000
m    :  12 items
n    :   2 items
force    :       98 ms
order    :       72 ms
binary   :       59 ms
```

想定どおり、総当たり探索＞順序探索二分探索、となります。

アイテム数を2倍にしてみます。

以下が予想されます。

総当たり探索：$O(MN)$ → $O(2M2N)=O(4MN)$
順序探索：$O(M+N)$ → $O(2M+2N)=O(2(M+N))$
二分探索：$O(\log{M}+\log{N})$ → $O(\log{2M}+\log{2N})=O(2+\log{M}+\log{N}))$

こんな計算してはいけないと思いますが、計算量の増加も、総当たり探索＞順序探索二分探索、となるはずです。

※：試行回数100万回、$m$が24個、$n$が4個

```text
loop : 1,000,000
m    :  24 items
n    :   4 items
force    :      209 ms
order    :       95 ms
binary   :       74 ms
```

※：試行回数100万回、$m$が120個、$n$が20個

```text
loop : 1,000,000
m    : 120 items
n    :  20 items
force    :     2858 ms
order    :      237 ms
binary   :      130 ms
```

|探索|データ量<br>1倍|データ量<br>2倍|倍率<br>1→2倍|データ量<br>10倍|倍率<br>1→10倍|
|:--|--:|--:|--:|--:|--:|
|総当たり探索|98 ms|209 ms|2.1|2858 ms|29.2|
|順序探索|72 ms|95 ms|1.3|237 ms|3.3|
|二分探索|59 ms|74 ms|1.25|130 ms|2.2|

想定どおり、総当たり探索＞順序探索＞二分探索、となります。
ですが、順序探索と二分探索差があまり無いように見えます。
これは、探索の対象が数十～数百しかないので大した差にならないと考えます。

また、判定などソース上のオーバーヘッドが加わるので、純粋な探索ロジックの時間とはならないですが、傾向は見えたと思います。

# まとめ（Conclusion）

予想どおりの結果となりました。
もっと探索する対象が多いと二分探索の計算量が優秀だとわかりそうですがやれませんでした。
ただ、計測を何回か試してみましたが、総当たり探索と順序探索は計測値がブレブレでした。
一方、二分探索は安定して同じような値が計測できました。
また、100万以上の配列を使うとJava側の処理上の問題で計測値が安定しませんでした。

二分探索の方が速いですが、やはり人間どうしでやるなら順序探索が効率的かもしれません。

予想どおりの結果となりましたが、M-1からプログラムを学べるもんですね。

他に良いやり方などありましたら、コメントなどで教えていただけるとありがたいです。

# 参照（References）

https://www.youtube.com/watch?v=ov7i54_2kWo

https://www.youtube.com/watch?v=kY10D5ygbL8