More than 3 years have passed since last update.

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

Last updated at 2021-07-17Posted at 2020-11-29

はじめに

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

Tips一覧

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

要素に重複が無く要素の順番が関係無い集合を扱う際はsetを使うこと

特にin句（含まれているかどうかの確認）をする場合はlistではなくsetを利用すべき。
listに対するinはO(n)だが、setに対するinはO(1)となるため（参考）。
この違いがモロに影響出た問題がこちら（ABC073-C）。
TLE解：https://atcoder.jp/contests/abc073/submissions/18492887
AC解：https://atcoder.jp/contests/abc073/submissions/18492873

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

この違いがモロに影響出た問題がこちら（競プロ典型90問 055 - Select 5（★2））。

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

    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

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

    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として取得することが可能である。
例）二分探索時の探索区間の絞り込み
ただ、こちらの記事によると、上記の書き方はO(k)とのこと。
そのため、大量のデータを処理する場合、スライスの処理がボトルネックになることがある。
その様な場合、切り出し区間の開始indexと終了indexを記録・更新する等、スライス記法以外の手法を検討すべきである。

この違いがモロに影響出た問題がこちら（競プロ典型90問 007 - CP Classes（★3））。

ACプログラム(二分探索部)

        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

TLEプログラム(二分探索部)

        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で提出すること。

参考記事 -【競プロ】PythonとPyPyの速度比較

実際にハマった問題はこちら　→ 競プロ典型90問 026

深さ優先探索の実装時に再帰関数を使ったコードをPyPyで提出した際にはTLEだが、Pythonで提出したところACとなった。
dequeによるFIFO実装に変えたコードをPyPyで提出したところACとなった。
PyPyは他にも文字列操作も遅いとのこと（まだ私自身AC/TLEの分かれ道になったことは無い）。

参考サイト

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up