Python高速化まとめ - かんプリンの学習記録

競プロでのPythonはたとえ高速な(C++は通るような)アルゴリズムでも実装の仕方によってはTLEする(他の高速な言語に比べてしやすい).
Pythonの高速化の方法について気づいたことをまとめていく.

関数化

なんかグローバルで処理するよりも関数にしてローカルにした方が速い.

処理

${\downarrow}$

def main:
    処理
main()

リストの初期化とかでfor文回すときは内包表記使うと速い.

a = []
for _ in range(100):
    a.append([0] * 100)

${\downarrow}$

a = [[0] * 100 for _ in range(100)]

ある数で割った余りを求めるときには, 最後に1回だけ余りを取るよりも計算するたびに余りを取った方が速い.

MOD = 10**9+7
sum = 0
for i in range(10**8):
    sum += i*i
print(sum%MOD)

${\downarrow}$

MOD = 10**9+7
sum = 0
for i in range(10**8):
    sum += i*i
    sum %= MOD
print(sum)

queueを使うよりcollection.dequeを使った方が速い. dequeはqueueの上位互換なのでqueueを使うことはなさそう.

import queue
q = queue.Queue()
~

${\downarrow}$

from collection import deque
q = deque()
~

リストの要素の変更をしないならリストを使うよりタプルを使った方が速い.

v = [[i,i**2] for i in range(10**7)]
sum = 0
for i,j in v:
    sum += i+j

${\downarrow}$

v = [(i,i**2) for i in range(10**7)]
sum = 0
for i,j in v:
    sum += i+j