はじめに
Pythonでx, yとかの2重ループをやめたいより
itertoolsの方が速度が遅いらしいが,もう少し細かく検証
また,コメントによるとmain関数に入れると同じ速度になるらしいのが気になったので
検証方法
2重ループのアルゴリズム使っている以上,計算量としてはO(N^2)であることは変わらないので,
2重ループの回数を増やしても時間の差はN^2で離れていくだけのはず.
なので2重ループの回数はある程度差が見れる1000回で固定.
redshoga Method
- ループ内の処理はpass
- 2重ループ回数は(x, y)共に1000
- 時間の取得は2重ループ直前と直後
- 100回繰り返した時間平均をとる
結論
下の方は回しているだけなので,先に結論だけ
Code | nest[s] | iter[s] |
---|---|---|
Original(直書き) | 0.0277 | 0.0593 |
Original(main関数) | 0.0110 | 0.0254 |
SatoshiTerasaki_original (直書き) | 0.0285 | 0.0290 |
SatoshiTerasaki_original(main関数) | 0.0296 | 0.0282 |
w/o list(直書き) | 0.0435 | 0.0617 |
w/o list(main関数) | 0.0270 | 0.0275 |
おそらくitertoolsを使うから遅くなるわけではなく,for loopでrangeをそのまま入れるよりもlistにすることで速くなっているという印象
オリジナル
nest: 0.02772940158843994[sec]
iter: 0.059307749271392825[sec]
nestの方が2倍ぐらい速い
import itertools
import time
import numpy as np
cycle = 100
iter = []
nest = []
for i in range(cycle):
x_list = list(range(1000))
y_list = list(range(1000))
product = itertools.product(x_list, y_list)
start_time = time.time()
for x, y in product:
pass
end_time = time.time()
iter.append(end_time-start_time)
start_time = time.time()
for x in x_list:
for y in y_list:
pass
end_time = time.time()
nest.append(end_time-start_time)
print("nest: {}[sec]".format(np.average(nest)))
print("iter: {}[sec]".format(np.average(iter)))
main関数へ入れる
nest[main]: 0.011095919609069825[sec]
iter[main]: 0.025424113273620607[sec]
どっちも2倍程度速くなってるが,iterの方が2倍くらい速いのは変わらず
main関数にしても同じになっていない
import itertools
import time
import numpy as np
cycle = 100
def main():
iter = []
nest = []
for i in range(cycle):
x_list = list(range(1000))
y_list = list(range(1000))
product = itertools.product(x_list, y_list)
start_time = time.time()
for x, y in product:
pass
end_time = time.time()
iter.append(end_time-start_time)
start_time = time.time()
for x in x_list:
for y in y_list:
pass
end_time = time.time()
nest.append(end_time-start_time)
print("nest[main]: {}[sec]".format(np.average(nest)))
print("iter[main]: {}[sec]".format(np.average(iter)))
if __name__ == '__main__':
main()
SatoshiTerasaki-method
コメントにあったmain関数に入れた場合の比較
条件だけredshoga Methodにして
nest: 0.029633991718292237 [sec]
iter: 0.02820287466049194 [sec]
逆にitertoolsの方が速くなっている!!
import time
import itertools
def naive(N):
s = 0
start_time = time.time()
for i in range(N):
for j in range(N):
pass
end_time = time.time()
return s, end_time - start_time
def product(N):
s = 0
start_time = time.time()
for i, j in itertools.product(range(N), repeat=2):
pass
end_time = time.time()
return s, end_time - start_time
def main():
N = 1000
n_trial = 100
naive_times = []
product_times = []
for _ in range(n_trial):
naive_s, naive_elapsed = naive(N)
prodcut_s, prodcut_elapsed = product(N)
assert naive_s == prodcut_s
naive_times.append(naive_elapsed)
product_times.append(prodcut_elapsed)
print(sum(naive_times) / n_trial)
print(sum(product_times) / n_trial)
if __name__ == '__main__':
main()
SatoshiTerasaki-method(w/o main関数)
先ほどのコードをmain関数でない場合と比較
結果は先ほどと同じでmain関数であるかどうかはおそらく関係ない
nest: 0.028573617935180665 [sec]
iter: 0.029031195640563966 [sec]
import time
import itertools
def naive(N):
s = 0
start_time = time.time()
for i in range(N):
for j in range(N):
pass
end_time = time.time()
return s, end_time - start_time
def product(N):
s = 0
start_time = time.time()
for i, j in itertools.product(range(N), repeat=2):
pass
end_time = time.time()
return s, end_time - start_time
N = 1000
n_trial = 100
naive_times = []
product_times = []
for _ in range(n_trial):
naive_s, naive_elapsed = naive(N)
prodcut_s, prodcut_elapsed = product(N)
assert naive_s == prodcut_s
naive_times.append(naive_elapsed)
product_times.append(prodcut_elapsed)
print(sum(naive_times) / n_trial)
print(sum(product_times) / n_trial)
考察
2人のコードの差を考えてみるとループ処理に入れている変数をlistに直しているかどうか
この差が効いていると考えられる.
redshoga W/O list (直書き)
nest: 0.043598706722259524[sec]
iter: 0.061788241863250735[sec]
import itertools
import time
import numpy as np
cycle = 100
iter = []
nest = []
for i in range(cycle):
x_list = range(1000)
y_list = range(1000)
product = itertools.product(x_list, y_list)
start_time = time.time()
for x, y in product:
pass
end_time = time.time()
iter.append(end_time-start_time)
start_time = time.time()
for x in x_list:
for y in y_list:
pass
end_time = time.time()
nest.append(end_time-start_time)
print("nest: {}[sec]".format(np.average(nest)))
print("iter: {}[sec]".format(np.average(iter)))
redshoga W/O list (メイン)
nest[main]: 0.027052536010742187[sec]
iter[main]: 0.0275067138671875[sec]
import itertools
import time
import numpy as np
cycle = 100
def main():
iter = []
nest = []
for i in range(cycle):
x_list = range(1000)
y_list = range(1000)
product = itertools.product(x_list, y_list)
start_time = time.time()
for x, y in product:
pass
end_time = time.time()
iter.append(end_time-start_time)
start_time = time.time()
for x in x_list:
for y in y_list:
pass
end_time = time.time()
nest.append(end_time-start_time)
print("nest[main]: {}[sec]".format(np.average(nest)))
print("iter[main]: {}[sec]".format(np.average(iter)))
if __name__ == '__main__':
main()
今回の測定環境
Macbook Pro Retina 13inc 2015
core i7 3.1GHz
RAM 16GB
python3.7
numpy 1.15.2 (w/o mkl)
最後に
クソ記事書いてすみません!
また,redshogaさん,SatoshiTerasakiさんにもし不快な思いをさせてしまっていたら大変申し訳ありません.
許してくださいなんでもしますから!