リストの利点
リスト：最初のデータ構造
リスト（あるいは他の言語では配列と呼ばれるもの）は、特定の順序でアイテムを格納します。次の操作ができます：
- 位置にアクセスする：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" と "dog" はそれぞれ複数回登場しています。リストは重複を許可します。リストは、与えられた順序で与えられたものをそのまま保持します。
しかし、リストには弱点があります。"fish" がリストに含まれているかどうかを尋ねる場合にどうなるかを見てください。
# メンバーシップチェック — "fish" がリストに含まれているかどうかを確認する
if "fish" in pets: # "cat", "dog", "cat", "fish"... の各アイテムを一つずつスキャン
print("found!") # 4 個のアイテムをすべてチェックしなければならなかったコンピューターは "cat" をチェックしますが、含まれていません。次に "dog" をチェックしますが、含まれていません。次に "cat" をチェックしますが、含まれていません。最後に "fish" をチェックすると、含まれていることがわかります。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)のメンバーシップテストが得られます — アイテムが存在するかどうかを確認するのに、セットが5000アイテムもしくは5000万アイテムであっても同じ時間がかかります。
# メンバーシップチェック — セットに"fish"が含まれているかどうか
if "fish" in pets: # hash("fish") → ジャンプバケット → 見つかった
print("found!") # exactly 1 spotをチェックし、4をチェックしませんセットとリストのメンバーシップ
500人の学生の名前がセットにリストよりも格納されています。
students = {"Alex", "Maria", ..., "Zara", ...} # 500 names
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)セット + リストの "パターン" は、速い重複検出とともに順序の結果を提供します。
適切な構造を選択する
三つの問題。各問題ごとに決めます:リスト、セット、または両方
1. ユーザーが追加した順序で音楽のプレイリストを保存する必要があります。
2. ユーザー名が既に取られていないか、迅速にチェックする必要があります。
3. メールリストから重複を削除するが、登録順を保持する必要がある場合
重複除去問題
問題: 重複を削除し、順序を保持する
メール登録リストを受け取ります。ある人は二度登録しました。各人物に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: # O(N) の unique リストスキャン
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の登録がある場合、~10,000のチェックが必要になり、~50,000,000のチェックから減少します。
速度アップの計算
リストのみバージョンは O(N²) で、set+list バージョンは O(N) です。
重複解消するために 10,000 のメールサインアップデータ を持っています。
共通要素を見つける
問題: 両クラスの共通の項目を見つける
あなたは二つのクラスリストを持っています。両クラスに同時に登録されている学生を特定する必要があります。
遅いアプローチ: nested loops O(N × M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a: # N iterations
if student in class_b: # M scans each time
both.append(student)
# O(N × M) — each student scanned against all of class_b速いアプローチ: 一方のリストをセットに変換 O(N + M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b) # O(M) to build
both = []
for student in class_a: # N iterations
if student in class_b_set: # O(1) each time
both.append(student)
# O(N + M) — build the set once, check N times at O(1) eachあるいは、Python の組み込みの set の交差を使って簡単にしましょう:
both = set(class_a) & set(class_b) # O(N + M) & オペレーターは両セットに共通の要素をすべて見つけます。
スピードアップのために書き直す
学校には2つのクラブがあり、それぞれ200人のメンバーがあります。このコードは両クラブの生徒を検索します：
chess_club = [...] # 200 names
art_club = [...] # 200 names
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(1)に費やす構造を選びます。Nではなく。
このレッスンではリストとセットについて説明しました。 他のデータ構造も存在します（辞書、木、ヒープ）が、それぞれ異なる問題を解決します。 決定フレームワークは同じです：操作を理解し、それらが安価になるデータ構造を選びます。
---
深く掘り下げたいですか？ 量子計算のレッスンでは成長率とスケーリング計算について詳細に説明しています。 また、実用ソフトウェアでこの具体的なリストからセットへの修正が1,000倍のスピードアップを生み出した実世界の欠陥（MOAD-0001）についても説明しています。 こちらも見てください：[アルゴリズム的複雑性：失われた章](/en/un/unhamming_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)この本には10万語あります。