itertools.productは何故for文より遅いのか?

Question

#問題

AtCoder ABC162 C問題より

#時間切れコード

from math import gcd
from itertools import product

K = int(input())

ans = 0
for x in list(product(range(1, K + 1), repeat = 3)):
	ans += gcd(gcd(x[0], x[1]), x[2])

print(ans)

#正解コード

from math import gcd
from itertools import product

K = int(input())

ans = 0
for i in range(1, K + 1):
	for j in range(1, K + 1):
		for k in range(1, K + 1):
			ans += gcd(gcd(i, j), k)

print(ans)

#質問
よくitertools.productは「多重ループを回避する」などと謳われているのを目にしてきましたが、このような場合どうしてfor文を用いた三重ループの方が計算量が小さく済んだのでしょうか？（実際は同じことをやっているようにしか見えないのですが…）　また、このケースだけでなく一般に多重ループをitertools.productを用いるよりfor文で愚直に書いた方が計算処理が少なく済むのだとしたら、itertools.productを使う旨味とは一体何なのでしょうか？（コードの見やすさというのは当然あると思いますが）　曖昧かつ漠然とした疑問ゆえ上手く得たい情報に行きつけず、素人質問にて恐縮ですが、簡単にご教授頂きたく存じます。よろしくお願い致します。

Answer 1

itertools.productは何故for文より遅いのか?

遅くなる要因としては、

• どのみち内部ではforループ相当のことをしている（はず）
• tupleをK^3回生成して、さらに要素参照orアンパックをこなさないといけない

などがあり得ます。

from math import gcd
from itertools import product


def f0(K):
    ans = 0
    for i in range(1, K + 1):
        for j in range(1, K + 1):
            for k in range(1, K + 1):
                ans += gcd(gcd(i, j), k)

def f1(K):
    ans = 0
    for i in range(1, K + 1):
        for j in range(1, K + 1):
            for k in range(1, K + 1):
                pass

def f2(K):
    ans = 0
    for x, y, z in product(range(1, K + 1), repeat = 3):
        ans += gcd(gcd(x, y), z)

def f3(K):
    ans = 0
    for x, y, z in product(range(1, K + 1), repeat = 3):
        pass

%%timeit
f0(170)

1.18 s ± 10.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%%timeit
f1(170)

52.6 ms ± 326 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%%timeit
f2(170)

1.24 s ± 7.44 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%%timeit
f3(170)

114 ms ± 835 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

K=170（適当に選んだだけ）ではループだけでも60 ms遅いので、不利といえば不利です。ただし今回の場合、全体の所要時間からすると誤差ですけど。

---

itertools.productを使う旨味

170^3なので、ラフに500万回弱ループして60 msというところに注目です。

事実上無視できるので、見やすさ優先で使います。

逆に、これが無視できないシチュエーションでは、アルゴリズムを見直すとか、実装も生Pythonを使わないでnumpyとかcythonとかnumbaとかC拡張とか……を持ち出すとか、そういうことをします。Pythonはそういう言語です。

Answer 2

Pythonのコードを書いていて、
productを使う場面
と
forループを使う場面
のどっちが多いかと言われれば間違いなく後者なので、Pythonの処理系を開発している人が高速化に多くの時間を掛けるべきと判断するのは当然後者でしょう。

Python2のころは事情が違っていて、forループは遅い、内包表記やmap関数やitertoolsを使え、と言われていました。
Python3の開発で（おそらくは開発者の方がめちゃくちゃがんばって）forループの処理の最適化がなされて、今は愚直にforループを書くのがだいたいにおいて一番速いことが多いです。

https://teratail.com/questions/330753#reply-457116 あたりも。

---

(追記)

ans = 0
for x, y, z in product(range(1, K + 1), repeat = 3):
    ans += gcd(gcd(x, y), z)

が3重forループとほぼ同様になりませんか。

Comments

[quickquip]

時間切れそのものはlistにするのにメモリ確保が必要になる点での違いだとは思います。

[kay_ventris4]

itertoolsはcombinationやpermutationなど使い所も多いものですが、forループで置き換えられるところは置き換えた方が良いんですね。とても勉強になりました。ありがとうございます。

[kay_ventris4]

追記返信）hide5stmさんの方でもご教授頂きましたが、list()を除きタプルへのアクセスをやめる方針でトライし、2226msから2161msまで削減できましたが、目標の2000msには届かずギリギリTLEでした。

[quickquip]

同じ内容がありましたね。失礼しました。
愚直に書くと、K=200が絶妙なラインにあるんですね。

Answer 3

1 hide5stmさんが書かれているように、listは必要ありません。

リストを作成した上に、それを順番にxに入れるためにさらに時間が増えます。

2 正解コードでは、gcd(i, j)の計算がK2回で済んでいるのに、時間切れコードではそれにあたる計算がK3回必要になっています。

3 正解コードでは、i,j,k をそのまま使えますが、時間切れコードではx[0],x[1],x[2]とタプルの要素アクセスになって時間がかかっています。

変更です。

以下のコードだと、gcd(i, j)の計算がK^2回で済むので、正解コードより速くなります。

for i in range(1, K + 1):
    for j in range(1, K + 1):
        gcd_ij = gcd(i, j)
        for k in range(1, K + 1):
            ans += gcd(gcd_ij, k)

Comments

[kay_ventris4]

ご返信ありがとうございます。
1,3の説明は理解したのですが、2の「時間切れコードではそれにあたる計算がK^3回必要になっています」という部分が理解できません。x[0]とx[1]のgcdの組み合わせのK^2回分とあともうK回分というのはどの部分のことなのでしょうか？

[ppaul]

ありゃ、間違っていましたね。
これを改善すると、もっと速くなるというパターンでした。
面白いので、回答に追加しておきます。

[kay_ventris4]

とてもスッキリしました。修正のほどありがとうございます。

Answer 4

productの外側のlist()を無くすとどうでしょうか。計算結果には影響せず性能向上するかもしれません。
このlist()は、productの全結果分のメモリを確保しに行くはずなので、
組合せが大きくなると、ループより、メモリ確保に時間がかかって時間切れになるということがあるかもしれません。

Comments

[kay_ventris4]

ご返信ありがとうございます。
早速試した結果、処理時間は2226msから2206msとなり、制限時間の2000msを切ることはできず、改善こそしたものの大きな成果は得られませんでした。

[hide5stm]

それならば、x[]の添字アクセスが不利になっていそうです。
以下の書き方だとどうでしょうか

```python
for x, y, z in product(range(1, K + 1), repeat = 3):
ans += gcd(gcd(x, y), z)
```

[kay_ventris4]

2161msまで削減出来ました。後はおそらくppaulさんの仰るgcdの箇所で余計にK回分多くループがかかっているところの修正でAC出来そうです。細かくご指導頂きありがとうございました。

[ppaul]

or x, y, z in product(range(1, K + 1), repeat = 3):
ans += gcd(gcd(x, y), z)

と書くよりは、

for x in product(range(1, K + 1), repeat = 3):
ans += gcd(*x)

方が少し速いはずです。

[quickquip]

私も書こうと思ってやめたんですが、gcd(*x)は3.9以降なのでAtCoderでは使えないです。