Python AtCoder入門 第10講 辞書(dict)と集合(set)

Python AtCoder入門 第10講 辞書(dict)と集合(set) ここから 第3部「道具を増やす」 に入ります。 第2部までで、AtCoderのA問題・B問題を解くための基礎は一通り揃いました。 1

今回のテーマ ここまでの知識だけでも、多くの問題は解けます。 しかし、 「解ける」と「速く正確に解ける」の間には、まだ大きな差があります。 第3部では、その差を埋めます。 2

辞書と集合 この講で扱うのは、 辞書 dict 集合 set です。 リストと二重ループで頑張れば書ける処理が、正しい道具を使うと数行で速く書けます。 3

コードファイル名の方針 この講でも、コード例ごとにファイル名を付けます。 dict_basic.py count_chars.py tuple_key.py set_basic.py set_speed.py answer_10_1.py 4

10-1 辞書の基本 リストは、 番号で中身を取り出す 入れ物でした。 A = [30, 10, 40] print(A[0]) 出力： 30 5

辞書とは 辞書は、 名前で中身を取り出す 入れ物です。 scores = {"Sato": 80, "Suzuki": 45} print(scores["Sato"]) 出力： 80 6

辞書の形 辞書は { } で作ります。 scores = {"Sato": 80, "Suzuki": 45} 中身は、 キー: 値 の形で並べます。 7

何に使うか 辞書は、次のようなデータに向いています。 名前と点数 文字と出現回数 座標と状態 「0番目、1番目」という並びより、 何に対応する値か が大事なときに使います。 8

追加と更新 scores = {} scores["Sato"] = 80 scores["Sato"] = 90 print(scores) 出力： {'Sato': 90} 存在しないキーなら追加、存在するキーなら上書きです。 9

削除 辞書から要素を削除するには del を使います。 scores = {"Sato": 80} del scores["Sato"] print(scores) 出力： {} 10

キーの存在判定 キーがあるかどうかは in で調べます。 scores = {"Sato": 80} print("Sato" in scores) print("Tanaka" in scores) 出力： True False 11

KeyError 存在しないキーを読もうとすると、エラーになります。 scores = {"Sato": 80} print(scores["Tanaka"]) KeyError このエラーは辞書でよく出ます。 12

get get() を使うと、キーがなくてもエラーになりません。 scores = {"Sato": 80} print(scores.get("Tanaka", 0)) print(scores.get("Sato", 0)) 出力： 0 80 13

getの形 d.get(キー, 初期値) キーがあれば、その値を返します。 キーがなければ、指定した初期値を返します。 カウント処理でとても便利です。 14

カウントの定石 d[c] = d.get(c, 0) + 1 これは、 あればその値、なければ0に、1を足す という意味です。 if c in d: で分岐を書く必要がなくなります。 15

辞書のループ 辞書を for で回すと、キーだけが取り出されます。 scores = {"Sato": 80, "Suzuki": 45} for name in scores: print(name, scores[name]) 16

items キーと値を同時に取り出すなら、 items() を使います。 for name, score in scores.items(): print(name, score) は、キーと値のタプルを順に返します。 それをアンパックしています。 items() 17

keys と values 辞書には次のメソッドもあります。 keys() ：キーだけ values() ：値だけ items() ：キーと値 たとえば、 sum(scores.values()) で値の合計が取れます。 18

dict_basic.py # Create a dictionary scores = {"Sato": 80, "Suzuki": 45} # Add and update scores["Takahashi"] = 72 scores["Suzuki"] = 60 # Access and check print(scores["Sato"]) print("Tanaka" in scores) print(scores.get("Tanaka", 0)) # Iterate over keys and values for name, score in scores.items(): print(name, score) # Aggregate the values print(sum(scores.values())) 19

dict_basic.py の出力 80 False 0 Sato 80 Suzuki 60 Takahashi 72 212 辞書の基本操作をまとめて確認できます。 20

count_chars.py # Read a string S = input() # Count each character count = {} for c in S: count[c] = count.get(c, 0) + 1 # Print in the order the characters first appeared for c, n in count.items(): print(c, n) 21

count_chars.py の実行例 入力例： banana 出力例： b 1 a 3 n 2 「何が何個あるか」を数える典型例です。 22

辞書は探す手間を消す リストで同じことをしようとすると、 値の種類ごとに探し直すことになりがちです。 辞書なら、キーに対応する値を直接更新できます。 辞書は「探す」という手間そのものを消してくれます。 23

辞書は追加順を覚えている Pythonの辞書は、追加した順序を覚えています。 そのため、 banana を数えると、 b, a, n の順に出力されます。 文字が最初に現れた順です。 24

10-2 辞書のキーに使えるもの 辞書のキーに使えるのは、 変更できないもの だけです。 第6講で学んだイミュータブルな値です。 25

キーに使える型 型 int str tuple list キーに使えるか ○ ○ ○ × リストは中身が変わる可能性があるので、キーにできません。 26

tupleはOK、listはNG d = {} d[(1, 2)] = "ok" d[[1, 2]] = "ng" 1行目はOKです。 2行目は TypeError になります。 27

座標をキーにする タプルがキーに使えることの大きな利点は、 座標を直接扱える ことです。 board = {} board[(3, 5)] = "#" board[(-100, 2000000)] = "#" 28

広い座標でも扱える 座標の範囲が非常に広い場合、2次元リストは作れません。 たとえば、 -10^9 <= x <= 10^9 のような範囲です。 辞書なら、実際に使った座標だけを保存できます。 29

getで空白マスを表す board = {} board[(3, 5)] = "#" print(board.get((3, 5), ".")) print(board.get((0, 0), ".")) 出力： # . 置かれていないマスは "." として扱えます。 30

tuple_key.py # Read the number of points N = int(input()) # Count how many times each coordinate appears count = {} for _ in range(N): x, y = map(int, input().split()) count[(x, y)] = count.get((x, y), 0) + 1 # Print coordinates that appear more than once for (x, y), n in count.items(): if n >= 2: print(x, y, n) 31

tuple_key.py の実行例 入力例： 5 1 2 3 4 1 2 5 6 1 2 出力例： 1 2 3 座標 (1, 2) が3回出ています。 32

キーもアンパックできる for (x, y), n in count.items(): ここでは、 キー (x, y) を x と y にアンパック 値を n に代入 しています。 第6講のアンパックの応用です。 33

10-3 集合の基本 集合 set は、 重複を許さない、順序のない集まり です。 辞書から値を取り除いて、キーだけにしたものと考えるとわかりやすいです。 34

集合の例 s = {3, 1, 4, 1, 5} print(s) 出力例： {1, 3, 4, 5} 重複した 1 が消えています。 順序は保証されません。 35

集合の作り方 s = {3, 1, 4} s = set() s = set([3, 1, 4, 1]) 注意： {} は空の集合ではありません。 空の辞書です。 36

空の集合 空の集合を作るときは、 s = set() です。 s = {} と書くと、辞書になります。 ここはよく間違えます。 37

追加・削除・判定 s = set() s.add(3) s.add(3) print(len(s)) s.discard(3) print(3 in s) 出力： 1 False 同じものを追加しても1つのままです。 38

discard と remove 集合には remove() もあります。 しかし、存在しない値を消そうとすると KeyError になります。 s.discard(x) なら、存在しなくてもエラーになりません。 安全に消すなら discard() です。 39

用途1：重複の除去 リストから重複を消して種類数を数えるなら、集合です。 A = [3, 1, 4, 1, 5, 9, 2, 6, 5] print(len(set(A))) 出力： 7 40

用途2：集合演算 数学の集合と同じ演算ができます。 演算 記号 和集合 `A 積集合 A & B 差集合 A - B 意味 B` 両方に含まれる Aにあり、Bにない 41

set_operations.py A = {1, 2, 3, 4} B = {3, 4, 5} print(A | B) print(A & B) print(A - B) 出力例： {1, 2, 3, 4, 5} {3, 4} {1, 2} 42

set_basic.py # Read N and the list of N integers N = int(input()) A = list(map(int, input().split())) # Number of distinct values print(len(set(A))) # Are all the values distinct? if len(set(A)) == N: print("Yes") else: print("No") 43

set_basic.py の実行例 入力例： 6 3 1 4 1 5 9 出力例： 5 No 1 が重複しているので、すべて異なるわけではありません。 44

重複がないか判定する定石 len(set(A)) == len(A) なら、すべての要素が異なります。 「全要素が異なるか」を問う問題でよく使います。 45

common_values.py # Read the two lists N = int(input()) A = set(map(int, input().split())) M = int(input()) B = set(map(int, input().split())) # Common values print(len(A & B)) # Values only in A print(len(A - B)) # All distinct values print(len(A | B)) 46

common_values.py の実行例 入力例： 5 1 2 3 4 5 4 3 4 5 6 出力例： 3 2 6 入力時点で set(...) にしています。 47

10-4 in の速度差 この節が、本講で最も重要です。 同じ in でも、 リストに使う場合 と 集合・辞書に使う場合 では速度が大きく違います。 48

リストのinは遅い リストの in は、先頭から順に探します。 要素がN個あれば、最悪N回の比較が必要です。 x in A Aがリストなら、要素数に比例して時間がかかります。 49

集合・辞書のinは速い 集合と辞書の in は、要素数が多くてもほぼ一瞬です。 中身を順に調べるのではなく、 値から直接場所を計算する仕組み になっているためです。 50

inの速さ データ構造 in の速さ リスト 遅い 集合 速い 辞書 速い ループの中で使うと、この差が大きく出ます。 51

危険な例 for x in A: if x in B: count += 1 もし B がリストなら、毎回Bの中を探します。 N = 100000 , M = 100000 なら、最大で100億回の比較です。 TLEになります。 52

対策はsetにするだけ B = set(B) for x in A: if x in B: count += 1 これだけで、 in が高速になります。 100億回の比較が、10万回程度になります。 53

鉄則 ループの中で in を使うなら、相手を集合にする。 B = set(B) この1行で、TLEがACに変わることがあります。 54

set_speed.py import time # Prepare 100000 values N = 100000 data = list(range(N)) data_set = set(data) # Search 10000 times in a list start = time.time() for i in range(10000): _ = (N - 1) in data print(f"list: {time.time() - start:.3f} sec") # Search 10000 times in a set start = time.time() for i in range(10000): _ = (N - 1) in data_set print(f"set: {time.time() - start:.3f} sec") 55

set_speed.py の出力例 list: 7.316 sec set: 0.001 sec 実行時間は環境によって変わります。 しかし、リストと集合で大きな差が出ることは体感できます。 56

第3部の主題 アルゴリズムを大きく変えなくても、 データ構造を変えるだけで速くなる ことがあります。 これが第3部の主題です。 「解ける」から「速く正確に解ける」へ進みます。 57

使い分けの整理 やりたいこと 順番に並べる 番号でアクセスする 存在判定を高速にする 重複を消す キーに対応する値を持つ 何が何個あるか数える 使うもの リスト リスト 集合 集合 辞書 辞書 58

判断の基準 迷ったら、次で考えます。 番号で取り出したいか 名前で取り出したいか あるかないかだけ知りたいか 何個あるか数えたいか 目的に合う道具を選びましょう。 59

章末まとめ：辞書 辞書は、 {キー: 値} で作ります。 番号ではなく、名前で中身を取り出す入れ物です。 追加も更新も、 d[key] = value です。 60

章末まとめ：get 存在しないキーを読むと KeyError になります。 安全に読むなら、 d.get(key, default) カウントの定石は、 d[x] = d.get(x, 0) + 1 です。 61

章末まとめ：辞書のループ で辞書を回すと、キーだけが取れます。 キーと値の両方を使うなら、 for for key, value in d.items(): です。 値だけなら d.values() が使えます。 62

章末まとめ：キーに使えるもの 辞書のキーに使えるのは、変更できないものです。 数値 文字列 タプル リストはキーにできません。 タプルをキーにすると、座標を直接扱えます。 63

章末まとめ：集合 集合は、重複を許さない集まりです。 s = set() 空の集合は {} ではなく set() です。 set(A) で重複を消せます。 64

章末まとめ：集合演算 集合演算は次の通りです。 A | B ：和集合 A & B ：積集合 A - B ：差集合 共通要素や片方にしかない要素を簡単に求められます。 65

章末まとめ：inの速度 リストの in は遅いです。 集合・辞書の in は速いです。 ループの中で in を使うなら、相手を集合にする。 これは鉄則です。 66

練習問題 10-1 共通して持っているもの 太郎さんはN個のカードを、次郎さんはM個のカードを持っています。 カードには整数が書かれています。 両方が持っている整数の種類数 を出力してください。 67

練習問題 10-1：入力と出力 入力例： 5 1 2 3 4 5 4 3 4 5 6 出力例： 3 共通するのは 3 , 4 , 5 です。 68

answer_10_1.py # Read the two card sets N = int(input()) A = set(map(int, input().split())) M = int(input()) B = set(map(int, input().split())) # Values that appear in both print(len(A & B)) 集合の積集合を使います。 69

answer_10_1_loop.py # Read the two card sets N = int(input()) A = set(map(int, input().split())) M = int(input()) B = set(map(int, input().split())) count = 0 for x in A: if x in B: count += 1 print(count) B が集合なので、 in が高速です。 70

練習問題 10-2 最も多く出た数 N個の整数が与えられます。 最も多く出現した整数と、その出現回数を出力してください。 同じ回数のものが複数ある場合は、 そのうち最小のもの を出力します。 71

練習問題 10-2：入力と出力 入力例： 7 3 1 4 1 5 3 1 出力例： 1 3 1 が3回出ています。 72

answer_10_2.py
# Read N and the list of N integers
N = int(input())
A = list(map(int, input().split()))
# Count occurrences
count = {}
for x in A:
count[x] = count.get(x, 0) + 1
# Find the most frequent value
best_value = -1
best_count = 0
for value, n in count.items():
if n > best_count:
best_value = value
best_count = n
elif n == best_count and value < best_value:
best_value = value
print(best_value, best_count)

73

answer_10_2.py のポイント 更新条件は2段階です。 出現回数が多ければ更新 出現回数が同じなら、値が小さいときだけ更新 値の範囲が広いので、個数管理には辞書を使います。 74

練習問題 10-3 初めて重複する位置 N個の整数が与えられます。 先頭から順に見たとき、 それまでに出てきた整数と同じものが初めて現れる位置 を1始まりで出力してください。 最後まで重複がなければ -1 です。 75

練習問題 10-3：入力と出力 入力例： 6 3 1 4 1 5 9 出力例： 4 4番目の 1 が、2番目の 1 と重複しています。 76

answer_10_3.py # Read N and the list of N integers N = int(input()) A = list(map(int, input().split())) # Remember the values we have seen so far seen = set() answer = -1 for i, x in enumerate(A, 1): if x in seen: answer = i break seen.add(x) print(answer) 77

answer_10_3.py のポイント 「それまでに出てきたもの」を集合で管理します。 seen = set() は、重複判定の後に書きます。 先に追加すると、自分自身と重複してしまいます。 seen.add(x) 78

第10講まとめ この講では、 辞書と集合 を学びました。 どちらも、B問題を速く正確に解くための重要な道具です。 79

次回予告 次の第11講では、 collectionsモジュール を扱います。 この講で書いた、 d.get(c, 0) + 1 というカウント処理が、さらに短く書けるようになります。 80