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

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

ただいまの
回答率

90.49%

  • Python 3.x

    9761questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

複数ある数値を2個ずつ比較して、規定値以上となる値が何パターンあるのか出力したい。ただし、現状のコードが遅いため、速くしたいです。

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 405

zeitaku_fire

score 18

処理速度が遅いために、みなさんにより処理速度の速い書き方を教わりたいと思い、相談いたします。

【やりたいこと】
・以下の数値を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ページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+3

なにも考えず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が遅いならバイナリサーチっぽいことをすると計算量は減るはず

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/09/19 18:51

    ありがとうございます。
    >5行目で内包表記の中にmax(li)を入れてますが、内包表記で一要素計算するごとに計算されますよ・・・
    こちらが主な原因となっていたようでした。
    修正したところ、無事に動きました。

    timeを用いて、処理にかかる時間を見ていたのですが、実行結果が9.8454・・のときもあれば、0.0000125とまばらだったので、どのコードが遅くなっている原因なのかつきとめられずにおりました。
    今回、はじめてprofileということおよび実行結果についても教えて頂き、大変参考になりました。
    今後、profileを活用して、ボトルネックを自身で見つけるよう精進してまいります。
    ありがとうございました。

    キャンセル

+3

残ってる数の中で一番大きな数は、必ず使うという特徴がありますね。
次のようにするとO(N)になりそうです。

- ソートする
- while True:
    - 現在残っている中で最大の数(A)と、
      それと組み合わせて条件を満たすことのできる最小の数(B)を
      組み合わせとして計上する
        - もし存在しなければ break
    - 「A」および「B以下の数」を除外する

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/09/19 16:13

    ご教授ありがとうございます。
    本文に反映させました。
    速度は少し改善できましたが、TLEはいまだ起こってしまっています。
    他に何か方法はございますでしょうか?

    キャンセル

  • 2018/09/19 16:56 編集

    del li[:line+1] で O(n) の計算量がかかり、これを O(n) 回繰り返すので、全体として O(n*n) になってるっぽいです。
    del ではなく、下限・上限の添字2つを動かす方式だと速くなると考えられます。
    参考: https://qiita.com/Hironsan/items/68161ee16b1c9d7b25fb

    キャンセル

  • 2018/09/19 17:58 編集

    ありがとうございます。
    delではなく、リストの中を移動するよう組んでみました。
    本文に反映しました。
    しかしながら、まだ遅いということではじかれてしまう・。

    キャンセル

同じタグがついた質問を見る

  • Python 3.x

    9761questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • トップ
  • Python 3.xに関する質問
  • 複数ある数値を2個ずつ比較して、規定値以上となる値が何パターンあるのか出力したい。ただし、現状のコードが遅いため、速くしたいです。