E資格対策：Pythonデータ構造の深層【応用編】
E資格試験では、単にコードが動くかどうかだけでなく、「そのコードは大規模データに対して効率的か？」「メモリリークの原因にならないか？」という、より深い理解が求められます。
前回の基礎編に続き、今回はリストの先頭削除のコストやハッシュ衝突、ジェネレータの消費など、実務でも重要な応用知識を解説します。
1. リスト操作の計算量：どこを削除するかで速度が激変する
リストは便利なデータ構造ですが、要素を削除する位置によって処理速度が天と地ほど変わります。これはリストがメモリ上で連続して配置されているためです。
先頭削除 pop(0) vs 末尾削除 pop()
| 操作 | コード | 計算量 | 何が起きているか |
|---|---|---|---|
| 末尾削除 | list.pop() |
O(1) (高速) | 一番後ろを消すだけ。他の要素に影響はない。 |
| 先頭削除 | list.pop(0) |
O(N) (低速) | 先頭を消すと、空いた穴を埋めるために残りの全要素を1つずつ前にずらす処理が発生する。（玉突き事故のような状態） |
先頭への追加・削除を頻繁に行う場合は、リストの代わりに collections.deque を使いましょう。これは双方向リストで実装されており、先頭操作も O(1) で行えます。
リストの連結のコスト
c = a + b のようにリストを結合する場合、計算量は O(N + M) となります。これは、新しいリストを作るために、両方のリストの全要素をコピーする必要があるからです。
2. ハッシュテーブルの弱点：最悪計算量と衝突
辞書や集合は通常 O(1) で高速ですが、これはあくまで「平均」の話です。特定の条件下では劇的に遅くなる可能性があります。
ハッシュ衝突 (Hash Collision)
異なるデータなのに、計算されたハッシュ値（格納場所）が偶然同じになってしまうことを「衝突」と呼びます。
- 通常時: 衝突がなければ、一発でデータが見つかる → O(1)
- 最悪ケース: 運悪くすべてのデータが同じ場所（バケット）に衝突した場合、その中を順番に探すことになる → O(N)
E資格では「辞書の検索は常にO(1)である」という記述が間違い（正しくは平均O(1)、最悪O(N)）であると見抜く力が問われます。
3. メモリ管理の落とし穴：デフォルト引数とジェネレータ
Python特有の挙動により、意図しないバグを生むケースがあります。
ミュータブルなデフォルト引数（Q14）
関数の引数にリストなどのミュータブルなオブジェクトをデフォルト値として設定するのは危険です。
# 危険な書き方
def add(x, data=[]):
data.append(x)
return data
print(add(1)) # [1]
print(add(2)) # [1, 2] !? [2]ではない！理由： デフォルト引数 [] は関数が定義された時に一度だけ作成され、使い回されるからです。そのため、前の呼び出しの結果が残ってしまいます。
解決策： デフォルト値を None にして、関数内で初期化します。
ジェネレータの「使い切り」特性（Q18）
ジェネレータは「一度しか反復できない」イテレータです。
gen = (i for i in range(3))
# 1回目のループ：0, 1, 2 が出る
for x in gen: print(x)
# 2回目のループ：何も起きない！
for x in gen: print(x)一度最後まで回すとジェネレータは空っぽになります。再度データが必要な場合は、ジェネレータを作り直す必要があります。
4. 覚えておくべきメソッドと演算子の挙動
集合への追加と複合データ型（Q17）
集合（Set）の要素になれるのは「ハッシュ可能（不変）」なものだけです。
s.add((1, 2))：タプルは不変なのでOK。s.add([1, 2])：リストは可変なのでNG（TypeError）。
辞書の pop() とデフォルト値（Q19）
要素を削除しつつ、その値を取得する pop() メソッドも、キーがない場合のデフォルト値を指定できます。
val = d.pop('key', 0)これにより、try-except ブロックを書かずに安全に削除操作を行えます。
集合の差集合は非対称（Q20）
数学と同様、引き算の順序は結果を変えます。
A - B：AにあってBにないもの。B - A：BにあってAにないもの。
5. まとめ：E資格合格のためのチェックリスト
- ✅ リストの先頭削除
pop(0)は遅い (O(N))。 - ✅ 辞書・集合の検索は最悪ケースで O(N) になる（ハッシュ衝突）。
- ✅ タプルはリストよりわずかにメモリ効率が良い。
- ✅ 関数のデフォルト引数にリスト
[]を使ってはいけない。 - ✅ ジェネレータは一度ループすると空になる。
これらの知識は、E資格だけでなく、実務でパフォーマンスの良いコードを書くためにも必須のスキルです。基礎編と合わせて復習しておきましょう。
