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

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

ただいまの
回答率

90.84%

  • Python 3.x

    4845questions

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

Pythonの計算コストについて

解決済

回答 3

投稿

  • 評価
  • クリップ 4
  • VIEW 367

ugokumaitake

score 2

 困っていること

AtcoderのABC081のC問題を解いていたところ、私がはじめに書いたコードはTLE(実行制限時間超過)となってしまいました。
その後、ソースコードを修正し、そのコードは通ったのですが、最初に書いたコードのどの処理にコストが高くかかってしまったのかいまいちわからないため、教えていただきたいです。

問題とそのテストケースのリンクは以下の通りです。
ABC081 C問題
テストケース(DropBox)

pythonのバージョンは3.6.5を使用しています。

 TLEとなったソースコード

from collections import Counter
n, k = map(int, input().split())
a = Counter((i for i in input().split()))

sort_count = sorted(a.items(), key=lambda x: x[1])

total = 0
while len(sort_count) > k:
    _, n = sort_count.pop(0)
    total += n

print(total)

 修正後のソースコード

from collections import Counter


n, k = map(int, input().split())
a = Counter((i for i in input().split()))

sort_count = sorted(a.values())

total = 0
l = len(sort_count)

if len(sort_count) <= k:
    print(0)
else:
    print(sum(sort_count[:l-k]))

 試したこと

修正前のコードでは、出現回数を昇順にソートしたものから1つずつpopしてtotalを算出しています。

修正後のコードでは、出現回数のみを格納したソートされたリストからpythonの組込関数であるsumを用いてtotalを算出しています。

勉強不足で申し訳ございませんが、どの部分の処理にコストが高くかかっているのか知りたいです。
よろしくお願いします。

  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 3

+6

面白そうなので、line_profilerというものを使ってプロファイリングしてみました。

参考:
Python: line_profiler でボトルネックを調べる - CUBE SUGAR CONTAINER

道具立てのためにbefore.pyとafter.pyを作り、それぞれline_profilerでプロファイリングします。

before.py

from collections import Counter

with open("1.txt", "r") as f:
    text_str = f.read()

n_k, data = text_str.split("\n")[:2]

@profile
def process():
    for x in range(100):
        n, k = map(int, n_k.split())
        a = Counter((i for i in data.split()))

        sort_count = sorted(a.items(), key=lambda x: x[1])

        total = 0
        while len(sort_count) > k:
            _, n = sort_count.pop(0)
            total += n

        #print(total)
        total

if __name__ == "__main__":
    process()

after.py

from collections import Counter

with open("1.txt", "r") as f:
    text_str = f.read()

n_k, data = text_str.split("\n")[:2]

@profile
def process():
    for x in range(100):
        n, k = map(int, n_k.split())
        a = Counter((i for i in data.split()))

        sort_count = sorted(a.values())

        total = 0
        l = len(sort_count)

        if len(sort_count) <= k:
            # print(0)
            0
        else:
            # print(sum(sort_count[:l-k]))
            sum(sort_count[:l-k])

if __name__ == "__main__":
    process()

実行結果

$ kernprof -lv before.py
Wrote profile results to before.py.lprof
Timer unit: 1e-06 s

Total time: 0.017229 s
File: before.py
Function: process at line 8

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     8                                           @profile
     9                                           def process():
    10       101        141.0      1.4      0.8      for x in range(100):
    11       100        504.0      5.0      2.9          n, k = map(int, n_k.split())
    12       100       8778.0     87.8     50.9          a = Counter((i for i in data.split()))
    13                                           
    14       100       2164.0     21.6     12.6          sort_count = sorted(a.items(), key=lambda x: x[1])
    15                                           
    16       100        163.0      1.6      0.9          total = 0
    17      1100       1858.0      1.7     10.8          while len(sort_count) > k:
    18      1000       2092.0      2.1     12.1              _, n = sort_count.pop(0)
    19      1000       1397.0      1.4      8.1              total += n
    20                                           
    21                                                   #print(total)
    22       100        132.0      1.3      0.8          total

$ kernprof -lv after.py
Wrote profile results to after.py.lprof
Timer unit: 1e-06 s

Total time: 0.006542 s
File: after.py
Function: process at line 8

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     8                                           @profile
     9                                           def process():
    10       101         71.0      0.7      1.1      for x in range(100):
    11       100        258.0      2.6      3.9          n, k = map(int, n_k.split())
    12       100       5397.0     54.0     82.5          a = Counter((i for i in data.split()))
    13                                           
    14       100        354.0      3.5      5.4          sort_count = sorted(a.values())
    15                                           
    16       100         70.0      0.7      1.1          total = 0
    17       100         70.0      0.7      1.1          l = len(sort_count)
    18                                           
    19       100         80.0      0.8      1.2          if len(sort_count) <= k:
    20                                                       # print(0)
    21                                                       0
    22                                                   else:
    23                                                       # print(sum(sort_count[:l-k]))
    24       100        242.0      2.4      3.7              sum(sort_count[:l-k])


とりあえずわかることはa = Counter((i for i in data.split()))の行が壮絶に遅いことですが、これはどちらにもあるので気にしないこととして、あとはbeforeの方はぜんぶ遅いですね。

 遅い理由の説明

  • sort_count = sorted(a.items(), key=lambda x: x[1])
    これをやるとaの中身をぜんぶ手繰り寄せた上で、キーでソートする(無駄にオブジェクトをたくさん作ったり、ポインタ見る回数が増えたり色々する)ので遅い。sorted(a.values())は値をぜんぶ取ってきてソートするだけなのでだいぶマシ。

以下はループ内のお話なので、とてもシビアに効いてきます。個々の計算はそうでもなくても、ループ回数がそれなりにありますから。

  • while len(sort_count) > k:
    毎回len計算して比較するから。
  • _, n = sort_count.pop(0)
    popという操作はオブジェクトを変更します。当然それなりに遅いです。
  • total += n
    ただの加算なのに意外と時間取ってますね。ループの中だとこうなります(というか逆に、これと比較するとlen, 比較, popは優秀なのか・・・)。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/05/04 23:18

    丁寧な解説ありがとうございました。

    ループ内の各処理とプロファイル結果から、どの操作に時間がかかっているのかが非常にわかりやすかったです。


    ふと冷静に自分が書いたプログラムを見るとなんでこんな書き方したんだろうと恥ずかしくなりますね。
    急いでプログラムを作っているとはいえ、各処理の正当性を確かめながらプログラムを書かなければいけないと再認識しました。

    ありがとうございました。

    キャンセル

checkベストアンサー

+5

cProfile & snakeviz & timeitを使ったプロファイルの仕方です。

<< チューニングの原則 >>
1,プロファイラを使う。代表的なプロファイラとしてcProfileがあります。
2,チューニングのデッドラインを決める。
今回の場合は、質問文のリンク先の問題にある、実行時間制限: 2 sec が該当します。
チューニングすることによってこれ以下の実行時間にしないといけません。

◇手順
1,before.pyを作成しその後コピーしafter.pyを作成します。

from collections import Counter
n, k = map(int, input().split())
a = Counter((i for i in input().split()))

sort_count = sorted(a.items(), key=lambda x: x[1])

total = 0
while len(sort_count) > k:
    _, n = sort_count.pop(0)
    total += n

print(total)


変更するのはafter.pyです。

2,初回のプロファイルを取ります。入力ファイルはリダイレクトで渡します。
python -m cProfile -o before.prof before.py < 13.txt
python -m cProfile -o after.prof after.py < 13.txt

3,snakevizで、プロファイル結果を表示します。
snakeviz before.prof
snakeviz after.prof

4,プロファイル結果を元にボトルネックを特定します。
イメージ説明
実行時間が0.0998 sかかり、 そのうち0.0714 sがcollectioncountが占めているのが分かります。
直前の呼び出し部分がupdateなので、ソースコードのCounterをチェックします。

    a = Counter((i for i in data.split()))


Counterの引数がジェネレータ式(※1)になっているため、試しにinput().split()に変更してみます。
※1 hayataka2049さん指摘ありがとうございました。

※注意
ここから変更するソースコードはafter.pyです。

    a = Counter(input().split())


6,after.pyのプロファイルを再度取ります。
python -m cProfile -o after.prof after.py < 13.txt
snakeviz after.prof
イメージ説明
◇結果
0.0714 sから0.0598 sに高速化されました。
このような形で一番CPU時間を専有している部分から、最初に求めたデッドラインの時間を満たすまでチューニングをします。

◇参考情報
SNAKEVIZ


pythonのバージョンは3.6.5を使用しています。

すべての提出一覧を見る限りではAtCoderの実行環境はPython3 (3.4.3)のなためvenvなどで、仮想環境を構築して同じ環境(3.4.3)にしたほうが良いと思われます。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/05/04 06:26

    a = Counter((i for i in data.split()))
    はtupleじゃなくてジェネレータ式です。
    にしても、リスト内包の方が早くなるのか・・・

    キャンセル

  • 2018/05/04 06:28

    >hayataka2049さんへ
    すみませぬううう。いえそもそも論としてこの形でデータを保持する必要があるのかという問題も。

    キャンセル

  • 2018/05/04 06:32

    この場合、
    a = Counter(data.split())
    でよさそうですが、これでもまだ激遅なので(オリジナルの半分程度の処理時間にしかならない)、Counter以外の手段で速くできるか・・・という挑戦のしがいがありそうですね(標準でも遅いモジュールはおっそいし、今回の目的に適うかもあるから)。

    キャンセル

  • 2018/05/04 08:04

    >hayataka2049さんへ
    timeitモジュールを使ってループを100回するのをやめました。
    あと標準のリダイレクトよりファイル入力を受け取る形に変更しました。

    キャンセル

  • 2018/05/04 08:36

    便利そうです。行で見えるのがなんとなく気に入ってline_profiler好んでましたけど、cProfileは標準だしsnakevizも良さそうです。cProfileは勝手にtimeitで測ってくれる感じですか?

    キャンセル

  • 2018/05/04 09:01

    >hayataka2049さんへ
    1,cProfileは勝手にtimeitで測ってくれませんー。。
    2,snakevizは初期表示が円グラフなので、site-packages\snakeviz\templates\viz.htmlを弄って、棒グラフに変更してます。

    キャンセル

  • 2018/05/04 09:03

    あれ? ではtimeitで測ってるのは回答の中でどの部分ですか?>1

    キャンセル

  • 2018/05/04 09:22

    https://teratail.com/questions/history-reply/190023
    回答の最初のコードに書いてあった以下の部分になります。
    if __name__ == "__main__":
    timeit(stmt=main, number=100)

    キャンセル

  • 2018/05/04 09:25

    理解しました

    キャンセル

  • 2018/05/04 12:32

    素朴な疑問ですが、cProfileやline_profilerなどをいれてしまうと、for文を使う場合、回した分だけプロファイラのオーバーヘッドがかかってしまって計算時間に影響が出ませんか?

    手元で実測すれば良いのですが、典型的な回避テクニックがあれば教えていただきたく…

    キャンセル

  • 2018/05/04 16:19

    >mkgreiさんへ
    for文のオーバーヘッドに関しては気にしてませんでした。回避テクニックあるのでしょうか・・。

    あと回答文に書いていない点で、プロファイラを取る時に気にしている点は、GC(Garbage Collection)の影響と1回ではなく複数回プロファイルを取るぐらいでしょうか。

    キャンセル

  • 2018/05/04 23:09

    ご回答ありがとうございます。

    早速教えていただいた手法でプロファイルをして見たところ、どの処理にコストがかかっているか一目瞭然で分かり易かったです。

    恥ずかしながらプロファイルというものを知らなかったので、このような手法があることを知り目から鱗でした。
    また、ご指摘いただいた通り、早速pythonのバージョンを3.4.3に変更いたしました
    ありがとうございます。

    キャンセル

+1

2秒で20万のデータをですか。。
こんなのどうでしょう
空の配列用意してデータを読み込みながら重複を省く。
(javascript風の動かないやつですが単純ですのでご勘弁を)

let a = []
for(i of input().split() ){
  a[parseInt(i)] = i
}

return max ( 0, a.length - k) 

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

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

  • Python 3.x

    4845questions

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