teratail
回答率
85.47%
質問するログイン新規登録
トップPython 3.xに関する質問numpyの連続した数値列のカウント

編集履歴

回答編集履歴

6

edit

2018/04/15 13:41

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -78,18 +78,20 @@
78
78
 
79
79
 
80
80
 
81
- 比較。
81
+ 比較。（更新：groupby, numpy.where, backward, forward）
82
82
 
83
83
  ```python
84
84
 
85
85
  from itertools import groupby
86
86
 
87
+ import numpy as np
88
+
87
89
  import random
88
90
 
91
+
92
+
89
93
  from contextlib import contextmanager
90
94
 
91
-
92
-
93
95
  import time
94
96
 
95
97
  @contextmanager
@@ -104,39 +106,139 @@
104
106
 
105
107
 
106
108
 
107
- slen = 1000
109
+ slen = 1300
108
-
110
+
109
- tslen = 1200
111
+ tslen = 1500
110
-
112
+
111
- N = 1000
113
+ N = 10000
114
+
115
+
116
+
112
-
117
+ ss = []
118
+
113
-
119
+ for _i in range(N):
114
-
120
+
115
- random.seed(0)
121
+ random.seed(_i)
116
-
122
+
117
- s_org = [1]*(tslen-slen) + [random.randint(0, 1) for _ in range(1000)]
123
+ s_ = np.array([1]*(tslen-slen) + [random.randint(0, 1) for _ in range(slen)])
124
+
125
+ ss.append(s_)
118
126
 
119
127
 
120
128
 
121
129
  with timer('groupby'):
122
130
 
131
+ mm0 = []
132
+
123
- for _ in range(N):
133
+ for _i in range(N):
124
-
134
+
125
- s = map(str, s_org)
135
+ s = ss[_i]
126
136
 
127
137
  ans = [len(list(g)) for k, g in groupby(s)]
128
138
 
129
139
  m = max(ans[::2])
130
140
 
141
+ mm0.append(m)
142
+
143
+
144
+
145
+ with timer('numpy.where'):
146
+
147
+ mm1 = []
148
+
149
+ for _i in range(N):
150
+
151
+ a = ss[_i]
152
+
153
+ offset = 1
154
+
155
+ diff_a = a[offset:] - a[:-offset]
156
+
157
+
158
+
159
+ pos1to0 = np.where(diff_a ==-1)[0] + offset
160
+
161
+ pos0to1 = np.where(diff_a ==+1)[0] + offset
162
+
163
+
164
+
165
+ pos0to1 = np.append([0], pos0to1)
166
+
167
+ m = (pos1to0 - pos0to1[:len(pos1to0)]).max()
168
+
169
+ mm1.append(m)
170
+
171
+
172
+
173
+ with timer('backward-search'):
174
+
175
+ def forward_search(s):
176
+
177
+ j = 0
178
+
179
+ while j < len(s) and s[j] == 1:
180
+
181
+ j += 1
182
+
183
+ return j
184
+
185
+
186
+
187
+ def backward_search(s, m):
188
+
189
+ if m >= len(s):
190
+
191
+ return False, len(s), 0
192
+
193
+ t = s[m::-1]
194
+
195
+ c = forward_search(t)
196
+
197
+ return True, m, c
198
+
199
+
200
+
201
+ mm2 = []
202
+
203
+ for _i in range(N):
204
+
205
+ s = ss[_i]
206
+
131
- m0 = m
207
+ m = 0
208
+
132
-
209
+ i = forward_search(s)
210
+
133
-
211
+ m = i
212
+
213
+ while i < len(s):
214
+
215
+ fforward, j, c = backward_search(s[i:], m)
216
+
217
+ i += j
218
+
219
+ if fforward:
220
+
221
+ j = forward_search(s[i:])
222
+
223
+ c += j
224
+
225
+ i += j
226
+
227
+ if c > m:
228
+
229
+ m = c
230
+
231
+ mm2.append(m)
232
+
233
+
134
234
 
135
235
  with timer('forward-search'):
136
236
 
137
- s = s_org
237
+ mm3 = []
138
-
238
+
139
- for _ in range(N):
239
+ for _i in range(N):
240
+
241
+ s = ss[_i]
140
242
 
141
243
  m = 0
142
244
 
@@ -160,71 +262,15 @@
160
262
 
161
263
  m = c
162
264
 
163
- m1 = m
164
-
165
-
166
-
167
- with timer('backward-search'):
168
-
169
- def forward_search(s):
170
-
171
- j = 0
172
-
173
- while j < len(s) and s[j] == 1:
174
-
175
- j += 1
176
-
177
- return j
178
-
179
-
180
-
181
- def backward_search(s, m):
182
-
183
- if m >= len(s):
265
+ mm3.append(m)
184
-
185
- return False, len(s), 0
266
+
186
-
187
- t = s[m::-1]
267
+
188
-
189
- c = forward_search(t)
268
+
190
-
191
- return True, m, c
192
-
193
-
194
-
195
- for _ in range(N):
196
-
197
- m = 0
198
-
199
- i = forward_search(s)
200
-
201
- m = i
202
-
203
- while i < len(s):
204
-
205
- fforward, j, c = backward_search(s[i:], m)
206
-
207
- i += j
208
-
209
- if fforward:
210
-
211
- j = forward_search(s[i:])
212
-
213
- c += j
214
-
215
- i += j
216
-
217
- if c > m:
218
-
219
- m = c
220
-
221
- m2 = m
222
-
223
-
224
-
225
- assert m0 == m1
269
+ assert np.all(mm0 == mm1)
226
-
270
+
227
- assert m1 == m2
271
+ assert np.all(mm0 == mm2)
272
+
273
+ assert np.all(mm0 == mm3)
228
274
 
229
275
  ```
230
276
 

5

edit

2018/04/15 13:41

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -292,4 +292,12 @@
292
292
 
293
293
 
294
294
 
295
+ （重複するようなケースが出現する場合、キャッシュをうまく使うことも重要です。
296
+
297
+ https://pypi.python.org/pypi/fastcache/0.4.3
298
+
299
+ メモリと演算のバランスをチューニングするがよいコード書くために大切です。）
300
+
301
+
302
+
295
303
  高速化することも大事ですが、楽して高速化することも大事です。

4

edit

2018/04/15 06:07

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -227,3 +227,69 @@
227
227
  assert m1 == m2
228
228
 
229
229
  ```
230
+
231
+
232
+
233
+ ---
234
+
235
+
236
+
237
+ 雑談
238
+
239
+
240
+
241
+ 高速化を行う際には、
242
+
243
+
244
+
245
+ 1. アルゴリズムの改良
246
+
247
+ 2. コーディングの改良
248
+
249
+
250
+
251
+ に分けて考えるとスッキリします。
252
+
253
+
254
+
255
+ 今回の場合、最低でもO(N)で各ピクセルを見ないと答えが出ないような問題です。
256
+
257
+ すると、探索の打ち切りの可能性を検討した後、コーディングの改良を検討します。
258
+
259
+
260
+
261
+ （目的とあっていない可能性がありますが、
262
+
263
+ 最長の1の塊を探索するのであれば、最長になりえない領域をできるだけスキップする作戦を考えます。）
264
+
265
+
266
+
267
+ 次に書き方を工夫します。
268
+
269
+ （ブロック化してSIMD命令を利用するのが、C++などのコンパイル言語を使う際に検討する必要があります。）
270
+
271
+ Pythonの場合、numpy、opencvのライブラリを出来る限り利用できるようにするのが近道です。
272
+
273
+ すると、numpyのメソッド、opencvのメソッド、pythonのbuilt-inメソッドを使用することを検討すべきです。
274
+
275
+
276
+
277
+ 一個ずつピクセルを見ていくより、ベクトルとみなしてsumが速いことは予想できます。
278
+
279
+ ならば、sumだけで済むように前処理を検討するのが良さそうです。
280
+
281
+
282
+
283
+ opencvのオープニングを使うことで先にノイズを消してから、sumを行うのが一番速そうです。
284
+
285
+
286
+
287
+ 他にもバイナリとして扱ってビット演算を用いることで高速化することも考えられます。
288
+
289
+ Pythonでそれをやるのは少しちぐはぐ感が残ってしまいます。
290
+
291
+ C++などで書き換えるだけで、もとのアルゴリズムで高速に処理できることが見込まれるためです。
292
+
293
+
294
+
295
+ 高速化することも大事ですが、楽して高速化することも大事です。

3

edit

2018/04/15 06:01

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -71,3 +71,159 @@
71
71
  ...
72
72
 
73
73
  ```
74
+
75
+
76
+
77
+ ---
78
+
79
+
80
+
81
+ 比較。
82
+
83
+ ```python
84
+
85
+ from itertools import groupby
86
+
87
+ import random
88
+
89
+ from contextlib import contextmanager
90
+
91
+
92
+
93
+ import time
94
+
95
+ @contextmanager
96
+
97
+ def timer(name):
98
+
99
+ t0 = time.time()
100
+
101
+ yield
102
+
103
+ print(f'[{name}] done in {time.time() - t0:.5f} s')
104
+
105
+
106
+
107
+ slen = 1000
108
+
109
+ tslen = 1200
110
+
111
+ N = 1000
112
+
113
+
114
+
115
+ random.seed(0)
116
+
117
+ s_org = [1]*(tslen-slen) + [random.randint(0, 1) for _ in range(1000)]
118
+
119
+
120
+
121
+ with timer('groupby'):
122
+
123
+ for _ in range(N):
124
+
125
+ s = map(str, s_org)
126
+
127
+ ans = [len(list(g)) for k, g in groupby(s)]
128
+
129
+ m = max(ans[::2])
130
+
131
+ m0 = m
132
+
133
+
134
+
135
+ with timer('forward-search'):
136
+
137
+ s = s_org
138
+
139
+ for _ in range(N):
140
+
141
+ m = 0
142
+
143
+ c = 0
144
+
145
+ for v in s:
146
+
147
+ if v == 1:
148
+
149
+ c += 1
150
+
151
+ else:
152
+
153
+ if c > m:
154
+
155
+ m = c
156
+
157
+ c = 0
158
+
159
+ if c > m:
160
+
161
+ m = c
162
+
163
+ m1 = m
164
+
165
+
166
+
167
+ with timer('backward-search'):
168
+
169
+ def forward_search(s):
170
+
171
+ j = 0
172
+
173
+ while j < len(s) and s[j] == 1:
174
+
175
+ j += 1
176
+
177
+ return j
178
+
179
+
180
+
181
+ def backward_search(s, m):
182
+
183
+ if m >= len(s):
184
+
185
+ return False, len(s), 0
186
+
187
+ t = s[m::-1]
188
+
189
+ c = forward_search(t)
190
+
191
+ return True, m, c
192
+
193
+
194
+
195
+ for _ in range(N):
196
+
197
+ m = 0
198
+
199
+ i = forward_search(s)
200
+
201
+ m = i
202
+
203
+ while i < len(s):
204
+
205
+ fforward, j, c = backward_search(s[i:], m)
206
+
207
+ i += j
208
+
209
+ if fforward:
210
+
211
+ j = forward_search(s[i:])
212
+
213
+ c += j
214
+
215
+ i += j
216
+
217
+ if c > m:
218
+
219
+ m = c
220
+
221
+ m2 = m
222
+
223
+
224
+
225
+ assert m0 == m1
226
+
227
+ assert m1 == m2
228
+
229
+ ```

2

edit

2018/04/15 05:24

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -56,16 +56,18 @@
56
56
 
57
57
  ```
58
58
 
59
- ↓ ↓
59
+ ↓ ↓↓　　↓
60
60
 
61
- 0000001
61
+ 0000001 0111011 ...
62
62
 
63
- 0000010
63
+ 0000010 1111011 ...
64
64
 
65
- 1000010
65
+ 1000010 0000000 ...
66
66
 
67
- 1100001
67
+ 1100001 1000001 ...
68
68
 
69
- 1000010
69
+ 1000010 0111110 ...
70
+
71
+ ...
70
72
 
71
73
  ```

1

edit

2018/04/12 14:22

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -43,3 +43,29 @@
43
43
  `01010101010101010101010101010`のように並んでいるのであれば判定が必要な分遅くなります。
44
44
 
45
45
  `11111111110000011100000000011`のようであれば、大幅に探索を減らすことができます。
46
+
47
+
48
+
49
+ ---
50
+
51
+
52
+
53
+ ブロック分けしてdivide-and-conquerでもよいですが。
54
+
55
+
56
+
57
+ ```
58
+
59
+ ↓ ↓
60
+
61
+ 0000001
62
+
63
+ 0000010
64
+
65
+ 1000010
66
+
67
+ 1100001
68
+
69
+ 1000010
70
+
71
+ ```