Pythonの計算コストについて

Question

困っていること

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]))

試したこと

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

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

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

Answer 1

面白そうなので、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は優秀なのか・・・）。

Comments

[ugokumaitake]

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

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

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

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

Answer 2

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がcollectionのcountが占めているのが分かります。
直前の呼び出し部分が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)にしたほうが良いと思われます。

Comments

[hayataka2049]

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

[umyu]

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

[hayataka2049]

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

[umyu]

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

[hayataka2049]

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

[umyu]

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

[hayataka2049]

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

[umyu]

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

[hayataka2049]

理解しました

[mkgrei]

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

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

[umyu]

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

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

[ugokumaitake]

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

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

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

Answer 3

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

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

return max ( 0, a.length - k)