質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
for

for文は、様々なプログラミング言語で使われている制御構造です。for文に定義している条件から外れるまで、for文内の命令文を繰り返し実行します。

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

4回答

5777閲覧

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

kay_ventris4

総合スコア269

for

for文は、様々なプログラミング言語で使われている制御構造です。for文に定義している条件から外れるまで、for文内の命令文を繰り返し実行します。

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

1グッド

1クリップ

投稿2021/04/22 08:58

編集2021/04/22 09:02

#問題
イメージ説明
AtCoder ABC162 C問題より

#時間切れコード

Python

1from math import gcd 2from itertools import product 3 4K = int(input()) 5 6ans = 0 7for x in list(product(range(1, K + 1), repeat = 3)): 8 ans += gcd(gcd(x[0], x[1]), x[2]) 9 10print(ans)

#正解コード

Python

1from math import gcd 2from itertools import product 3 4K = int(input()) 5 6ans = 0 7for i in range(1, K + 1): 8 for j in range(1, K + 1): 9 for k in range(1, K + 1): 10 ans += gcd(gcd(i, j), k) 11 12print(ans)

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

gottadiveintopy👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答4

0

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

遅くなる要因としては、

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

などがあり得ます。

python

1from math import gcd 2from itertools import product 3 4 5def f0(K): 6 ans = 0 7 for i in range(1, K + 1): 8 for j in range(1, K + 1): 9 for k in range(1, K + 1): 10 ans += gcd(gcd(i, j), k) 11 12def f1(K): 13 ans = 0 14 for i in range(1, K + 1): 15 for j in range(1, K + 1): 16 for k in range(1, K + 1): 17 pass 18 19def f2(K): 20 ans = 0 21 for x, y, z in product(range(1, K + 1), repeat = 3): 22 ans += gcd(gcd(x, y), z) 23 24def f3(K): 25 ans = 0 26 for x, y, z in product(range(1, K + 1), repeat = 3): 27 pass

python

1%%timeit 2f0(170) 3 41.18 s ± 10.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 5 6%%timeit 7f1(170) 8 952.6 ms ± 326 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 10 11%%timeit 12f2(170) 13 141.24 s ± 7.44 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 15 16%%timeit 17f3(170) 18 19114 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はそういう言語です。

投稿2021/04/22 10:56

hayataka2049

総合スコア30933

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

Pythonのコードを書いていて、
productを使う場面

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

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

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


(追記)

python

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

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

投稿2021/04/22 09:21

編集2021/04/22 09:29
quickquip

総合スコア11029

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

quickquip

2021/04/22 09:24

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

2021/04/22 09:29

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

2021/04/22 09:33

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

2021/04/22 09:52

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

0

ベストアンサー

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回で済むので、正解コードより速くなります。

python

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

投稿2021/04/22 09:14

編集2021/04/22 09:57
ppaul

総合スコア24666

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kay_ventris4

2021/04/22 09:27

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

2021/04/22 09:57

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

2021/04/22 10:29

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

0

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

投稿2021/04/22 09:05

hide5stm

総合スコア426

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kay_ventris4

2021/04/22 09:10 編集

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

2021/04/22 09:19 編集

それならば、x[]の添字アクセスが不利になっていそうです。 以下の書き方だとどうでしょうか ```python for x, y, z in product(range(1, K + 1), repeat = 3): ans += gcd(gcd(x, y), z) ```
kay_ventris4

2021/04/22 09:31

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

2021/04/22 10:06

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

2021/04/22 23:48

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問