list
aとbをリストとする。
| 操作 | 計算量 | 説明 |
|---|---|---|
a[i] |
O(1) | 要素へのアクセス・代入 |
a.append(x) |
O(1) | 末尾に要素追加 |
a.pop() |
O(1) | 末尾要素取り出し |
a.pop(0) |
O(n) | 先頭要素取り出し |
a.insert(i,x) |
O(n) | 指定の位置への要素挿入（末尾以外は遅い） |
del a[i] |
O(n) | 要素削除（末尾以外は遅い） |
x in a |
O(n) | 要素が存在しているかどうか |
a.index(x) |
O(n) |
xと一致する最初の要素のindexを返す |
a.count(x) |
O(n) |
xの出現回数を返す |
a.sort(), sorted(a) |
O(nlogn) | 昇順に並び替える |
a.reverse() |
O(n) | 逆順に並び替える |
min(a),max(a),sum(a) |
O(n) | 最小値、最大値、和 |
a[i:j] |
O(j-i) | スライス |
a+b |
O(len(a)+len(b)) | リストの足し算 |
len(a) |
O(1) | 長さ取得 |
deque（両端キュー）
from collections import deque
d = deque()
| 操作 | 計算量 | 説明 |
|---|---|---|
d.append(x) |
O(1) | 末尾追加 |
d.appendleft(x) |
O(1) | 先頭追加 |
d.pop() |
O(1) | 末尾要素取り出し |
d.popleft() |
O(1) | 先頭要素取り出し |
d[0], d[-1] |
O(1) | 両端要素へのアクセス |
d[i] |
O(n) | 両端以外の要素へのアクセス |
d.rotate(k) |
O(k) | 要素を円環状に回転させる |
d.extend(list) |
O(k) | 長さkの配列をまとめて末尾に追加 |
d.extendleft(list) |
O(k) | 長さkの配列をまとめて先頭に追加 |
x in d |
O(n) | 要素が存在しているかどうか |
len(d) |
O(1) | 長さ取得 |
-
deque(maxlen=K)で固定長にすることができ、はみ出した要素が自動的に反対端から捨てられる（押し出される感じ）
d = deque([1,2,3], maxlen=3) # [1,2,3]
d.append(4) # [2,3,4]
d.appendleft(5) # [5,2,3]
rotate()について
d = deque([1,2,3,4,5])
d.rotate(1) # [1,2,3,4,5]→[5,1,2,3,4] 右に１ずれる
d.rotate(2) # [1,2,3,4,5]→[4,5,1,2,3] 右に２ずれる
d.rotate(-1) # [1,2,3,4,5]→[2,3,4,5,1] 左に1ずれる
d.rotate(-2) # [1,2,3,4,5]→[3,4,5,1,2] 左に2ずれる
# 要素数より大きい場合、回転数は要素数で割った余りになる
d.rotate(7) # [1,2,3,4,5]→[4,5,1,2,3] 右に２ずれる
- 両端以外の要素にアクセスする場合は
listの方が優れている。
heapq（優先度付きキュー）
最小ヒープ（親ノードの値は常に子ノードの値以下）
import heapq
h = []
heapq.heappush(h, x)
top = heapq.heappop(h) # 最小値が取り出される
要素全てに-1をかけることで、最大ヒープ（親ノードが常に子ノード以上）として扱うこともできる
| 操作 | 計算量 | 説明 |
|---|---|---|
heapify(a) |
O(n) | リストをヒープ化（一個ずつpushより速い） |
heappush(h, x) |
O(logn) |
hに要素xを追加 |
heappop(h) |
O(logn) | 最小値を取り出す |
h[0] |
O(1) | 最小値へのアクセス |
heappushpop(h, x) |
O(logn) | 追加→最小値取り出しを実行 |
heapreplace(h, x) |
O(logn) | 最小値取り出し→追加をまとめて実行 |
nlargest(k, h) |
O(nlogk) | 上位k個を取得 |
nsmallest(k, h) |
O(nlogk) | 下位k個を取得 |
set（集合）
aとbをsetとする。
| 操作 | 計算量 | 説明 |
|---|---|---|
a.add(x) |
O(1) | 要素xを追加 |
a.remove(x) |
O(1) | 要素xが存在しない場合はエラー |
a.discard(x) |
O(1) | 要素xが存在しない場合は何もしない |
x in a |
O(1) | 要素xが存在するかどうか |
len(a) |
O(1) | |
a | b |
O(len(a)+len(b)) | 和を取る |
a & b |
O(min(len(a),len(b))) | 積を取る |
a - b |
O(len(a)) | 差を取る |
- 存在するかどうかのチェックが速いことが最大の特徴
dict,defaultdict（連想配列（辞書））
| 操作 | 計算量 | 説明 |
|---|---|---|
dict[k] |
O(1) | 参照・代入 |
k in dict |
O(1) | キーkがあるかどうか |
del dict[k] |
O(1) | キーkを削除 |
len(dict) |
O(1) | キーの数を取得 |
from collections import defaultdict
# 引数にはvalueの型を指定する
# 存在しないkeyにアクセスしてもエラーを出さない
d = defaultdict(list)
d["A"].append(1)
d["A"].append(3)
d["B"].append(2) # {'A': [1, 3], 'B': [2]}
cnt = defaultdict(int)
cnt["A"] += 1
cnt["A"] += 1
cnt["B"] += 1 # {'A': 2, 'B': 1}
# lambdaを使って、初期値を設定する
d = defaultdict(lambda: 10)
print(d["A"]) # 10
# 二次元辞書
d = defaultdict(lambda: defaultdict(int))
d["Alice"]["math"] += 1
d["Alice"]["english"] += 2
print(d)
'''
{
"Alice": {
"math": 1,
"english": 2
}
}
'''
SortedList（順序付き集合）
C++のstd::set, multisetの代替として使える。
要素を常にソートされた状態で保持してくれるリスト。
from sortedcontainers import SortedList
sl = SortedList()
| 操作 | 計算量 | 説明 |
|---|---|---|
sl.add(x) |
O(√n) | 非常に高速(lognに近い) |
sl.remove(x) |
O(√n) |
discardの挙動はsetと同じ |
sl[i] |
O(logn) |
i番目の要素にアクセス |
bisect_left(x) |
O(logn) | 要素xの最も左側の挿入位置を返す |
bisect_right(x) |
O(logn) | 要素xの最も右側の挿入位置を返す |
sl.index(x) |
O(logn) |
xのindexを取得 |
sl = SortedList()
sl.add(5)
sl.add(1)
sl.add(3) # [1,3,5] 常にソートされている
bisect（二分探索）
ソート済み（昇順）のリストに対する二分探索
aはlistである。
| 操作 | 計算量 | 返り値 | 意味 |
|---|---|---|---|
bisect_left(a,x) |
O(logn) |
xを入れられる最も左の位置 |
x未満の要素数 |
bisect_right(a,x) |
O(logn) |
xを入れられる最も右の位置 |
x以下の要素数 |
from bisect import bisect_left, bisect_right
a = [1, 3, 3, 3, 5, 7]
i = bisect_left(a, 3) # 1
j = bisect_right(a, 3) # 4