リストが便利な理由
リスト: 最初のデータ構造
リスト (一部の言語では配列と呼ばれます) は項目を特定の順序で格納します。次のことができます:
- 位置で任意の項目にアクセス: names[0] で最初の項目を取得。O(1) — 即座。
- 末尾に項目を追加: names.append("Zoe")。O(1) — 即座。
- すべての項目を順番に走査: for name in names。O(N) — 各項目を一度ずつ訪問。
リストは挿入した順序を保持します。最初の項目は最初のまま。最後は最後のままです。
# ペットのリスト
pets = ["cat", "dog", "cat", "fish", "dog"]
print(pets[0]) # "cat" — O(1) 即座
print(pets[3]) # "fish" — O(1) 即座
print(len(pets)) # 5 — 重複も保持注目: "cat" は2回登場します。"dog" も2回登場します。リストは重複を許可します。 与えられた通りに、与えられた順序で格納します。
しかしリストには弱点があります。次の質問をしたときに何が起こるか見てみましょう: "fish" はこのリストにありますか?
# メンバーシップ確認 — "fish" はリストにあるか?
if "fish" in pets: # ["cat", "dog", "cat", "fish"...] を一つずつ走査
print("found!") # 見つけるまでに4項目を確認コンピュータは "cat" を確認 — 違う。"dog" — 違う。"cat" — 違う。"fish" — そう! 答えを見つけるまでに4項目を走査しました。1,000項目あれば、1,000項目すべてを走査するかもしれません。このメンバーシップ確認のコストは O(N) です。
走査コストを予測
ランダムな順序で500人の生徒名を持つリストがあります。
リストに "Zara" が含まれているか確認したいとします。
students = ["Alex", "Maria", ..., "Zara", ...] # 500個の名前
if "Zara" in students:
print("enrolled")集合の動作の違い
集合: メンバーシップ質問のために作られた構造
集合 は ハッシュ化 という技法を使って一意な項目を格納します。項目を追加すると、コンピュータはハッシュ (数値の指紋) を計算し、その項目を格納する正確な場所を特定します。
メンバーシップを確認するとき、コンピュータは同じハッシュを計算し、正しい場所に直接ジャンプします。走査は不要です。
# ペットの集合
pets = {"cat", "dog", "cat", "fish", "dog"}
print(pets) # {"cat", "dog", "fish"} — 重複は除去
print(len(pets)) # 3 — 一意な項目のみリストとの3つの違いに注目してください:
1. 重複なし。 "cat" は入力に2回登場しましたが、集合は1コピーのみ保持します。
2. 保証された順序なし。 集合は項目を任意の順序で表示する可能性があります。
3. インデックスアクセスなし。 pets[0] と書くことはできません — 集合に位置はありません。
トレードオフ: 順序と重複を失います。O(1) のメンバーシップテスト を得ます — 項目が存在するか確認するのは、集合に5項目あろうと500万項目あろうと同じ時間です。
# メンバーシップ確認 — "fish" は集合にあるか?
if "fish" in pets: # hash("fish") → バケットへジャンプ → 発見
print("found!") # 4箇所ではなく、正確に1箇所を確認集合とリストのメンバーシップ
リストではなく 集合 に500人の生徒名が格納されているとします。
students = {"Alex", "Maria", ..., "Zara", ...} # 500個の名前
if "Zara" in students:
print("enrolled")並列比較
操作早見表
リストを使うべき場合:
- 項目が特定の順序で必要なとき (プレイリスト、レシピ、キュー)
- 位置によるアクセス (items[3])
- 重複を保持したいとき ("cat" が3回登場 = 3匹の猫)
集合を使うべき場合:
- 高速メンバーシップ確認 (「これを見たことがあるか?」)
- 自動的な重複除去
- 順序を気にしないとき
順序と高速検索の両方が必要な場合は両方を使う:
seen = set() # O(1) メンバーシップ確認
result = [] # 挿入順を保持
for item in data:
if item not in seen: # O(1) 確認
seen.add(item) # O(1) 追加
result.append(item) # O(1) 末尾追加
# 合計: O(N) — 1パス、各ステップ O(1)この「集合 + リスト」パターンは両者の良いところを与えます: 順序付けされた結果と高速な重複検出。
適切な構造を選ぶ
3つの問題があります。それぞれに対し、決めてください: リスト、集合、または両方?
1. ユーザーが追加した順序で曲のプレイリストを格納する必要がある。
2. ユーザー名がすでに使われているか素早く確認する必要がある。
3. メーリングリストから重複したメールを削除しつつ、登録順を保つ必要がある。
重複除去問題
問題: 順序を保ちつつ重複を除去
メール登録のリストを受け取ります。一部の人は2回登録しています。最初に登録した順序で、一人につき1通のメールを送る必要があります。
試み1: リストのみ (遅い)
signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
if email not in unique: # unique リストの O(N) 走査
unique.append(email)
# 動作する! しかし: O(N) 確認 × N 項目 = O(N²)100個の登録で約5,000回の確認。10,000個の登録で約50,000,000回の確認になります。
試み2: 集合 + リスト (高速)
signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
seen = set()
unique = []
for email in signups:
if email not in seen: # O(1) ハッシュ検索
seen.add(email) # O(1) 集合に追加
unique.append(email) # O(1) リストに末尾追加
# O(1) 確認 × N 項目 = O(N)同じ結果。同じ順序。しかし: 10,000個の登録に必要な確認が約50,000,000回ではなく約10,000回になりました。
高速化を計算
リストのみ版はO(N²)で動作します。集合+リスト版はO(N)で動作します。
10,000個のメール登録 を重複除去するとします。
共通要素を見つける
問題: 両方のリストに含まれる項目を見つける
2つのクラス名簿があります。両方のクラスに登録している生徒を見つける必要があります。
遅いアプローチ: 二重ループ O(N × M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a: # N 回反復
if student in class_b: # 毎回 M 回走査
both.append(student)
# O(N × M) — 各生徒が class_b 全体に対して走査される速いアプローチ: 1つのリストを集合に変換 O(N + M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b) # 構築に O(M)
both = []
for student in class_a: # N 回反復
if student in class_b_set: # 毎回 O(1)
both.append(student)
# O(N + M) — 集合を一度構築し、N回 O(1) で確認あるいはPythonの組み込み集合交差を使ってさらにシンプルに:
both = set(class_a) & set(class_b) # O(N + M)& 演算子は両方の集合に登場するすべての項目を見つけます。
高速化のために書き直す
学校に200人ずつのメンバーがいる2つのクラブがあります。次のコードは両方のクラブに所属する生徒を見つけます:
chess_club = [...] # 200個の名前
art_club = [...] # 200個の名前
both_clubs = []
for student in chess_club:
if student in art_club:
both_clubs.append(student)決定フレームワーク
あなたのデータ構造決定フレームワーク
項目のコレクションを格納するコードを書くたびに、問いましょう:
1. 項目を順序付けする必要があるか? → リスト
2. 高速メンバーシップ確認が必要か? → 集合
3. 順序と高速確認の両方が必要か? → 集合 + リストの併用
4. 重複が必要か? → リスト (集合は重複を落とす)
---
このレッスンからの重要な洞察: 同じプログラムが、同じ問題を解いていても、適切なデータ構造を選ぶだけで1,000倍から1,000,000倍速く動くことがあります。賢いトリックは不要。複雑な数学も不要。ただ問うだけ: 自分のコードはどの操作を最も頻繁に行うか? そして、それらの操作がO(N)ではなくO(1)で済む構造を選ぶ。
このレッスンではリストと集合を扱いました。他の問題を解決する他のデータ構造 (辞書、木、ヒープ) も存在します。決定フレームワークは同じです: 自分の操作を理解し、それを安価にする構造を選ぶ。
---
さらに深く学びたい? Big O レッスンでは増加率とスケーリング計算を詳しく扱います。Big O: どれだけ速ければ十分か? をご覧ください。unhamming コースでは、まさにこのリストから集合への修正が本番ソフトウェアで1,000倍の高速化をもたらした実世界の欠陥 (MOAD-0001) を扱います。The Missing Chapter: Algorithmic Complexity をご覧ください。
このコードをデバッグせよ
ある生徒が、本に登場する一意な単語の数を数えるためにこのコードを書きました:
words = book.split() # すべての単語のリスト
unique_count = 0
checked = []
for word in words: # N 個の単語
if word not in checked: # checked リストを走査
checked.append(word)
unique_count += 1
print(unique_count)本には100,000語あります。