月影

日々の雑感

【E資格対策】Pythonデータ構造ドリル10選 | 計算量とメモリ管理の応用　その２

 

E資格レベル：Pythonデータ構造 10本ノック（発展編）

計算量・メモリ管理・内部実装の深掘り
計算量 (Big-O)

Q11. リストの先頭要素削除の計算量

要素数 N のリスト my_list に対し、my_list.pop(0) を実行して先頭の要素を削除した場合の平均計算量（Big-O）として正しいものはどれか。

答えを見る

正解：C. O(N) (線形時間)

解説：リストはメモリ上で連続しているため、先頭の要素を削除すると、その後の要素すべてを一つずつ前にずらす（再配置する）必要があります。この操作回数は N に比例するため、計算量は O(N) です。末尾の削除（pop()）は O(1) です。

内部実装・計算量

Q12. 辞書とセットの最悪計算量（ハッシュ衝突）

ハッシュテーブル（辞書や集合の内部構造）におけるキーの検索（key in d や d[key]）の最悪計算量として正しいものはどれか。

答えを見る

正解：C. O(N) (線形時間)

解説：通常は平均 O(1) ですが、**ハッシュ衝突**が発生し、すべてのキーが同じバケット（格納場所）に入ってしまった最悪のケースでは、目的のキーを見つけるためにすべての要素を順番に比較する必要が生じ、計算量は O(N) に悪化します。

メモリ効率

Q13. タプルの生成効率

大量の要素 N を持つリストとタプルを生成する際、タプル生成のメモリおよび処理効率に関する記述として最も適切なものはどれか。

答えを見る

正解：A. タプルは不変なので、リストより生成速度とメモリ効率がわずかに高い。

解説：タプルはイミュータブルであるため、リストが必要とする「要素変更のための予約メモリ領域」が不要です。このため、タプルはリストよりも**コンパクト**であり、生成時のオーバーヘッドも少なく、わずかに効率的です。

メモリ管理・関数の落とし穴

Q14. ミュータブルなデフォルト引数

以下のコードを実行した際、list_a と list_b の出力として正しいものはどれか。

def add_to_list(element, data=[]):
    data.append(element)
    return data

list_a = add_to_list(1)
list_b = add_to_list(2)
答えを見る

正解：B. list_a: [1], list_b: [1, 2]

解説：デフォルト引数の data=[] は、関数が定義されたときに**一度だけ評価**されます。リストはミュータブル（可変）なため、2回目の呼び出しで list_a が使用したのと同じリストオブジェクトが再利用され、要素が追加されます。この挙動を避けるには、data=None をデフォルト値とし、関数内で if data is None: data = [] と初期化します。

計算量 (Big-O)

Q15. リストの連結（+ 演算子）の効率

要素数 N のリスト a と要素数 M のリスト b を連結する操作 c = a + b の計算量として正しいものはどれか。

答えを見る

正解：C. O(N + M) (線形時間)

解説：+ 演算子は、元のリストを変更せず、**新しいリスト**を作成します。この際、N 個と M 個の要素すべてを新しいメモリ領域にコピーする必要があるため、処理時間は総要素数に比例します。

プログラミングの落とし穴

Q16. for ループ中のリスト変更

以下のコードが無限ループ（または非常に長いループ）に陥る理由を説明する最も適切なものはどれか。

a = [1, 2, 3]
for x in a:
    if x % 2 != 0:
        a.append(x)
答えを見る

正解：B. ループ中に要素が末尾に追加され、リストのサイズが常に大きくなるため、ループの終端に到達しない。

解説：for ループがリストの要素を反復処理している間に、append() によってリストの末尾が伸び続けるため、イテレータが終端にたどり着くことができず、実質的に無限ループとなります。ループ中にリストを変更する際は、元のリストのコピー（a[:]など）に対してループを実行すべきです。

ハッシュ可能性

Q17. 集合への複合データ型の追加

集合 s = {1, 2} に、リスト [3, 4] とタプル (5, 6) を追加しようとしたとき、エラーになる操作はどれか。

答えを見る

正解：C. s.add([3, 4])

解説：集合の要素も辞書のキーと同じく**ハッシュ可能（Hashable）**である必要があります。リスト（[]）はミュータブル（可変）なためハッシュを持てず、追加しようとすると TypeError が発生します。タプル（()）は不変なので追加可能です。

ジェネレータ・メモリ管理

Q18. ジェネレータの消費（一度きりのアクセス）

以下のコードを実行した後、再度 for x in x: を実行しようとした場合の結果として正しいものはどれか。

x = (i for i in range(5)) # ジェネレータ式
# 最初の消費
for i in x:
    pass 
# 2回目のループ
for x in x: 
    print(x)
答えを見る

正解：C. 何も出力されず、ループが即座に終了する。

解説：ジェネレータは**一度しか反復処理できない（消費される）**イテレータです。最初のループで全ての値が生成・消費された後、ジェネレータは空になります。2回目のループでは、ジェネレータはすぐに終端を検知し、ループが実行されることなく終了します。

メソッドの挙動

Q19. 辞書の pop() メソッドとデフォルト値

辞書 d = {'a': 1, 'b': 2} からキー 'c' の要素を**削除**しようとした際、エラーを出さずに 0 を返したい。以下のコードで目的を達成できるものはどれか。

答えを見る

正解：A. d.pop('c', 0)

解説：pop() メソッドは、キーが存在しない場合に備えて、第二引数に**デフォルト値**を指定できます。このデフォルト値は、キーが見つからなかったときにエラーの代わりに返されます。Dの get() は削除機能がありません。

集合演算

Q20. 集合の差集合の非対称性

集合 A = {1, 2, 3} と B = {3, 4, 5} について、`A - B` と `B - A` の実行結果として正しいものはどれか。

答えを見る

正解：B. A - B: {1, 2}, B - A: {4, 5}

解説：差集合（- 演算子）は、**非対称**な演算です。A - B は「AにあってBにないもの」、B - A は「BにあってAにないもの」を意味します。