〈python〉競プロで処理を高速化したい

pythonで競技プログラミングをするとき、TLEが起こるのが悩み。
処理の遅いpythonでも、高速化できる裏技がたくさんありそう。

標準入力：sys.stdin.readlineを使う

組み込み関数のinput()を使っていたが、sys.stdin.readlineを使った方が早い。
ただし末尾の改行文字も読み取ってしまう（inputは改行文字を取り除いてくれる）。
sys.stdin.readline().rstrip()を使うのが良さそう。

import sys
a = sys.stdin.readline().rstrip()

Listを使いすぎない

なんでもListで処理しがち。でもListへのアクセスはとっても遅い。
末尾へのappendやpopは早いが、indexを使ったそれ以外の場所への挿入・代入はとにかく遅い。in,min,maxなどもO(n)の処理になる。
データの検索をしたいならdictやset、データの操作をしたいならcollections.dequeを使って、Listで処理をしすぎない。

内包表記を使う

list を作成するとき、

for i in range(10):
    list.append(i)

このようなfor文を使いがち。毎回appendを参照するコストがかかるそうなので、内包表記を使った方が早い。

list = [ i for i in range(10)]

ローカル変数を利用する

グローバル変数にアクセスするよりもローカル変数にアクセスする方が早いらしい。
コードを直接書いて実行するよりも、main関数にコードを入れるだけで早くなる。

def main():
   #処理を書く

if __name__ == '__main__':
    main()

Atcorderで他の方のコードを見ていると、他にもたくさん高速化できることがありそう…。奥が深い。
またそのうち他の方法もまとめたい。