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

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

ただいまの
回答率

90.47%

  • Python 3.x

    10253questions

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

  • PyCharm

    235questions

    エディター・開発ツール

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

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,119

mofu_mofu

score 61

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

いま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
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 1

checkベストアンサー

+2

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

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

諸悪の根源は

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


です。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/02/25 19:38

    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の部分)で負担が大きいかな?と思ったのですが、このような解釈であっていますでしょうか?

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

    キャンセル

  • 2018/02/25 21:51

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

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

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

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

    キャンセル

  • 2018/02/26 00:34

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

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

    キャンセル

  • 2018/02/26 00:54

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

    キャンセル

  • 2018/02/26 10:37

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

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

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

    キャンセル

  • 2018/02/26 22:45

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

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

    キャンセル

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

  • ただいまの回答率 90.47%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

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

  • Python 3.x

    10253questions

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

  • PyCharm

    235questions

    エディター・開発ツール