回答編集履歴
4
追記
test
CHANGED
@@ -126,4 +126,4 @@
|
|
126
126
|
|
127
127
|
|
128
128
|
|
129
|
-
[すべての提出一覧](https://beta.atcoder.jp/contests/abc081/submissions)を見る限りではAtCoderの実行環境はPython3 (3.4.3)のなためvenvなどで、仮想環境を構築して同じ環境(3.4.3)にしたほうが良いと思われます。
|
129
|
+
[すべての提出一覧](https://beta.atcoder.jp/contests/abc081/submissions?f.Task=arc086_a&f.Language=3023&f.Status=&f.User=)を見る限りではAtCoderの実行環境はPython3 (3.4.3)のなためvenvなどで、仮想環境を構築して同じ環境(3.4.3)にしたほうが良いと思われます。
|
3
追記
test
CHANGED
@@ -115,3 +115,15 @@
|
|
115
115
|
◇参考情報
|
116
116
|
|
117
117
|
[SNAKEVIZ](https://jiffyclub.github.io/snakeviz/)
|
118
|
+
|
119
|
+
|
120
|
+
|
121
|
+
---
|
122
|
+
|
123
|
+
|
124
|
+
|
125
|
+
> pythonのバージョンは3.6.5を使用しています。
|
126
|
+
|
127
|
+
|
128
|
+
|
129
|
+
[すべての提出一覧](https://beta.atcoder.jp/contests/abc081/submissions)を見る限りではAtCoderの実行環境はPython3 (3.4.3)のなためvenvなどで、仮想環境を構築して同じ環境(3.4.3)にしたほうが良いと思われます。
|
2
そもそも論として、標準入力からファイルを渡せばよい話なので修正!
test
CHANGED
@@ -20,59 +20,29 @@
|
|
20
20
|
|
21
21
|
```Python
|
22
22
|
|
23
|
-
|
23
|
+
from collections import Counter
|
24
24
|
|
25
|
-
|
25
|
+
n, k = map(int, input().split())
|
26
26
|
|
27
|
-
|
27
|
+
a = Counter((i for i in input().split()))
|
28
28
|
|
29
29
|
|
30
30
|
|
31
|
-
|
31
|
+
sort_count = sorted(a.items(), key=lambda x: x[1])
|
32
|
-
|
33
|
-
text_str = f.read()
|
34
32
|
|
35
33
|
|
36
34
|
|
35
|
+
total = 0
|
36
|
+
|
37
|
-
|
37
|
+
while len(sort_count) > k:
|
38
|
+
|
39
|
+
_, n = sort_count.pop(0)
|
40
|
+
|
41
|
+
total += n
|
38
42
|
|
39
43
|
|
40
44
|
|
41
|
-
|
42
|
-
|
43
|
-
def main():
|
44
|
-
|
45
|
-
n, k = map(int, n_k.split())
|
46
|
-
|
47
|
-
a = Counter((i for i in data.split()))
|
48
|
-
|
49
|
-
sort_count = sorted(a.items(), key=lambda x: x[1])
|
50
|
-
|
51
|
-
|
52
|
-
|
53
|
-
total = 0
|
54
|
-
|
55
|
-
while len(sort_count) > k:
|
56
|
-
|
57
|
-
_, n = sort_count.pop(0)
|
58
|
-
|
59
|
-
total += n
|
60
|
-
|
61
|
-
|
62
|
-
|
63
|
-
|
64
|
-
|
65
|
-
|
45
|
+
print(total)
|
66
|
-
|
67
|
-
|
68
|
-
|
69
|
-
|
70
|
-
|
71
|
-
if __name__ == "__main__":
|
72
|
-
|
73
|
-
timeit(stmt=main, number=100)
|
74
|
-
|
75
|
-
|
76
46
|
|
77
47
|
```
|
78
48
|
|
@@ -80,11 +50,11 @@
|
|
80
50
|
|
81
51
|
|
82
52
|
|
83
|
-
2,初回のプロファイルを取ります。
|
53
|
+
2,初回のプロファイルを取ります。入力ファイルはリダイレクトで渡します。
|
84
54
|
|
85
|
-
`python -m cProfile -o before.prof before.py`
|
55
|
+
`python -m cProfile -o before.prof before.py < 13.txt`
|
86
56
|
|
87
|
-
`python -m cProfile -o after.prof after.py`
|
57
|
+
`python -m cProfile -o after.prof after.py < 13.txt`
|
88
58
|
|
89
59
|
|
90
60
|
|
@@ -98,9 +68,9 @@
|
|
98
68
|
|
99
69
|
4,プロファイル結果を元にボトルネックを特定します。
|
100
70
|
|
101
|
-
![イメージ説明](
|
71
|
+
![イメージ説明](812ad02d39ffd2201fee0d97cfbfd489.jpeg)
|
102
72
|
|
103
|
-
実行時間が
|
73
|
+
実行時間が0.0998 sかかり、 そのうち0.0714 sが`collection`の`count`が占めているのが分かります。
|
104
74
|
|
105
75
|
直前の呼び出し部分が`update`なので、ソースコードの`Counter`をチェックします。
|
106
76
|
|
@@ -110,7 +80,11 @@
|
|
110
80
|
|
111
81
|
```
|
112
82
|
|
113
|
-
`Counter`の引数
|
83
|
+
`Counter`の引数がジェネレータ式(※1)になっているため、試しに`input().split()`に変更してみます。
|
84
|
+
|
85
|
+
※1 hayataka2049さん指摘ありがとうございました。
|
86
|
+
|
87
|
+
|
114
88
|
|
115
89
|
※注意
|
116
90
|
|
@@ -118,21 +92,21 @@
|
|
118
92
|
|
119
93
|
```Python
|
120
94
|
|
121
|
-
a = Counter(
|
95
|
+
a = Counter(input().split())
|
122
96
|
|
123
97
|
```
|
124
98
|
|
125
99
|
6,`after.py`のプロファイルを再度取ります。
|
126
100
|
|
127
|
-
`python -m cProfile -o after.prof after.py`
|
101
|
+
`python -m cProfile -o after.prof after.py < 13.txt`
|
128
102
|
|
129
103
|
`snakeviz after.prof`
|
130
104
|
|
131
|
-
![イメージ説明](
|
105
|
+
![イメージ説明](3cd713458ddb257a9dc51284a1c462e6.jpeg)
|
132
106
|
|
133
|
-
結果
|
107
|
+
◇結果
|
134
108
|
|
135
|
-
|
109
|
+
0.0714 sから0.0598 sに高速化されました。
|
136
110
|
|
137
111
|
このような形で一番CPU時間を専有している部分から、最初に求めた**デッドラインの時間を満たすまで**チューニングをします。
|
138
112
|
|
@@ -141,5 +115,3 @@
|
|
141
115
|
◇参考情報
|
142
116
|
|
143
117
|
[SNAKEVIZ](https://jiffyclub.github.io/snakeviz/)
|
144
|
-
|
145
|
-
[27.5. timeit — 小さなコード断片の実行時間計測](https://docs.python.jp/3/library/timeit.html)
|
1
timeit
test
CHANGED
@@ -141,3 +141,5 @@
|
|
141
141
|
◇参考情報
|
142
142
|
|
143
143
|
[SNAKEVIZ](https://jiffyclub.github.io/snakeviz/)
|
144
|
+
|
145
|
+
[27.5. timeit — 小さなコード断片の実行時間計測](https://docs.python.jp/3/library/timeit.html)
|