複数ある数値を2個ずつ比較して、規定値以上となる値が何パターンあるのか出力したい。ただし、現状のコードが遅いため、速くしたいです。
- 評価
- クリップ 0
- VIEW 853
処理速度が遅いために、みなさんにより処理速度の速い書き方を教わりたいと思い、相談いたします。
【やりたいこと】
・以下の数値を2個ずつ組み合わせることで、規定値(8)以上になるようにしたいと考えています。
※なお、一度使った数値は、再使用することはできません。この条件で、8以上となる組み合わせは最大何通りできるかを出力したいです。
[4 6 5 1 5 3]
上記数値の場合、
4 + 5 =9
6 + 3 =9
残っている数値:1と5 では、8以上とできないため、8以上となる組み合わせはこの場合、2通りとなります。
数値の組み合わせを変更して、
4 + 5 =9
5 + 3 =8
残っている数値:1と6 では、8以上とできないため、8以上となる組み合わせはこの場合も2通りとなります。
今回の数値では組み合わせをどう変更しても、2通りまでしかできないため、この場合、2通りを出力します。
上記を実現するため、私が書いた最初のコードです。
少ない数値なら問題なく動きましたが、今回扱う数値の数は、
・最大10万個
・数値の幅は、1 ~ 1,000,000,000
となるため、現在のコードでは、TLEとなっております。
high = 8
li = [4,6,5,1,5,3]
li = sorted(li)
cou = 0
for i in range(len(li)):
for j in range(i+1,len(li)):
if li[i] + li[j] >= high:
cou +=1
li[i] =0
li[j] =0
print(cou)
TLEを避けるため、改良したコードが下記です。
※速度は少し改善しましたが、TLEはいまだにおきています。
「やったこと」
・一番高い値を足しても、規定値以上ならない低い値は、その時点で削除しておく。
・昇順ソートしてから、リストの値をひとつずつ比較しているのは前回と同じで、今回、規定値以上となる値を見つけた場所をベースに、
それより上の値がいくつあるのかを出して、その分をパターンに追加しています。そうすることにより、forの流れる回数を減らしている。
high = 8
li = [4,6,5,1,5,3]
li = [i for i in li if i + max(li) >= high] # 一番高い数値を足しても、規定値を満たさない値は、事前に削除
li = sorted(li)
cou = 0
while li:
flag = 0 # 1回でもtrueなら、繰り返す
end=""
cont=""
for i in range(len(li)):
for j in range(i+1,len(li)):
if li[i] + li[j] >= high:
flag =1
cou +=1
ind_max = len(li[j+1:]) #後ろにいくつあるか
ind_min = len(li[i+1:j])
if ind_min == ind_max: #同じ数
cou += ind_max
end ="END"
break #終了
elif ind_min < ind_max: #大きい値のがおおい
cou += ind_min
cou += (ind_max - ind_min) // 2
end ="END"
break #終了
elif ind_min > ind_max: #小さい値のがおおい
cou += ind_max
li = li[i+1+ind_max:j] #リストの値を更新
cont = "True"
break
if end == "END": #終了
li=[]
break
elif cont =="True":
break #リストを更新して最初から繰り返す
if flag == 0: #forを最後まで流して、一回もtrueじゃなければ、規定値以上はもう作れない
li=[]
break
print(cou)
解決したいこと、聞きたいこと。
上記ように処理を最大100,000回ほど繰り返す必要があるのですが、
上記のコードがボトルネックになっていて、処理速度がとても遅いです。
Pythonを使う前提で、上記のゴールを達成するできるだけ速いコードの書き方を提案してもらえないでしょうか。
どうぞよろしくお願いします。
【追記】
ご解答頂いた内容でコード作成しました。
速度は少し改善できました。ありがとうございます。
しかし、TLEはおきてしまっています。
high = 8
li = [4,6,5,1,5,3]
li = [i for i in li if i + max(li) >= high] # 一番高い数値を足しても、規定値を満たさない値は、事前に削除
li = sorted(li)
cou = 0
while li:
obj = 0
value = high - li[-1] #value値以上の最小を見つける
for line,i in enumerate(li):
if i >= value and line+1 < len(li): #後半の条件は、末尾でないということ
obj = li[line] #見つかった。
break
if obj == 0: #見つからなかった。
break
else:
cou +=1
del li[-1]
del li[:line+1]
print(cou)
【再追記】
ご教授いただいた点を考慮。
コード再作成。
high = 8
li = [4,6,5,1,5,3]
li = [i for i in li if i + max(li) >= high] # 一番高い数値を足しても、規定値を満たさない値は、事前に削除
li = sorted(li)
cou = 0
ind_max = len(li)-1
ind_min = 0
while li:
obj = 0
value = high - li[ind_max] #value値以上の最小を見つける
for i in range(ind_min,ind_max):
if li[i] >= value : #見つかった。
obj = li[i]
break
if obj == 0: #見つからなかった。
break
else: #見つかった
cou +=1
ind_max -=1
ind_min = i +1 #リストの値を削除するのではなく、移動
print(cou)
【コード完成】
n,high = map(int,input().split())
li = list(map(int,input().split()))
max_li = max(li)
li = [i for i in li if i + max_li >= high] # 一番高い雪を足しても、高さが満たさない雪だまは削除
li = sorted(li)
cou = 0
ind_max = len(li)-1 # 5
ind_min = 0
while li:
obj = 0
value = high - li[ind_max] #value値以上の最小を見つける
for i in range(ind_min,ind_max):
if li[i] >= value : #見つかった。
obj = li[i]
break
if obj == 0: #見つからなかった。
break
else: #見つかった
cou +=1
ind_max -=1
ind_min = i +1
print(cou)
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
checkベストアンサー
+4
なにも考えずline_profilerにかけました。
tle_test.py
@profile
def main():
high = 8
li = [4,6,5,1,5,3]
li = [i for i in li if i + max(li) >= high] # 一番高い数値を足しても、規定値を満たさない値は、事前に削除
li = sorted(li)
cou = 0
ind_max = len(li)-1
ind_min = 0
while li:
obj = 0
value = high - li[ind_max] #value値以上の最小を見つける
for i in range(ind_min,ind_max):
if li[i] >= value : #見つかった。
obj = li[i]
break
if obj == 0: #見つからなかった。
break
else: #見つかった
cou +=1
ind_max -=1
ind_min = i +1 #リストの値を削除するのではなく、移動
# print(cou)
if __name__ == "__main__":
for _ in range(50):
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が遅いならバイナリサーチっぽいことをすると計算量は減るはず
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+4
残ってる数の中で一番大きな数は、必ず使うという特徴がありますね。
次のようにするとO(N)になりそうです。
- ソートする
- while True:
- 現在残っている中で最大の数(A)と、
それと組み合わせて条件を満たすことのできる最小の数(B)を
組み合わせとして計上する
- もし存在しなければ break
- 「A」および「B以下の数」を除外する
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう!
- ただいまの回答率 89.96%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
2018/09/19 18:51
>5行目で内包表記の中にmax(li)を入れてますが、内包表記で一要素計算するごとに計算されますよ・・・
こちらが主な原因となっていたようでした。
修正したところ、無事に動きました。
timeを用いて、処理にかかる時間を見ていたのですが、実行結果が9.8454・・のときもあれば、0.0000125とまばらだったので、どのコードが遅くなっている原因なのかつきとめられずにおりました。
今回、はじめてprofileということおよび実行結果についても教えて頂き、大変参考になりました。
今後、profileを活用して、ボトルネックを自身で見つけるよう精進してまいります。
ありがとうございました。