回答編集履歴
4
説明を改善
test
CHANGED
@@ -254,7 +254,11 @@
|
|
254
254
|
|
255
255
|
- sort_count = sorted(a.items(), key=lambda x: x[1])
|
256
256
|
|
257
|
-
これをやるとaの中身をぜんぶ手繰り寄せた上で、キーでソートする(無駄にポインタ見る回数が増える)ので遅い。sorted(a.values())は値をぜんぶ取ってきてソートするだけなのでだいぶマシ。
|
257
|
+
これをやるとaの中身をぜんぶ手繰り寄せた上で、キーでソートする(無駄にオブジェクトをたくさん作ったり、ポインタ見る回数が増えたり色々する)ので遅い。sorted(a.values())は値をぜんぶ取ってきてソートするだけなのでだいぶマシ。
|
258
|
+
|
259
|
+
|
260
|
+
|
261
|
+
以下はループ内のお話なので、とてもシビアに効いてきます。個々の計算はそうでもなくても、ループ回数がそれなりにありますから。
|
258
262
|
|
259
263
|
- while len(sort_count) > k:
|
260
264
|
|
@@ -262,8 +266,8 @@
|
|
262
266
|
|
263
267
|
- _, n = sort_count.pop(0)
|
264
268
|
|
265
|
-
popという操作はオブジェクトを変更す
|
269
|
+
popという操作はオブジェクトを変更します。当然それなりに遅いです。
|
266
270
|
|
267
271
|
- total += n
|
268
272
|
|
269
|
-
ただの加算なのに意外と時間取ってますね。こう
|
273
|
+
ただの加算なのに意外と時間取ってますね。ループの中だとこうなります(というか逆に、これと比較するとlen, 比較, popは優秀なのか・・・)。
|
3
インクリメントじゃないじゃん・・・
test
CHANGED
@@ -266,4 +266,4 @@
|
|
266
266
|
|
267
267
|
- total += n
|
268
268
|
|
269
|
-
ただの
|
269
|
+
ただの加算なのに意外と時間取ってますね。こういう意外性もあります。
|
2
理論的な説明を追加
test
CHANGED
@@ -247,3 +247,23 @@
|
|
247
247
|
```
|
248
248
|
|
249
249
|
とりあえずわかることは`a = Counter((i for i in data.split()))`の行が壮絶に遅いことですが、これはどちらにもあるので気にしないこととして、あとはbeforeの方はぜんぶ遅いですね。
|
250
|
+
|
251
|
+
|
252
|
+
|
253
|
+
### 遅い理由の説明
|
254
|
+
|
255
|
+
- sort_count = sorted(a.items(), key=lambda x: x[1])
|
256
|
+
|
257
|
+
これをやるとaの中身をぜんぶ手繰り寄せた上で、キーでソートする(無駄にポインタ見る回数が増える)ので遅い。sorted(a.values())は値をぜんぶ取ってきてソートするだけなのでだいぶマシ。
|
258
|
+
|
259
|
+
- while len(sort_count) > k:
|
260
|
+
|
261
|
+
毎回len計算して比較するから。
|
262
|
+
|
263
|
+
- _, n = sort_count.pop(0)
|
264
|
+
|
265
|
+
popという操作はオブジェクトを変更する。早くはない。
|
266
|
+
|
267
|
+
- total += n
|
268
|
+
|
269
|
+
ただのインクリメントなのに意外と時間取ってますね。こういう意外性もあります。
|
1
説明を追記
test
CHANGED
@@ -2,6 +2,16 @@
|
|
2
2
|
|
3
3
|
|
4
4
|
|
5
|
+
参考:
|
6
|
+
|
7
|
+
[Python: line_profiler でボトルネックを調べる - CUBE SUGAR CONTAINER](http://blog.amedama.jp/entry/2016/08/31/213229)
|
8
|
+
|
9
|
+
|
10
|
+
|
11
|
+
道具立てのためにbefore.pyとafter.pyを作り、それぞれline_profilerでプロファイリングします。
|
12
|
+
|
13
|
+
|
14
|
+
|
5
15
|
**before.py**
|
6
16
|
|
7
17
|
```python
|