Q&A
ご教授ありがとうございます。
本文に反映させました。
速度は少し改善できましたが、TLEはいまだ起こってしまっています。
他に何か方法はございますでしょうか？
処理速度が遅いために、みなさんにより処理速度の速い書き方を教わりたいと思い、相談いたします。
【やりたいこと】
・以下の数値を2個ずつ組み合わせることで、規定値（８）以上になるようにしたいと考えています。
**※なお、一度使った数値は、再使用することはできません。**この条件で、８以上となる組み合わせは最大何通りできるかを出力したいです。
[4 6 5 1 5 3]
上記数値の場合、
4 + 5 ＝9
6 + 3 ＝9
残っている数値：1と5 では、８以上とできないため、８以上となる組み合わせはこの場合、２通りとなります。
数値の組み合わせを変更して、
4 + 5 ＝9
5 + 3 ＝8
残っている数値：1と6 では、８以上とできないため、８以上となる組み合わせはこの場合も２通りとなります。
今回の数値では組み合わせをどう変更しても、２通りまでしかできないため、この場合、２通りを出力します。
上記を実現するため、私が書いた最初のコードです。
少ない数値なら問題なく動きましたが、今回扱う数値の数は、
・最大１０万個
・数値の幅は、1 ~ 1,000,000,000
となるため、現在のコードでは、TLEとなっております。
python
1high = 8 2li = [4,6,5,1,5,3] 3li = sorted(li) 4cou = 0 5for i in range(len(li)): 6 for j in range(i+1,len(li)): 7 if li[i] + li[j] >= high: 8 cou +=1 9 li[i] =0 10 li[j] =0 11 12print(cou)
TLEを避けるため、改良したコードが下記です。
※速度は少し改善しましたが、TLEはいまだにおきています。
「やったこと」
・一番高い値を足しても、規定値以上ならない低い値は、その時点で削除しておく。
・昇順ソートしてから、リストの値をひとつずつ比較しているのは前回と同じで、今回、規定値以上となる値を見つけた場所をベースに、
それより上の値がいくつあるのかを出して、その分をパターンに追加しています。そうすることにより、forの流れる回数を減らしている。
python
1high = 8 2li = [4,6,5,1,5,3] 3li = [i for i in li if i + max(li) >= high] # 一番高い数値を足しても、規定値を満たさない値は、事前に削除 4li = sorted(li) 5cou = 0 6while li: 7 flag = 0 # 1回でもtrueなら、繰り返す 8 end="" 9 cont="" 10 for i in range(len(li)): 11 for j in range(i+1,len(li)): 12 if li[i] + li[j] >= high: 13 flag =1 14 cou +=1 15 ind_max = len(li[j+1:]) #後ろにいくつあるか 16 ind_min = len(li[i+1:j]) 17 if ind_min == ind_max: #同じ数 18 cou += ind_max 19 end ="END" 20 break #終了 21 elif ind_min < ind_max: #大きい値のがおおい 22 cou += ind_min 23 cou += (ind_max - ind_min) // 2 24 end ="END" 25 break #終了 26 27 elif ind_min > ind_max: #小さい値のがおおい 28 cou += ind_max 29 li = li[i+1+ind_max:j] #リストの値を更新 30 cont = "True" 31 break 32 if end == "END": #終了 33 li=[] 34 break 35 elif cont =="True": 36 break #リストを更新して最初から繰り返す 37 if flag == 0: #forを最後まで流して、一回もtrueじゃなければ、規定値以上はもう作れない 38 li=[] 39 break 40print(cou)
解決したいこと、聞きたいこと。
上記ように処理を最大100,000回ほど繰り返す必要があるのですが、
上記のコードがボトルネックになっていて、処理速度がとても遅いです。
Pythonを使う前提で、上記のゴールを達成するできるだけ速いコードの書き方を提案してもらえないでしょうか。
どうぞよろしくお願いします。
【追記】
ご解答頂いた内容でコード作成しました。
速度は少し改善できました。ありがとうございます。
しかし、TLEはおきてしまっています。
python
1high = 8 2li = [4,6,5,1,5,3] 3li = [i for i in li if i + max(li) >= high] # 一番高い数値を足しても、規定値を満たさない値は、事前に削除 4li = sorted(li) 5cou = 0 6 7while li: 8 obj = 0 9 value = high - li[-1] #value値以上の最小を見つける 10 for line,i in enumerate(li): 11 if i >= value and line+1 < len(li): #後半の条件は、末尾でないということ 12 obj = li[line] #見つかった。 13 break 14 if obj == 0: #見つからなかった。 15 break 16 else: 17 cou +=1 18 del li[-1] 19 del li[:line+1] 20print(cou)
【再追記】
ご教授いただいた点を考慮。
コード再作成。
python
1high = 8 2li = [4,6,5,1,5,3] 3li = [i for i in li if i + max(li) >= high] # 一番高い数値を足しても、規定値を満たさない値は、事前に削除 4li = sorted(li) 5cou = 0 6ind_max = len(li)-1 7ind_min = 0 8 9while li: 10 obj = 0 11 value = high - li[ind_max] #value値以上の最小を見つける 12 for i in range(ind_min,ind_max): 13 if li[i] >= value : #見つかった。 14 obj = li[i] 15 break 16 if obj == 0: #見つからなかった。 17 break 18 else: #見つかった 19 cou +=1 20 ind_max -=1 21 ind_min = i +1 #リストの値を削除するのではなく、移動 22 23print(cou) 24
【コード完成】
python
1n,high = map(int,input().split()) 2li = list(map(int,input().split())) 3max_li = max(li) 4li = [i for i in li if i + max_li >= high] # 一番高い雪を足しても、高さが満たさない雪だまは削除 5li = sorted(li) 6cou = 0 7ind_max = len(li)-1 # 5 8ind_min = 0 9 10while li: 11 obj = 0 12 value = high - li[ind_max] #value値以上の最小を見つける 13 for i in range(ind_min,ind_max): 14 if li[i] >= value : #見つかった。 15 obj = li[i] 16 break 17 if obj == 0: #見つからなかった。 18 break 19 else: #見つかった 20 cou +=1 21 ind_max -=1 22 ind_min = i +1 23 24print(cou)
回答2件
0
ベストアンサー
なにも考えずline_profilerにかけました。
** tle_test.py**
python
1@profile 2def main(): 3 high = 8 4 li = [4,6,5,1,5,3] 5 li = [i for i in li if i + max(li) >= high] # 一番高い数値を足しても、規定値を満たさない値は、事前に削除 6 li = sorted(li) 7 cou = 0 8 ind_max = len(li)-1 9 ind_min = 0 10 11 while li: 12 obj = 0 13 value = high - li[ind_max] #value値以上の最小を見つける 14 for i in range(ind_min,ind_max): 15 if li[i] >= value : #見つかった。 16 obj = li[i] 17 break 18 if obj == 0: #見つからなかった。 19 break 20 else: #見つかった 21 cou +=1 22 ind_max -=1 23 ind_min = i +1 #リストの値を削除するのではなく、移動 24 25 # print(cou) 26 27if __name__ == "__main__": 28 for _ in range(50): 29 main()
$ kernprof -lv tle_test.py Wrote profile results to tle_test.py.lprof Timer unit: 1e-06 s Total time: 0.001542 s File: tle_test.py Function: main at line 1 Line # Hits Time Per Hit % Time Line Contents ============================================================== 1 @profile 2 def main(): 3 50 116.0 2.3 7.5 high = 8 4 50 34.0 0.7 2.2 li = [4,6,5,1,5,3] 5 50 276.0 5.5 17.9 li = [i for i in li if i + max(li) >= high] # 一番高い数値を足しても、規定値を満たさない値は、事前に削除 6 50 76.0 1.5 4.9 li = sorted(li) 7 50 28.0 0.6 1.8 cou = 0 8 50 38.0 0.8 2.5 ind_max = len(li)-1 9 50 29.0 0.6 1.9 ind_min = 0 10 11 150 84.0 0.6 5.4 while li: 12 150 80.0 0.5 5.2 obj = 0 13 150 111.0 0.7 7.2 value = high - li[ind_max] #value値以上の最小を見つける 14 150 162.0 1.1 10.5 for i in range(ind_min,ind_max): 15 100 70.0 0.7 4.5 if li[i] >= value : #見つかった。 16 100 61.0 0.6 4.0 obj = li[i] 17 100 59.0 0.6 3.8 break 18 150 109.0 0.7 7.1 if obj == 0: #見つからなかった。 19 50 28.0 0.6 1.8 break 20 else: #見つかった 21 100 62.0 0.6 4.0 cou +=1 22 100 60.0 0.6 3.9 ind_max -=1 23 100 59.0 0.6 3.8 ind_min = i +1 #リストの値を削除するのではなく、移動
もう少しでかいテストケース持ってこないとなんとも言えない面はあるのですが、とりあえずぱっと思いつく改善点。
- 5行目で内包表記の中に
max(li)を入れてますが、内包表記で一要素計算するごとに計算されますよ（恐ろしいことにこの行で17%消費している）。外でmax_liみたいな変数に代入して、内包表記の中ではそれを参照して比較するだけでだいぶマシになります - ソートする前に削除してからソートするのと、ソートしてから一回探索＆スライスで削除するのと、どっちが速いか検討してみました？
- whileの内側のforが遅いならバイナリサーチっぽいことをすると計算量は減るはず
投稿2018/09/19 09:25
総合スコア30933
0
残ってる数の中で一番大きな数は、必ず使うという特徴がありますね。
次のようにするとO(N)になりそうです。
- ソートする - while True: - 現在残っている中で最大の数（A）と、 それと組み合わせて条件を満たすことのできる最小の数（B）を 組み合わせとして計上する - もし存在しなければ break - 「A」および「B以下の数」を除外する
投稿2018/09/19 06:04
総合スコア2413
del li[:line+1] で O(n) の計算量がかかり、これを O(n) 回繰り返すので、全体として O(n*n) になってるっぽいです。
del ではなく、下限・上限の添字2つを動かす方式だと速くなると考えられます。
参考: https://qiita.com/Hironsan/items/68161ee16b1c9d7b25fb
ありがとうございます。
delではなく、リストの中を移動するよう組んでみました。
本文に反映しました。
しかしながら、まだ遅いということではじかれてしまう・。
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/09/19 09:51