競技プログラミングで差がつくPython高速化テクニック徹底解説

Pythonは、競技プログラミングの世界で最も人気のある言語の一つです。多くの問題は、Pythonを使えば現実的な時間内に簡単に解くことができます。

しかし、複雑な問題になると、十分に高速なPythonコードを書くこと自体が課題になることも少なくありません。ここでは、競技プログラミングでコードのパフォーマンスを向上させるための、Pythonらしい（Pythonicな）コーディング技法を紹介します。

1. 文字列の連結にはjoinを使う

以下のような書き方は避けましょう。

str1 = ""
some_list = ["Welcome ", "To ", "Tutorialspoint "]
for x in some_list:
    str1 += x
print(str1)

この方法では、文字列がイミュータブル（変更不可）であるため、連結のたびに新しい文字列オブジェクトが生成され、大きな時間的オーバーヘッドが発生します。代わりに、joinメソッドを使いましょう。

str1 = ""
some_list = ["Welcome ", "To ", "Tutorialspoint "]
print(str1.join(some_list))

2. map関数で入力を高速に処理する

競技プログラミングでは、次のような入力を扱うことがよくあります。

1234567

これを数値のリストとして取得するには、次のように書くだけでOKです。

list(map(int, input().split()))

入力の種類にかかわらず、まずinput()関数で受け取り、その後map関数で変換するのが基本です。

>>> list(map(int, input("enter numbers:").split()))
enter numbers:1 2 3 4 5 6 7
[1, 2, 3, 4, 5, 6, 7]
>>>

map関数はPythonの組み込み関数の中でも特に便利な存在で、覚えておくと多くの場面で役立ちます。

3. setとリスト操作を活用する

リストから重複を除去したい場合、Javaなどの言語ではHashMapやその他の複雑な方法が必要ですが、Pythonではsetを使うだけで簡単に実現できます。

>>> print(list(set([1,2,3,4,3,4,5,6])))
[1, 2, 3, 4, 5, 6]

また、複数のリストを結合する際は、extend()とappend()の違いに注意しましょう。

>>> a = [1, 2, 3, 4]  # リスト1
>>> b = [5, 6, 7]      # リスト2
>>> a.extend(b)  # 要素が展開されて1つのリストになる
>>> a
[1, 2, 3, 4, 5, 6, 7]
>>> a.append(b)  # リストの中にリストが入る
>>> a
[1, 2, 3, 4, [5, 6, 7]]

4. 関数の中にコードを書く

Pythonは手続き型のコードもサポートしていますが、処理は関数内に記述する方が高速です。

def main():
    for i in range(2**3):
        print(x)
main()

こちらの方が、次のコードよりも優れています。

for x in range(2**3):
    print(x)

これは、CPythonの実装の仕組み上、ローカル変数へのアクセスがグローバル変数よりも高速だからです。

5. 標準ライブラリを最大限活用する

組み込み関数や標準ライブラリは、できる限り活用しましょう。例えば、次のようなコードの代わりに、

newlist = []
for x in somelist:
    newlist.append(myfunc(x))

次のように書けます。

newlist = map(myfunc, somelist)

同様に、標準ライブラリのitertoolsを使うと、よくある処理を大幅に高速化できます。例えば、順列の生成はわずか数行で実現できます。

>>> import itertools
>>> iter = itertools.permutations(["a","b","c"])
>>> list(iter)
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

6. ジェネレーターでメモリと時間を節約する

ジェネレーターは、コードのメモリ使用量と平均時間計算量の両方を削減できる優れた仕組みです。

def fib():
    a, b = 0, 1
    while 1:
        yield a
        a, b = b, a+b

まとめ

競技プログラミングでPythonのパフォーマンスを引き出すポイントは、「joinによる文字列連結」「map関数による入力処理」「setやitertoolsなどの標準ライブラリ活用」「関数化とローカル変数の利用」「ジェネレーターの活用」です。これらのテクニックを身につければ、複雑な問題にも十分な速度で対応できるコードが書けるようになります。