in listをin setに変えたら2985倍速くなった話。Pythonで最初に直すべき3箇所
アルゴリズムの改造も、並列化も不要。書き方を1行変えるだけで、笑えない倍率が出ました。
先に結果を見てください
| 改善項目 | 最大速度向上 |
|---|---|
in list → in set
|
2985倍 |
list.insert(0, i) → deque.appendleft(i)
|
381倍 |
文字列 += → "".join()
|
8.7倍 |
数字がちょっと笑えないレベルなので、計測結果ごと残しておきます。
本記事のリポジトリ
1. in list → in set（最大 2985倍）
# Before
found = target in list_data # O(n) — 先頭から1件ずつ線形探索
# After
found = target in set_data # O(1) — ハッシュで一発
なぜ差が出るか
| データ構造 | 探索方法 | 計算量 |
|---|---|---|
list |
先頭から1件ずつ比較 | O(n) |
set |
ハッシュテーブルで直接参照 | O(1) |
listはデータが10倍になれば探索も10倍遅くなります。setはデータ量が増えてもほぼ一定です。
if x in some_list という書き方はどのコードにも必ずあるので、ここを直すだけでも体感が変わることがあります。
2. list.insert(0, i) → deque.appendleft(i)（最大 381倍）
# Before
items = []
for i in range(n):
items.insert(0, i) # 追加のたびに全要素を後ろへシフト
# After
from collections import deque
items = deque()
for i in range(n):
items.appendleft(i) # 両端操作が O(1)
なぜ差が出るか
list.insert(0, ...) は先頭に1件追加するたびに、それ以降の全要素を1つ後ろにずらします。要素数が増えるほど、その移動コストも増えるため、全体では O(n²) になります。
deque（双方向キュー）は先頭・末尾への追加・削除がどちらも O(1) です。
キューのような処理を list で書いているコードがあれば、ほぼ確実にここが詰まっています。インターフェースはほぼ変わらず、数字だけ変わります。
3. 文字列 += → "".join()（最大 8.7倍）
# Before
result = ""
for p in parts:
result += p # ループのたびに新しいstr オブジェクトを生成
# After
result = "".join(parts) # 必要サイズを計算してから1回で結合
なぜ差が出るか
Pythonの文字列は**イミュータブル（変更不可）**です。+= をするたびに「古い文字列 + 新しい文字列」のコピーを毎回作り直すため、ループが増えるほどメモリ確保とコピーが積み上がります。
join() は事前に合計サイズを計算して、メモリを1回だけ確保してから結合するため高速です。
倍率は上2つと比べると小さく見えますが、ループ回数が多いコードでは確実に効いてきます。
まとめ：今すぐ確認すべき3箇所
| # | 直す前 | 直した後 | 効く場面 |
|---|---|---|---|
| 1 | x in list |
x in set |
検索を繰り返すとき |
| 2 | list.insert(0, x) |
deque.appendleft(x) |
先頭への追加を繰り返すとき |
| 3 | ループ内の +=
|
"".join() |
文字列を連結し続けるとき |
いずれも「アルゴリズムを変える」のではなく、データ構造と組み込み関数の使い方を変えるだけです。既存コードへの影響も最小限なので、まず探してみてください。
計測条件
- 計測ライブラリ：
timeit - 実行設定：
number=10、repeat=5、最小値採用 - データサイズ：N = 10,000 / 30,000 / 50,000
python3 benchmark.py --sizes 10000,30000,50000 --number 10 --repeat 5
詳細な計測結果は benchmark_results.txt を参照してください。
リポジトリ（スターをもらえると喜びます）