Pythonでx, yとかの2重ループをやめつつ，速度を考える


# はじめに
[Pythonでx, yとかの2重ループをやめたい](https://qiita.com/redshoga/items/ec09a91fcca3db80646e)より　
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倍ぐらい速い

```python:redshoga_original.py
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関数にしても同じになっていない

```python:redshoga_main.py
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の方が速くなっている！！

```python:SatoshiTerasaki_original
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]

```python:
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]

```python:w/o_list.py
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]

```python:w/o_list(main).py
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さんにもし不快な思いをさせてしまっていたら大変申し訳ありません．
許してくださいなんでもしますから！