はじめに
順序変更に対して同じ結果が得られるネストした繰り返し処理(forループ)の場合、長い方を内側にして回した方が処理が速いようです。(どこかでそのような記事を読んだことがあるのですが、探せませんでした。)
本記事では、その事について実際に計測して比較しました。
@fujitanozomuさん、@YewShmzさん、@tenmyoさん、@minegishirei_v2さん、@yoshi389111さん、この記事へのご教授に心より感謝いたします。
実装
Google Colabで作成した本記事のコードは、こちらにあります。
結果
Google Colabのセル内をtimeitで計測しました。100ループ(-n 100)を10セット(-r 10)した結果を表記しています。
2ネストループ
%%timeit -r 10 -n 100
irange = ['hoge'] * 10000
jrange = ['hoge'] * 10
for i in irange:
for j in jrange:
pass
# -> 2.33 ms ± 95.5 µs per loop (mean ± std. dev. of 10 runs, 100 loops each)
%%timeit -r 10 -n 100
irange = ['hoge'] * 10
jrange = ['hoge'] * 10000
for i in irange:
for j in jrange:
pass
# -> 1.66 ms ± 59.5 µs per loop (mean ± std. dev. of 10 runs, 100 loops each)
| 平均 | |
|---|---|
| 内側が短い | 2.33 ms |
| 内側が長い | 1.66 ms |
内側が長い方が速い結果になりました。
3ネストループ
%%timeit -r 10 -n 100
irange = ['hoge'] * 200
jrange = ['hoge'] * 50
krange = ['hoge'] * 20
for i in irange:
for j in jrange:
for k in krange:
pass
# -> 4.23 ms ± 1.08 ms per loop (mean ± std. dev. of 10 runs, 100 loops each)
%%timeit -r 10 -n 100
irange = ['hoge'] * 20
jrange = ['hoge'] * 50
krange = ['hoge'] * 200
for i in irange:
for j in jrange:
for k in krange:
pass
# -> 3.27 ms ± 83.3 µs per loop (mean ± std. dev. of 10 runs, 100 loops each)
| 平均 | |
|---|---|
| 内側が短い | 4.23 ms |
| 内側が長い | 3.27 ms |
内側が長い方が速い結果になりました。
理由
理由については調べてもヒットしせず、あくまで筆者の推測なので、詳しい方がいましたら是非ご教授ください。
筆者の推測ですが、同じ回数のループ処理をする場合、内側が短いとその分だけ、外側から内側のfor文を一から組み立てる回数が増え、その結果処理が遅くなると思います。
以下追記(イメージ図）
irange = ['hoge'] * 10
jrange = ['hoge'] * 10000
for i in irange:
for j in jrange:
pass
のforループを展開したイメージは
for j in jrange:
pass
for j in jrange:
pass
for j in jrange:
pass
...(これが10個続く)
ということになり、10個のforループの生成で済むが
irange = ['hoge'] * 10000
jrange = ['hoge'] * 10
for i in irange:
for j in jrange:
pass
のforループを展開した際には
for j in jrange:
pass
for j in jrange:
pass
for j in jrange:
pass
for j in jrange:
pass
for j in jrange:
pass
for j in jrange:
pass
...(これが10000個続く)
というように、10000個のforループが生成される。
例外
@fujitanozomuさん、@tenmyoさん、コメントでのご指摘いただきありがとうございます。
2023/02/05時点でのPythonでは、-5~256の整数は、整数オブジェクトの配列を保持するようになっているため、毎回同じ参照先となります。
現在の実装では、-5 から 256 までの全ての整数に対する整数オブジェクトの配列を保持するようにしており、この範囲の数を生成すると、実際には既存のオブジェクトに対する参照が返るようになっています。(Python公式 https://docs.python.org/ja/3.8/c-api/long.html より引用)
一方、-5~256以外の整数は、毎回整数のオブジェクトを生成するため、遅くなります。例えば以下のループの場合、-5~256の整数を多く用いる内側が短いループが速くなる事があります。
%%timeit -r 10 -n 100
irange = range(10000)
jrange = range(10)
for i in irange:
for j in jrange:
pass
# -> 2.62 ms ± 119 µs per loop (mean ± std. dev. of 10 runs, 100 loops each)
%%timeit -r 10 -n 100
irange = range(10)
jrange = range(10000)
for i in irange:
for j in jrange:
pass
# -> 2.8 ms ± 81.7 µs per loop (mean ± std. dev. of 10 runs, 100 loops each)
まとめ
Pythonでネストしたfor文で順序を入れ替えても成り立つ場合は、内側にループ回数が多い方を書くと処理が速くなることを確認しました(例外あり)。
あくまで筆者の推測ですが、内側のループが少ないと、その文外側で多くループが入り、一回一回内側でfor文を作るのに処理時間がよりかかってしまっていると考えています。
何かと遅めのPythonですが、ネストに気をつけて快適にしていきましょう。