Atcoderに挑戦
プログラミングの技術向上のためにAtCoderに挑戦してみましたが、
pythonではTLE（時間超過）してしまうので対策を調査しました。
標準入力について
pythonの標準入力input()は遅いようです。
普通のやり方
n = int(input()) a = [int(input()) for _ in range(n)]
早いやり方
import sys input = sys.stdin.readline n = int(input()) a = [int(input()) for _ in range(n)]
Listについて
Listへのランダムアクセスは遅いようです。
appendやpopは早いがinsertや末尾以外のpopは遅い。
先頭へ追加・削除をしたい場合はdequeを使う。
in、max、minは遅いのでsetやDictを使う。
普通のやり方
| Operation | Code | Average Case |
|---|---|---|
| Append | l.append(x) |
O(1) |
| Pop last | l.pop() |
O(1) |
| Pop intermediate | l.pop(i) |
O(n) |
| Insert | l.insert(i, x) |
O(n) |
| in | x in l |
O(n) |
| min, max | min(l), max(l) |
O(n) |
早いやり方
| data structure | Operation | Code | Average Case |
|---|---|---|---|
| set | in | x in s |
O(1) |
| set | add | s.add(x) |
O(1) |
| dict | in | x in d |
O(1) |
| dict | Get item | d[x] |
O(1) |
| dict | Set item | d[x] = y |
O(1) |
