LoginSignup
8

More than 5 years have passed since last update.

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

Posted at

はじめに

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倍ぐらい速い

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関数にしても同じになっていない

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の方が速くなっている!!

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]

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]

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]

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さんにもし不快な思いをさせてしまっていたら大変申し訳ありません.
許してくださいなんでもしますから!

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
8