python3における３重ループの書き換え

Question

python3 において
n = int(input())
count=0
if n>=3:
for i in range(1,n+1):
for j in range(i,n+1):
for k in range(j,n+1):
if k<i+j:
count+=1
else:
break
print(count)
else:
print(0)

と書いてみましたが、
python3はforループのネストが遅いとネットにでていたので
itertoolsを使って書き直したいのですが、range()において
jの初期値i, kの初期値j,を上手く表現できません。
どなたかご教示ください。

Comments

[mattn]

コードはコードブロックを使って書いて下さい。python の様にインデントが重要になる言語では正しく読み取れません。

[shinichi0326]

誠に申し訳ございません。夜中の質問だったのでコピペでよく確認もせずに質問してしまいました。以後気を付けます。

[mattn]

そもそもなのですが、オリジナルのコードの3重ループはやりたい内容の通りなのでしょうか？

[shinichi0326]

入力nに対して 1≦a≦b≦c≦n（a, b, c, nはすべて整数）を満たすa, b, cの中で、 これらを3辺とする三角形が成り立つ場合の組み合わせを求めるプログラムを書いてください。という問題に対する私の答えです。

[mattn]

なるほどあってそうですね。

Answer 1

for i in range(1,n+1):
    for j in range(i,n+1):
        for k in range(j,n+1):
            ...

の部分を

import itertools
for i,j,k in itertools.combinations_with_replacement(range(1,n+1), 3):
    ...

に置き換えることができます。

---

【追記】
上記でパフォーマンスがでないようですので・・改善案を書いておきます。

とりあえず　質問での３重ループの一番内側のループは、k<i+j が成り立つ k をカウントしているだけですので、この部分をループではなく計算で求めるようにするとループの回数を大幅に少なくすることができます。

n = 1000
count = 0
for i in range(1,n+1):
    for j in range(i,n+1):
        count += min(i,n-j+1)
print(count)

内包表記だとこんなかんじ

n = 1000
ret = sum([min(i,n-j+1) for i in range(1,n+1) for j in range(i,n+1) ])

Comments

[shinichi0326]

nの値を1000などに大きくすると、for でも itertools.combinations_with_replacement でも
タイムアウトしてしまうのですが、何か対策ご教示頂けないでしょうか。

[pashango2]

1000の3重ループは1000の3乗の10億回のループです、処理の内容によりますが、非常に時間がかかると思います。
誰がどような理由でマイナスが付いたかわかりませんが、この回答にマイナス評価が付く理由が見当たりません。

[magichan]

> shinichi0326さん
こちらでも確認してみましたが、iteratoolsを使うほうが逆に遅くなりますね。
たぶん break を使えない分だけループ回数が増えるのが原因かと思います。
一応内包表記でも確認しましたが結果は同様で、３重ループの方が早いという結果となりました。
たぶん根本的にアルゴリズムを変える必要があるのではないでしょうか。

[magichan]

> pashango2さん
ありがとうございます。itertoolsにて
・ i,j,k がソート済みである
という前提で記述しているのですが、その部分に私が仕様的に勘違いをしている部分があるかもしれないと疑っていたところです。（理由が明示されていないのでよくわからないのですが）
それともよいパフォーマンスが得られないことがマイナスの要因なのでしょうかね？

[magichan]

代替となるアルゴリズム案を追記しました。

[shinichi0326]

magichanさん、解答大変ありがとうございます。
for j in range(i,n+1):
count += min(i,n-j+1)
の所、大変勉強になりました。
しかし、問題では最大n=1000000となっており解答のコードでもタイムアウトになってしまいます。
根本的にアルゴリズムを変えなくてはならないのでしょうか？
何かヒントでも良いので、ご教示いただければ幸いです。

[magichan]

> 根本的にアルゴリズムを変えなくてはならないのでしょうか？
たぶんそうでしょうね。 n=1000000 の時点で２重ループは無いと思います。

> 何かヒントでも良いので

私はコードから設問を推測しているだけなので、勘違いがあったらスミマセンが、
例えば、 n = 5 の時に i,j に対する k<i+j が成り立つ数を表にすると

1 1 1 1 1
X 2 2 2 1
X X 3 2 1
X X X 2 1
X X X X 1

n = 6 の時は

1 1 1 1 1 1
X 2 2 2 2 1
X X 3 3 2 1
X X X 3 2 1
X X X X 2 1
X X X X X 1

となりますので、これより何かしらの規則性を見つけると良いと思います。

たとえば

1 の数が (n*2-1) 個
2 の数が (n*2-1) - 4 個
3 の数が (n*2-1) - 8 個
…

に注目すると

n = 1000000
count = 0
for i,n in enumerate(range(n*2-1,0,-4)):
__count += (i+1)*n
print(count)

のような２重ループを使わないコードが得られます。

[shinichi0326]

magichanさん、解答大変ありがとうございます。
問題が解決しました。タイムアウトにはなりませんでした。
世の中には本当に頭の良い人がいるもんですね‼
凡人の私にはループで回すくらいしか思いつきませんでした。
大変勉強になりました。
また何か解らないことがありましたら、ご教示ください。

Answer 2

Python のコードを速くするには、とにかく実行する「Pythonの文」を少なくする。
アルゴリズム的に、ループの回数を小さくする、です。

from datetime import datetime

start = datetime.now()
n = 1000
count=0
for i in range(1,n+1):
  for j in range(i,n+1):
    for k in range(j,n+1):
      if k<i+j:
        count+=1
      else:
        break
print(count)
print(datetime.now() - start)  # かかった時間

に対して

from datetime import datetime
import itertools

start = datetime.now()
n = 1000
count=0

for i,j,k in itertools.combinations_with_replacement(range(1,n+1), 3):
  count+=1
print(count)
print(datetime.now() - start)

は最後の k のループの範囲が問題で、 i+jと等しくなった時に、 k に関するループを抜ければ済むはずなのにそれができない点です。
その分だけ余計にループを回さないといけません。

n=1000の場合で、手元のマシンだと25%ほど遅くなります。
n=1500にすると、ループが増える割合が大きくなって、50%ほど遅くなります。

「ループの回数」の増加分が、「Pythonの文」が減少分に対して見合ってないのです。そして n が大きくなればなるほどその傾向が大きくなります。

最初のコードで、無駄な部分は if k<i+j: の部分です。 k が i+j に到達したらループを抜けるのですから、これはループの範囲として書いてしまえばいいです。

from datetime import datetime

start = datetime.now()
n = 1000
count=0
for i in range(1,n+1):
  for j in range(i,n+1):
    for k in range(j, min(n+1, i+j)):
      count+=1
print(count)
print(datetime.now() - start)

n か i+j-1 のうち小さい方までループすればいいのでこう書けます。
これで if k<i+j: や break の実行が無くなるので、実行時間は半分ぐらいです。

そして、Python3系では、forループは十分に速くなっていて、メモリを使わずに書こうとした場合は、これが一番よいと思っています。（もっと良い解が出てくると私も嬉しいです）

---

実はメモリを潤沢に使っていいなら、内包表記でリストを生成して長さを調べるのが最速です。リストの中身は何でもいいです。

from datetime import datetime

start = datetime.now()
n = 1000
print(len([1 for i in range(1,n+1) for j in range(i,n+1) for k in range(j, min(n+1, i+j))]))
print(datetime.now() - start)

これは上のソースの半分ぐらい。最初のソースの1/4ぐらいです。

ただしメモリは使います。n=1000で600MB、n=1500で2.5GBぐらい使います。

ループが大きくなるなら現実的ではないかもしれませんが、ループの回数の上限がしっかり分かっているなら、往々にして「リストを作ってしまう」のがPyhtonでは最速だったりします。

Comments

[shinichi0326]

quiquiさん、大変解りやすく解説ありがとうございます。
for k in range(j, min(n+1, i+j))　の部分私には解りませんでした。
下の回答に更にパフォーマンスをあげる方法が載っていますので、自分の未熟さを痛感します。
しかし、問題の条件として最大n=1000000となっており下の回答でもパフォーマンスが足りません。
誠に申し訳ないのですがn=1000000でもタイムアウトにならない方法はないものでしょうか？

[quickquip]

> n=1000000でもタイムアウトにならない方法はないものでしょうか？
それが求められているなら考えるべき解法の質が違います。

今やっている方法は例えるなら、1〜1000000までの総和を求めなさい、という問題があって1〜1000000までをループして和を取っていく、というようなものです。
それに対して求められているのは 1000000×(1000000+1)/2 を計算する、みたいな解法でしょう。

そもそも、ループを使ってどうにかする、と考えてはいけない問題でしょう。

> for k in range(j, min(n+1, i+j))　の部分
for i in range(100):
..if i<50:
....何かする
..else
....break

というループを考えてみてください。100未満の範囲でループしろとforに書いてますが、一方で if 文で50に等しくなったらループを抜けろ、とも書いてあります。これなら最初から
for i in range(50):
..何かする
でいいですよね?

質問のkのループもそのようになっていて、n 以下の範囲でループしろ、i+j に等しくなったらループを抜けろって書いてあるのですから
for k in range(1, 《n+1 か i+jのどっちか小さい方》):
でいいわけです。

[shinichi0326]

quiquiさん、大変厳しいご指摘ありがとうございます。
quiquiさんのおっしゃる通り、自分で条件を書いておきながら効率の良いコードを書けていませんでした。
以後気を付けます。プログラミングは奥が深いですね。
この問題は何か公式みたいなものを使って解くしかないのですかね？
大変勉強になりました。

[quickquip]

ああ、すみません。すごく断言した口調で書いてしまいましたが、n=1000000 という問題であればこうだろう、と直感的に判断した印象論です。

2重ループさせる解ではありえない、という確信はあります。

純粋に数学的な解があるとは限りません。直感ではそこまでは分かりません。
しかし、ループが1回で済む解ではあるはずだ、と思います。でなければ秒のオーダーでは解けません。