「同じ問題でも、データ構造を変えるだけで 1000 倍速くなる」 ことが普通にあります。本記事では基本 4 種類を、Python での書き方と計算量で見比べます。
1. 4 大データ構造
| 構造 | アクセス | 検索 | 挿入 | 削除 | メモリ |
|---|---|---|---|---|---|
| 配列 (動的) | O(1) | O(n) | O(1) 末尾 | O(n) | 連続 |
| 連結リスト | O(n) | O(n) | O(1) 先頭 | O(1) | ばらつき |
| ハッシュテーブル | — | O(1) | O(1) | O(1) | 領域大きめ |
| 二分探索木 (平衡) | — | O(log n) | O(log n) | O(log n) | 中間 |
2. 配列とリスト (Python)
list と deque の比較
Python
from collections import dequeimport time
# Python の list (動的配列) - 末尾追加は速い、先頭追加は遅いlst = []for i in range(100000): lst.append(i) # O(1) 平均 lst.insert(0, i) # O(n)、遅い!
# deque (両端キュー) - 両端の追加削除が O(1)dq = deque()for i in range(100000): dq.append(i) # O(1) dq.appendleft(i) # O(1) 速い!3. ハッシュテーブル (Python の dict / set)
dict は内部ハッシュテーブル
Python
# 1 万件の検索を比較import time
# リストで線形検索 - 遅いdata_list = list(range(10000))start = time.time()for q in [9999, 5000, 0]: print(q in data_list) # O(n)print(f'list: {time.time()-start:.4f}s')
# dict (ハッシュ) - 一瞬data_set = set(range(10000))start = time.time()for q in [9999, 5000, 0]: print(q in data_set) # O(1)print(f'set: {time.time()-start:.4f}s')4. ツリーと再帰
二分探索木 (基本構造)
Python
class Node: def __init__(self, value): self.value = value self.left = None self.right = None
class BST: def __init__(self): self.root = None
def insert(self, value): if not self.root: self.root = Node(value) return self._insert(self.root, value)
def _insert(self, node, value): if value < node.value: if node.left: self._insert(node.left, value) else: node.left = Node(value) else: if node.right: self._insert(node.right, value) else: node.right = Node(value)
# 使い方tree = BST()for v in [5, 3, 8, 1, 9, 4]: tree.insert(v)# 平衡している場合は検索 O(log n)5. データ構造の選び方
| 要件 | 推奨 | Python での書き方 |
|---|---|---|
| 順番に処理 | list | for x in lst: |
| 末尾に追加 | list | lst.append() |
| 先頭に追加 | deque | dq.appendleft() |
| 特定キーで検索 | dict / set | x in d / d[k] |
| 重複を除く | set | set(lst) |
| 最小/最大の取出し | heapq | heapq.heappush/pop |
| 順序付きキー検索 | ソート済み list + bisect / SortedDict | bisect.bisect_left |
6. 次の話
EP.09 では アルゴリズム へ。データ構造を活かして、探索・ソート・最短経路を効率良く解く方法を見ます。
この記事の感想を教えてください
あなたの 1 クリックで、本当にこの記事は更新されます。「もっと詳しく」「続編希望」が一定数集まった記事は、 ふくふくが 実際に内容を拡充したり続編記事を公開 します。 送信したリアクションはお使いのブラウザに記録され、再カウントされません。