女性向けエンジニアスクール
3秒でわかる
データをどう並べて保持するかを決める設計。選び方ひとつで検索や追加にかかる時間が桁で変わるため、処理速度の土台になる部分です。
もう少し詳しく
どういうものか
データ構造は、複数のデータをメモリ上でどう並べ、どう取り出せるようにするかの決まりごとです。配列、連結リスト、スタック、キュー、ハッシュ表、木、グラフなどがあります。それぞれ得意な操作と不得意な操作があり、たとえば配列は番号での取り出しが速い一方、先頭への挿入は後ろ全体をずらすため遅くなります。
なぜ必要か
同じ処理でも、選ぶ構造で実行時間が桁違いになるためです。1 万件のデータから特定の値を探す処理を考えると、配列を先頭から見る方式では平均 5000 回の比較が要ります。ハッシュ表なら 1 回で位置が決まります。この差は件数が増えるほど広がり、10 万件では 20 倍の開きになります。
アルゴリズムを工夫する前に、まず構造が合っているかを見るほうが効果が大きい場面は多くあります。処理を速くしたいという相談の多くは、リストで持っているものを辞書やセットに置き換えるだけで解決します。
具体例
# 配列 (リスト) からの検索は件数に比例して遅くなる
users = ["sato", "suzuki", "takahashi"]
print("suzuki" in users) # 先頭から順に比較
# 辞書ならキーから直接引ける
ages = {"sato": 28, "suzuki": 35}
print(ages["suzuki"]) # 1 回で決まる
# スタックは後入れ先出し
stack = []
stack.append(1); stack.append(2)
print(stack.pop()) # 2
# キューは先入れ先出し
from collections import deque
q = deque([1, 2])
q.append(3)
print(q.popleft()) # 1似た用語との違い
| 構造 | 得意な操作 | 苦手な操作 |
|---|---|---|
| 配列 | 番号での取り出し | 途中への挿入と削除 |
| 連結リスト | 途中への挿入と削除 | 番号での取り出し |
| ハッシュ表 | キーでの検索 | 順序を保った走査 |
| 木 (二分探索木) | 範囲検索、順序付きの検索 | 実装と均衡の維持 |
データ構造は「データの入れ物」、アルゴリズムは「その入れ物に対する手順」です。二分探索というアルゴリズムは、並んだ配列という構造が前提になります。両者は組で選びます。
つまずきやすいところ
Python のリストに対して pop(0) を繰り返すと、そのたびに全要素がずれるため、件数が増えると急激に遅くなります。先頭から取り出す処理には deque を使います。
もうひとつは、ハッシュ表なら常に速いという思い込みです。順序を保った走査や、範囲での絞り込みは苦手です。DB のインデックスに木構造が使われるのは、範囲検索が必要だからです。どの操作が多いのかを先に数えると、選ぶべき構造は自然に決まります。
