競プロでは、いかに速い動くコードを書くかが重要になってきます。
でないと、指定された時間内にプログラムが終了しないからです。
でないと、指定された時間内にプログラムが終了しないからです。
今回は、より速く動くコードを載せておきます。見つけ次第追加する予定です。
目次
書き方「こんなプログラムを書くには」
①1番速い書き方
②2番目に速い書き方
③...
1からnを順番に足す
①総和の公式を使う
n(n+1) / 2 という、あれです。
②ビルトインのsumを使う
sum(range(1000000))
③forを使って足していく
sum = 0
for n in range(1000000):
sum += n
[1, 2, 3, ...., n]というリストを作る
①ビルトインのlist関数を使う
l = list(range(1000000))
②リスト内包表記を使う
l = [n for n in range(1000000)]
③appendをキャッシュする
l = []
l_append = l.append
for n in range(1000000):
l_append(n)
④forループでappendする
l = []
for n in range(1000000):
l.append(n)
リストに特定の要素が含まれているかを何回も判定する
①集合に対してinで判定
l = list(range(10000))
s = set(l)
for n in range(10000):
n in s
②リストに対してinで判定
l = list(range(10000))
for n in range(10000):
n in l
リストの先頭に何度も値を追加する
①dequeに対してappendleftで先頭に要素を追加
from collections import deque
dq = deque()
for n in range(100000):
dq.appendleft(n)
②リストに対してinsertで先頭に要素を追加
l = []
for n in range(100000):
l.insert(0, n)
listは末尾への追加のみ速いものです。両端の追加にはdequeが強い！
| 処理内容 | listでの処理 | dequeでの処理 |
| 先頭に要素を追加 | O(N) | O(1) |
| 末尾に要素を追加 | O(1) | O(1) |
dequeの使い方についてはこちら。
- deque 両端での出し入れが速いキュー。
- defaultdict ファクトリ関数を呼び出して存在しない値を供給する辞書。
- Counter 数え上げをしてくれるset。たまに使うと楽なことがある。
「リストの要素の挿入」と「最小値（最大値）を取り出す」ことを繰り返す
①heapqライブラリを使う
②listを使う
heapqライブラリはPython標準のライブラリで、優先度付きキューというデータ型をしています。
計算量の比較は以下の通りです。
計算量の比較は以下の通りです。
| 処理内容 | listでの処理 | heapqでの処理 |
| 最小（最大）値を取り出す | O(N) | O(logN) |
| 要素を挿入する | O(N) | O(logN) |
O(N) > O(logN) より、heapqの方が速いことがわかります。
import heapq # heapqライブラリのimport a = [1, 6, 8, 0, -1] print(type(a)) # <class 'list'> heapq.heapify(a) print(type(a)) # <class 'list'>
heap化されたリストも、クラスはlistのようです。
主に使う関数は以下の3つです。
import heapq a = [1, 6, 8, 0, -1] heapq.heapify(a) # リストを優先度付きキューへ print(a) # 出力: [-1, 0, 8, 1, 6] (優先度付きキューとなった a) print(heapq.heappop(a)) # 最小値の取り出し # 出力: -1 (a の最小値) print(a) # 出力: [0, 1, 8, 6] (最小値を取り出した後の a) heapq.heappush(a, -2) # 要素の挿入 print(a) # 出力: [-2, 0, 1, 8, 6] (-2 を挿入後の a)
