実際に競プロで効果のあったPython高速化Tips ～ACとTLEの分かれ道～

# はじめに
Pythonの高速化記事/手法は数多く存在するが、すべて対応しなければならいのか？どれが実際に有効な手法なの？
ということで、私が試してみて実際に効果のあった(ACとTLEの分かれ道になった）手法を纏めていく。
※随時追加していきます。

# Tips一覧
* 要素に重複が無く要素の順番が関係無い集合を扱う際はsetを使うこと
* 集合内の要素の全組み合わせを取得する場合は、itertools.combinationsは使わずにfor文を回して取得すること
* Listのスライスは極力使わないこと
* 再帰関数を使うならPyPyではなくPythonで提出すること


# 要素に重複が無く要素の順番が関係無い集合を扱う際はsetを使うこと
特にin句（含まれているかどうかの確認）をする場合はlistではなくsetを利用すべき。
listに対するinはO(n)だが、setに対するinはO(1)となるため（<a href="https://qiita.com/Hironsan/items/68161ee16b1c9d7b25fb">参考</a>）。
この違いがモロに影響出た問題がこちら（<a href="https://atcoder.jp/contests/abc073/tasks/abc073_c">ABC073-C</a>）。
TLE解：https://atcoder.jp/contests/abc073/submissions/18492887
AC解：https://atcoder.jp/contests/abc073/submissions/18492873

# 集合内の要素の全組み合わせを取得する場合は、itertools.combinationsは使わずにfor文を回して取得すること

この違いがモロに影響出た問題がこちら（<a href="https://atcoder.jp/contests/typical90/tasks/typical90_bc">競プロ典型90問 055 - Select 5（★2）</a>）。

<b>ACプログラム(組み合わせ取得部)</b>

```python
    for i in range(n-4):
        for j in range(i+1, n-3):
            for k in range(j+1, n-2):
                for ll in range(k+1, n-1):
                    for m in range(ll + 1, n):
                        t = l[i] * l[j] % p * l[k] % p * l[ll] % p * l[m] % p
                        if t == q:
                            ans += 1
```

<b>TLEプログラム(組み合わせ取得部)</b>

```python
    for pair in itertools.combinations(l, 5):
        t = pair[0] * pair[1] % p * pair[2] % p * pair[3] % p * pair[4] % p
        if t  == q:
           ans +=1
```

combination関数を使う場合、恐らく内部処理の兼ね合いで何かしらのオーバヘッドがかかって遅くなっていると思われる。
集合内の要素の全組み合わせを取得する場合は、面倒でもcombination関数は使わずにfor文を使った方がよさそう。
手元の環境で、上記のプログラムを要素数100(len(l)=100)で実行したところ、2秒程の差があった。

# Listのスライスは極力使わないこと
Pythonでは、Listのスライス記法（例: hoge[2:5]）を使って、List内の指定の区間を別Listとして取得することが可能である。
例）二分探索時の探索区間の絞り込み
ただ、<a href="https://qiita.com/bee2/items/4ab87d05cc03d53e19f9">こちらの記事</a>によると、上記の書き方はO(k)とのこと。
そのため、大量のデータを処理する場合、スライスの処理がボトルネックになることがある。
その様な場合、切り出し区間の開始indexと終了indexを記録・更新する等、スライス記法以外の手法を検討すべきである。

この違いがモロに影響出た問題がこちら（<a href="https://atcoder.jp/contests/typical90/tasks/typical90_g">競プロ典型90問 007 - CP Classes（★3）</a>）。

<b>ACプログラム(二分探索部)</b>

```python
        st = 0
        ed = len(a) - 1
        while ed - st >= 0:
            if ed - st == 1:
                print(min(abs(a[st]-c),abs(a[ed]-c)))
                break
            elif ed - st == 0:
                print(abs(c-a[st]))
                break

            idx = (ed-st)//2 + st
            if c == a[idx]:
                print(0)
                break
            elif a[idx] < c:
                st = idx
                ed = ed
            elif c < a[idx]:
                st = st
                ed = idx
```

<b>TLEプログラム(二分探索部)</b>

```python
        tmp = list(a)
        while len(tmp) >= 1:
            if len(tmp) == 2:
                print(min(abs(tmp[0]-c),abs(tmp[1]-c)))
                break
            elif len(tmp) == 1:
                print(abs(c-tmp[0]))
                break
 
            idx = len(tmp)//2
            if c == tmp[idx]:
                print(0)
                break
            elif tmp[idx] < c:
                tmp = tmp[idx:len(tmp)]
            elif c < tmp[idx]:
                tmp = tmp[0:idx+1]
```

# 再帰関数を使うならPyPyではなくPythonで提出すること
PyPyは再帰関数の呼び出しがクソ遅いので、再帰関数を使う場合はPythonで提出すること。

<a href="https://qiita.com/OKCH3COOH/items/f0c5c4681bc30dddf7f4">参考記事 -【競プロ】PythonとPyPyの速度比較</a>


実際にハマった問題はこちら　→ <a href="https://atcoder.jp/contests/typical90/tasks/typical90_z">競プロ典型90問 026</a>

深さ優先探索の実装時に再帰関数を使ったコードを<a href="https://atcoder.jp/contests/typical90/submissions/24269315">PyPyで提出</a>した際にはTLEだが、<a href="https://atcoder.jp/contests/typical90/submissions/24269299">Pythonで提出</a>したところACとなった。
<a href="https://atcoder.jp/contests/typical90/submissions/24273199">dequeによるFIFO実装に変えたコード</a>をPyPyで提出したところACとなった。
PyPyは他にも文字列操作も遅いとのこと（まだ私自身AC/TLEの分かれ道になったことは無い）。


# 参考サイト
* https://qiita.com/sotasato/items/cc36a532ba6487dd3dba
* https://atsuoishimoto.hatenablog.com/entry/2019/01/18/180020
* https://medium.com/finatext/lets-do-competitive-programming-with-python-9c8b834769f6
* https://qiita.com/c-yan/items/dbf2838cdd89864ef5ac
* https://nonbiri-tereka.hatenablog.com/entry/2016/09/01/072402#PyPy
* https://python.ms/optimization/#%E7%B5%90%E8%AB%96
* https://qiita.com/machi-no-soko/items/54c82b4bf99422e37011
* http://nobunaga.hatenablog.jp/entry/2018/03/19/081425
* https://qiita.com/OKCH3COOH/items/f0c5c4681bc30dddf7f4