回答編集履歴
4
説明を改善
answer
CHANGED
|
@@ -126,10 +126,12 @@
|
|
|
126
126
|
|
|
127
127
|
### 遅い理由の説明
|
|
128
128
|
- sort_count = sorted(a.items(), key=lambda x: x[1])
|
|
129
|
-
これをやるとaの中身をぜんぶ手繰り寄せた上で、キーでソートする（無駄にポインタ見る回数が増える）ので遅い。sorted(a.values())は値をぜんぶ取ってきてソートするだけなのでだいぶマシ。
|
|
129
|
+
これをやるとaの中身をぜんぶ手繰り寄せた上で、キーでソートする（無駄にオブジェクトをたくさん作ったり、ポインタ見る回数が増えたり色々する）ので遅い。sorted(a.values())は値をぜんぶ取ってきてソートするだけなのでだいぶマシ。
|
|
130
|
+
|
|
131
|
+
以下はループ内のお話なので、とてもシビアに効いてきます。個々の計算はそうでもなくても、ループ回数がそれなりにありますから。
|
|
130
132
|
- while len(sort_count) > k:
|
|
131
133
|
毎回len計算して比較するから。
|
|
132
134
|
- _, n = sort_count.pop(0)
|
|
133
|
-
popという操作はオブジェクトを変更す
|
|
135
|
+
popという操作はオブジェクトを変更します。当然それなりに遅いです。
|
|
134
136
|
- total += n
|
|
135
|
-
ただの加算なのに意外と時間取ってますね。こう
|
|
137
|
+
ただの加算なのに意外と時間取ってますね。ループの中だとこうなります（というか逆に、これと比較するとlen, 比較, popは優秀なのか・・・）。
|
3
インクリメントじゃないじゃん・・・
answer
CHANGED
|
@@ -132,4 +132,4 @@
|
|
|
132
132
|
- _, n = sort_count.pop(0)
|
|
133
133
|
popという操作はオブジェクトを変更する。早くはない。
|
|
134
134
|
- total += n
|
|
135
|
-
ただの
|
|
135
|
+
ただの加算なのに意外と時間取ってますね。こういう意外性もあります。
|
2
理論的な説明を追加
answer
CHANGED
|
@@ -122,4 +122,14 @@
|
|
|
122
122
|
24 100 242.0 2.4 3.7 sum(sort_count[:l-k])
|
|
123
123
|
|
|
124
124
|
```
|
|
125
|
-
とりあえずわかることは`a = Counter((i for i in data.split()))`の行が壮絶に遅いことですが、これはどちらにもあるので気にしないこととして、あとはbeforeの方はぜんぶ遅いですね。
|
|
125
|
+
とりあえずわかることは`a = Counter((i for i in data.split()))`の行が壮絶に遅いことですが、これはどちらにもあるので気にしないこととして、あとはbeforeの方はぜんぶ遅いですね。
|
|
126
|
+
|
|
127
|
+
### 遅い理由の説明
|
|
128
|
+
- sort_count = sorted(a.items(), key=lambda x: x[1])
|
|
129
|
+
これをやるとaの中身をぜんぶ手繰り寄せた上で、キーでソートする（無駄にポインタ見る回数が増える）ので遅い。sorted(a.values())は値をぜんぶ取ってきてソートするだけなのでだいぶマシ。
|
|
130
|
+
- while len(sort_count) > k:
|
|
131
|
+
毎回len計算して比較するから。
|
|
132
|
+
- _, n = sort_count.pop(0)
|
|
133
|
+
popという操作はオブジェクトを変更する。早くはない。
|
|
134
|
+
- total += n
|
|
135
|
+
ただのインクリメントなのに意外と時間取ってますね。こういう意外性もあります。
|
1
説明を追記
answer
CHANGED
|
@@ -1,5 +1,10 @@
|
|
|
1
1
|
面白そうなので、line_profilerというものを使ってプロファイリングしてみました。
|
|
2
2
|
|
|
3
|
+
参考：
|
|
4
|
+
[Python: line_profiler でボトルネックを調べる - CUBE SUGAR CONTAINER](http://blog.amedama.jp/entry/2016/08/31/213229)
|
|
5
|
+
|
|
6
|
+
道具立てのためにbefore.pyとafter.pyを作り、それぞれline_profilerでプロファイリングします。
|
|
7
|
+
|
|
3
8
|
**before.py**
|
|
4
9
|
```python
|
|
5
10
|
from collections import Counter
|