Pythonの競技プログラミングのTLE(Time limit exceeded)の対策方法

Question

いつもお世話になっております。

いまyukicoderでこの問題を解いたのですが、こんな回答をして、LTEがでて計算が遅いと言われています。
一応サンプルのテストは通っているのでコード自体はおそらく問題ないと思うのですが、Pythonのプログラムを①速くする方法とその②そしてpycharmで速さを確認する方法(やざっくり手計算などでアルゴリズムを計算する方法)を教えていただけますでしょうか。

速くなりそうな方法を考えていたのですがここを見る限り、リストの1要素が8byteらしいので、C言語はほとんどわからないのですが、listではなくてarrayだと速くなり、かつ、Nの最大値からunsigned long(4byte)だと速くなるのではないかと思っています。

(Nの最大値10^5 = 100,000 = 0001 1000 0110 1010 0000 (非負値の2進数) = 少なくとも17bitで表せる = 20bitなので3byteあれば十分表せる? = なので非負値4byteのunsigned longかと思っています)

以上になりますがどうぞよろしくお願いいたします。

####環境

python3.6
windows 10
pycharm

###いただいたコメントを受けて①

LTEになったこのテストを試した結果が以下のようになりました。

NO
         181191 function calls in 162.567 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.226    0.226  162.567  162.567 406.py:1(<module>)
        1    0.020    0.020    0.020    0.020 406.py:2(<listcomp>)
       99    0.000    0.000    0.001    0.000 codecs.py:318(decode)
       99    0.000    0.000    0.000    0.000 codecs.py:330(getstate)
       99    0.001    0.000    0.001    0.000 {built-in method _codecs.utf_8_decode}
        1    0.000    0.000  162.567  162.567 {built-in method builtins.exec}
        2    1.433    0.717    1.434    0.717 {built-in method builtins.input}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        1    0.042    0.042    0.042    0.042 {built-in method builtins.sorted}
    90442    0.014    0.000    0.014    0.000 {method 'append' of 'list' objects}
    90442  160.824    0.002  160.824    0.002 {method 'count' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.007    0.007    0.007    0.007 {method 'split' of 'str' objects}



Process finished with exit code 0

###いただいた回答を受けて②
dkato0077さんのcollections.Counterをループの外から呼び出して、すこし修正を加えたらACになりました。（こんな回答になりました）

from collections import Counter

n = int(input())
kamo = sorted([int(i) for i in input().split()], reverse=True)

isDuplicate = False
distance_list = []

#ここを追記しました
counter = Counter(kamo)
if (set([len(Counter(kamo))]) - {1}) == set():
    isDuplicate = True
#追記ここまで

for i in range(len(kamo) - 1):
    #ここをコメントアウトしました
    #if kamo.count(kamo[i]) != 1:
    #    isDuplicate = True

    distance = 0
    distance = kamo[i] - kamo[i + 1]
    distance_list.append(distance)

if not isDuplicate and (len(set(distance_list)) == 1):
    print("YES")
else:
    print("NO")

上記で試したLTEになったこのテストを再度実行したら結果が以下のようになりました。30倍くらい速い結果となりました。

NO
         90886 function calls (90874 primitive calls) in 5.793 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.032    0.032    5.793    5.793 406.py:1(<module>)
        1    0.019    0.019    0.019    0.019 406.py:4(<listcomp>)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:989(_handle_fromlist)
        2    0.000    0.000    0.029    0.015 __init__.py:519(__init__)
        2    0.000    0.000    0.029    0.015 __init__.py:588(update)
        7    0.000    0.000    0.000    0.000 _collections_abc.py:392(__subclasshook__)
        7    0.000    0.000    0.000    0.000 _weakrefset.py:16(__init__)
        7    0.000    0.000    0.000    0.000 _weakrefset.py:20(__enter__)
        7    0.000    0.000    0.000    0.000 _weakrefset.py:26(__exit__)
        7    0.000    0.000    0.000    0.000 _weakrefset.py:36(__init__)
        7    0.000    0.000    0.000    0.000 _weakrefset.py:52(_commit_removals)
        9    0.000    0.000    0.000    0.000 _weakrefset.py:58(__iter__)
       10    0.000    0.000    0.000    0.000 _weakrefset.py:70(__contains__)
        7    0.000    0.000    0.000    0.000 _weakrefset.py:81(add)
        2    0.000    0.000    0.000    0.000 abc.py:178(__instancecheck__)
      7/1    0.000    0.000    0.000    0.000 abc.py:194(__subclasscheck__)
       99    0.000    0.000    0.001    0.000 codecs.py:318(decode)
       99    0.000    0.000    0.000    0.000 codecs.py:330(getstate)
       99    0.001    0.000    0.001    0.000 {built-in method _codecs.utf_8_decode}
        2    0.029    0.014    0.029    0.014 {built-in method _collections._count_elements}
        1    0.000    0.000    5.793    5.793 {built-in method builtins.exec}
        7    0.000    0.000    0.000    0.000 {built-in method builtins.getattr}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.hasattr}
        2    5.672    2.836    5.673    2.836 {built-in method builtins.input}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
      8/2    0.000    0.000    0.000    0.000 {built-in method builtins.issubclass}
        7    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        1    0.031    0.031    0.031    0.031 {built-in method builtins.sorted}
        7    0.000    0.000    0.000    0.000 {method '__subclasses__' of 'type' objects}
       14    0.000    0.000    0.000    0.000 {method 'add' of 'set' objects}
    90442    0.005    0.000    0.005    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        7    0.000    0.000    0.000    0.000 {method 'remove' of 'set' objects}
        1    0.004    0.004    0.004    0.004 {method 'split' of 'str' objects}



Process finished with exit code 0

Answer 1

スクリプト名がmain.pyと仮定して、インプットをin0ファイルにして、

python -m cProfile main.py < in0
とすることで速度をはかれます。

諸悪の根源は

    if kamo.count(kamo[i]) != 1:
        isDuplicate = True

です。

Comments

[mofu_mofu]

mkgreiさん
いつも大変お世話になっております。こんなやり方があるのですね。ありがとうございます。

質問に追記したのですが、cProfileだと上記のような結果になりました。
とくに多いのが以下の部分で
90442 0.014 0.000 0.014 0.000 {method 'append' of 'list' objects}
90442 160.824 0.002 160.824 0.002 {method 'count' of 'list' objects}

結果のここの部分が回数が多いので、このコードの後ろらへんが怪しいなあと思います。
この結果を見る限りではappendとcountが回数が多そうです。appendとcountが使われているのがfor文の中で、そのfor文のl.8-9(countの部分)とl.13(appendの部分)で負担が大きいかな？と思ったのですが、このような解釈であっていますでしょうか？

以上となりますがどうぞよろしくお願いいたします。

[mkgrei]

回数も重要ですが、実行時間も重要です。

countの部分で160秒以上かかっています。

これはcountということがO(N)であるのに対して、それをN回行っており、結果O(N^2)であることが問題であることを示しています。

これに対して、appendはO(1)であり、それがN回でO(N)なので、それほど問題にはなりません。

[mofu_mofu]

私の理解力が乏しいため何回も質問をしてしまい大変恐縮なのですが、
appendがO(N)なのはforループ内でリストにある値を一度だけ追加して、それをN回行っているからという理由だと思うのですが、countがO(N)になる理由がいまいちわかりません。

これはcount関数のソースコード内でlistに対して計算量O(N)の探索アルゴリズムが動いていて、そのうえで私が書いたforループがN回回るから、というのが理由になるんでしょうか？

[退会済みユーザー]

イエス。対策としては、例えばcollections.Counterを使って最初に数え上げて、forループの中ではそのカウンターを参照するだけにする、などがあるでしょうね。横槍失礼しました。

[mkgrei]

dkato0077さん、代わりに回答していただきありがとうございます。

ちなみにですが、このcountは取り除くことができます。
2つ以上同じ値がないことを保証しようとしていますが、
2つ以上同じ値があるとその差は0になりますので、差だけを見ることで十分なはずです。

この課題では、
差が0ではないこと、そして、差がずっと同じであること
の2点を確かめることができれば解けます。

[mofu_mofu]

dkato0077さん mkgreiさん
collections.Counterを使うことで解決しました（コードと実行結果は追記に記載）。
ループをさせなくてもカウントができるのですね。しかもすごく速い。
いままで計算量を意識したことがなかったのですが、お二人のアドバイスのおかげでACになるまで取り組むことができ、ものすごく勉強になりました。

お二人方にお礼申し上げます。ありがとうございます。