Python3のコードをもっと早く走らせたい。改善案お教えください。

Question

某サイトの問題です。ただし、問題そのものを載せてしまうと規定に違反するので詳細は伏せます。

下記コードで目的の結果は得られています。しかし、実際にコードを走らせると時間切れになってしまいます。
どの部分が遅くなっている原因でしょうか？
どうすれば早くなりますか？お教えください。

mono=[[300, 3], [140, 5], [200, 5]]
a = ['ok 1 1 1', 'ok 3 4 0', 'no 1 1 1', 'ok 3 4 0', 'ok 0 0 2', 'add 1 0 0']
for i in range(6):
    aa=a[i].split()
    if aa[0]=='ok':
        aa=aa[1:]
        aa=[int(x) for x in aa]
        price=0
        err=0
        for j in range(len(aa)):
            if aa[j] > mono[j][1]:
                err=1
        if err==1:
            print(-1)
        else:
            for j in range(len(aa)):
                price=price+mono[j][0]*aa[j]
                bread[j][1]=mono[j][1]-aa[j]
            print(price)
    elif aa[0]=='add':
        aa=aa[1:]
        aa=[int(x) for x in aa]
        for k in range(len(aa)):
            mono[k][1]=mono[k][1]+aa[j]

Comments

[8524ba23]

問題が分からないと回答できないと思うのですが、いかがお考えでしょうか？

[cateye]

「規定に違反する」のは、問題文だけですか？・・・回答を、他者に聞くには良いのですか？

[nono33]

ご質問ありがとうございます。
can110さん、そうですね。問題文からだいぶ離れているのでもう少し背景を記載します。
monoには３種類、それぞれ値段と個数が入力されています。
aにはある行為が６回入力されています。
行為名がOKの場合はmonoからそれぞれ記載の個数分ずつ売ります。
行為名がaddの場合は、monoにそれぞれの個数を追加します。
行為名がOKの場合は売上金priceを出力
行為名OKの注文を達成できない場合には-1を出力します。

cateyeさん、ありがとうございます。
> 回答を、他者に聞くには良いのですか？
回答を尋ねる行為も違反ですが、私はこの問題にすでに回答済み（一度しか挑戦できないため）なので大丈夫です。

[yymmt]

前提条件がもう少し欲しいです。
1. listを足し合わせるのにsum()は利用可能でしょうか?
2. numpy等のパッケージは利用可能でしょうか?
3. monoを分解してmono_price, mono_countとするのは可能でしょうか?

[nono33]

yymmt様
ご質問ありがとうございます。
1. listを足し合わせるのにsum()は利用可能でしょうか?
2. numpy等のパッケージは利用可能でしょうか?
3. monoを分解してmono_price, mono_countとするのは可能でしょうか?
上記全て可能ですが、
例えば３の場合は、途中に
mono_price=[x[0] for x in mono]
のようにコードを入れる必要があります。

宜しくお願いいたします。

[yymmt]

monoやaは与えられたものとして、自分でパースしなさいと理解しました。

[nono33]

そうです。宜しくお願いいたします。

Answer 1

どの部分が遅くなっている原因でしょうか？

下記のように実行するとプロファイラが動きますので、関数の呼び出し回数や実行時間を調べることができます。

python -m cProfile hoge.py

実行結果は

         25 function calls in 0.002 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.002    0.002 hoge.py:1(<module>)
        1    0.000    0.000    0.000    0.000 hoge.py:22(<listcomp>)
        4    0.000    0.000    0.000    0.000 hoge.py:7(<listcomp>)
        1    0.000    0.000    0.002    0.002 {built-in method builtins.exec}
        7    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        4    0.002    0.000    0.002    0.000 {built-in method builtins.print}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        6    0.000    0.000    0.000    0.000 {method 'split' of 'str' objects}

となりました。一回だけだとほとんど分かりませんが、1000回くらいループすると、どの部分が遅いか分かります。print()が非常に重いのでコメントアウトやリダイレクトすると良いかも知れません。

どうすれば早くなりますか？

高速化のポイントとしては

• 重い処理を同等の軽い処理に置き換える
• loopを減らす・内包表記を使う
• 不要な処理は実行しない

ということです。例えば回数が多く呼ばれている関数(ここではlen()やsplit())が削除できないか、あるいは高速化できないかを考えます。例えば一例として

• range()ではなく既存のリストでループ
• 文字列比較に先頭文字の'a'と'o'のみ比較
• noのときはsplit()処理が不要のためsplit処理をif後に実施

以上を行うことで実行時間は私の環境では60%くらいまで短縮できました。

mono=[[300, 3], [140, 5], [200, 5]]
a = ['ok 1 1 1', 'ok 3 4 0', 'no 1 1 1', 'ok 3 4 0', 'ok 0 0 2', 'add 1 0 0']
for aa in a:
    if aa[0]=='o':
        price = 0
        for count, m in zip(aa.split()[1:], mono):
            count = int(count)
            if count > m[1]:
                price = -1
                break
            else:
                price += m[0] * count
                m[1] -= count
        print(price)
    elif aa[0]=='a':
        mono=[[m[0], m[1] + int(count)] for count, m in zip(aa.split()[1:], mono)]

Comments

[nono33]

yymmt様、丁寧な解説・コードだけでなく、考え方までお教え頂きとても勉強になりました。
高速化などについてはなかなか勉強する方法が無かったのでとても助かりました。
ありがとうございました。