Python 遅いものたち

Python に関する遅いものたちをまとめました．

Python

Python は遅い．

改善策

  • c++ を使う

numpy でないもの

numpy でないものは numpy であるものより遅い．

改善策

  • numpy を使う．

tuple

tuple に関するものは大体遅い．dict の key にしたり，リストに突っ込んでソートしたりするとやばい．tuple の比較自体が遅い．

改善策

  • tuple を使わない．
    • 例えば 2 要素の tuple で，要素が 2 つとも 109 以下なら，(x, y) は z = (x<<30) + y のように 1 つの整数に変換する．z から x,y を復元するには mask = (1<<30)-1 として x = z>>30, y = z&mask とすればよい．
  • tuple のソートは key を指定する

再帰

PyPy だと特に遅い．

改善策

多倍長整数

263 を超えると途端に遅くなる．

改善策

多次元リスト

遅い．

改善策

  • 一次元化する．
    • 例えば H×W サイズの二次元配列 A は，長さ HW の一次元配列 A' に対して，A'[W * i + j] = A[i][j] とすればよい．

list の append

遅い．

改善策

  • list のメモリをはじめに確保しておく．

入出力

入力がいっぱいやってくると詰む．

改善策

  • sys.stdin.readline を使う
  • 出力が複数行にわたるときは '\n' で join して一つの文字列で出力する

pow(x,k,mod)

何で遅いのかよくわかってない

改善策

  • mod を引数に取らないと除算高速化をしてくれるみたい
def fpow(x,k):
  res=1
  while k:
    if k&1:
      res=res*x%mod
    x=x*x%mod
    k>>=1
  return res