はじめに
二重ループは、複数のデータを照合したり、組み合わせを調べたりするときによく使う処理です。しかし、データ件数が増えると比較回数も増えやすく、「正しく動くが遅い」という問題につながることがあります。
重要なのは、二重ループそのものを悪い処理と決めつけないことです。まず何を結果として得たいのかを固定し、その結果を変えずに、不要な比較を減らせないか、検索しやすいデータ構造へ変えられないか、同じ計算を繰り返していないかを順番に確認します。この記事では、その基本的な見直し方をPythonの例とともに解説します。
二重ループは入れ子だけで遅いとは限らない
二重ループの計算量は、「ループが2段ある」という見た目だけでは決まりません。外側でn件、内側でm件を毎回すべて処理するなら、おおむねn×m回の組み合わせを確認します。両方がn件ならn×n回です。
一方で、条件を満たした時点で内側のループを終了する処理や、内側の反復回数が外側の状態によって変わる処理もあります。そのため、「二重ループだから必ず遅い」「入れ子が増えると必ず指数関数的に増える」とは言えません。実際に何回の比較や計算が行われるのかを確認することが出発点です。
| 見直す対象 | 確認すること | 改善の方向 |
|---|---|---|
| 比較回数 | 全件同士を比較する必要があるか | 候補を先に絞る、不要な比較をしない |
| 検索方法 | 同じデータを何度も先頭から探していないか | setやdictなど検索に向く構造を使う |
| 繰り返し計算 | ループ中で同じ値を毎回計算していないか | ループ外で計算し、結果を再利用する |
改善前に「同じ結果」を定義する
高速化で最も重要なのは、変更前と変更後で処理の意味を変えないことです。たとえば「重複している値の種類数を数える」「同じ値の組み合わせ数を数える」「重複が1件でもあるか調べる」は、似て見えても別の処理です。
二重ループをsetへ置き換えれば必ず正しいわけではありません。setは重複しない要素を扱うため、重複数そのものが必要な処理では結果が変わることがあります。最適化前に、入力に対して何を出力する処理なのか、重複や順序をどのように扱うのかを確認し、改善後も同じ結果になることをテストします。
処理量を減らす3つの見直し方
1. 比較する候補を減らす
最初に確認したいのは、本当にすべての組み合わせを比較する必要があるかです。条件に合わないデータを先に除外できる、同じ組み合わせを逆順でもう一度確認している、目的の値が見つかった後も検索を続けている、といった処理では比較回数を減らせます。
ただし、途中でループを終了してよいのは、その後の候補を確認しなくても結果が変わらない場合だけです。高速化のために探索範囲を削って、必要な結果まで落とさないようにします。
2. setやdictなど検索に向くデータ構造を使う
「ある値が別の一覧に含まれているか」を何度も調べる処理では、毎回リストを先頭から探すより、検索用のsetやdictを先に作る方が効率化しやすくなります。Pythonのsetは重複しない要素の集合で、要素が含まれているかを調べる用途に使えます。dictはキーから対応する値を取得したい場合に向いています。
一方で、検索用データ構造を作る処理自体にも時間とメモリが必要です。データが少ない場合や検索が一度しかない場合は、変換によって必ず速くなるとは限りません。何度も検索する処理やデータ量が多い処理で効果を確認します。
3. ループ内で変わらない計算を外へ出す
ループの各回で同じ値を計算しているなら、その計算を繰り返す必要はありません。条件判定に使う基準値の計算、設定値の読み込み、同じ文字列の変換など、ループ中に変化しない処理は事前に1回だけ実行し、その結果を使い回せないか確認します。
ただし、ループごとに入力や状態が変わる計算まで外へ移動すると結果が変わります。「この値は反復中に本当に変化しないか」を確認してから移動することが必要です。
Python例で改善前後を比較する
例として、注文データに含まれる商品IDのうち、販売対象の商品IDに含まれるものを取り出す処理を考えます。注文側の重複はそのまま残し、販売対象に含まれるかどうかだけを判定するものとします。
改善前：一覧同士を二重ループで照合する
def filter_sellable_products(order_ids, sellable_ids):
result = []
for order_id in order_ids:
for sellable_id in sellable_ids:
if order_id == sellable_id:
result.append(order_id)
break
return resultこの方法では、注文IDごとに販売対象IDを順番に探します。該当するIDが見つからない場合は、販売対象IDを最後まで確認するため、データが増えるほど比較回数が増えやすくなります。
改善後：検索用のsetを先に作る
def filter_sellable_products(order_ids, sellable_ids):
sellable_set = set(sellable_ids)
return [
order_id
for order_id in order_ids
if order_id in sellable_set
]改善後は販売対象IDをsetへ変換し、各注文IDがその集合に含まれるかを確認します。注文IDの並びと重複はそのまま残るため、この例では改善前と同じ結果を得られます。全件同士を順番に照合する処理を避けられる点が改善ポイントです。
この書き換えが正しいのは、今回の目的が「販売対象に含まれる注文IDを取り出す」ことだからです。販売対象ID側の重複回数を数えたい場合など、必要な結果が異なる処理へそのまま適用してはいけません。
改善効果を測定する
コードを書き換えたら、読みやすくなった印象だけで高速化を判断せず、変更前後の実行時間を測定します。Pythonでは小さなコードの実行時間を測る標準モジュールとしてtimeitを利用できます。
- 同じ入力データで改善前後を比較する
- 1回だけでなく複数回測定し、極端なばらつきがないか確認する
- 小さいデータだけでなく、実際に問題が出る規模でも確認する
- 実行時間だけでなく、結果が同じであることもテストする
高速化には、データ構造を作るための追加コストやメモリ使用量との兼ね合いもあります。測定結果に十分な差がないなら、複雑な最適化を追加せず、分かりやすい実装を維持する判断も必要です。
まとめ
二重ループを高速化するときは、入れ子の形だけを見て削除するのではなく、何を結果として得る処理なのかを最初に固定します。そのうえで、比較候補を減らす、setやdictなど検索に向くデータ構造を使う、反復中に変わらない計算を外へ出す、という順で見直すと改善点を整理しやすくなります。
最適化後は、変更前と同じ結果になることを確認し、実行時間も測定します。処理の意味を守ったまま不要な仕事を減らすことが、二重ループを含むコードを安全に高速化する基本です。
