回答編集履歴
6
edit
answer
CHANGED
|
@@ -38,12 +38,13 @@
|
|
|
38
38
|
|
|
39
39
|
---
|
|
40
40
|
|
|
41
|
-
比較。
|
|
41
|
+
比較。（更新：groupby, numpy.where, backward, forward）
|
|
42
42
|
```python
|
|
43
43
|
from itertools import groupby
|
|
44
|
+
import numpy as np
|
|
44
45
|
import random
|
|
46
|
+
|
|
45
47
|
from contextlib import contextmanager
|
|
46
|
-
|
|
47
48
|
import time
|
|
48
49
|
@contextmanager
|
|
49
50
|
def timer(name):
|
|
@@ -51,43 +52,45 @@
|
|
|
51
52
|
yield
|
|
52
53
|
print(f'[{name}] done in {time.time() - t0:.5f} s')
|
|
53
54
|
|
|
54
|
-
slen =
|
|
55
|
+
slen = 1300
|
|
55
|
-
tslen =
|
|
56
|
+
tslen = 1500
|
|
56
|
-
N =
|
|
57
|
+
N = 10000
|
|
57
58
|
|
|
59
|
+
ss = []
|
|
60
|
+
for _i in range(N):
|
|
58
|
-
random.seed(
|
|
61
|
+
random.seed(_i)
|
|
59
|
-
|
|
62
|
+
s_ = np.array([1]*(tslen-slen) + [random.randint(0, 1) for _ in range(slen)])
|
|
63
|
+
ss.append(s_)
|
|
60
64
|
|
|
61
65
|
with timer('groupby'):
|
|
66
|
+
mm0 = []
|
|
62
|
-
for
|
|
67
|
+
for _i in range(N):
|
|
63
|
-
s =
|
|
68
|
+
s = ss[_i]
|
|
64
69
|
ans = [len(list(g)) for k, g in groupby(s)]
|
|
65
70
|
m = max(ans[::2])
|
|
71
|
+
mm0.append(m)
|
|
72
|
+
|
|
73
|
+
with timer('numpy.where'):
|
|
66
|
-
|
|
74
|
+
mm1 = []
|
|
75
|
+
for _i in range(N):
|
|
76
|
+
a = ss[_i]
|
|
77
|
+
offset = 1
|
|
78
|
+
diff_a = a[offset:] - a[:-offset]
|
|
67
79
|
|
|
68
|
-
|
|
80
|
+
pos1to0 = np.where(diff_a ==-1)[0] + offset
|
|
69
|
-
s = s_org
|
|
70
|
-
|
|
81
|
+
pos0to1 = np.where(diff_a ==+1)[0] + offset
|
|
71
|
-
m = 0
|
|
72
|
-
c = 0
|
|
73
|
-
for v in s:
|
|
74
|
-
if v == 1:
|
|
75
|
-
c += 1
|
|
76
|
-
else:
|
|
77
|
-
if c > m:
|
|
78
|
-
m = c
|
|
79
|
-
c = 0
|
|
80
|
-
if c > m:
|
|
81
|
-
m = c
|
|
82
|
-
m1 = m
|
|
83
82
|
|
|
83
|
+
pos0to1 = np.append([0], pos0to1)
|
|
84
|
+
m = (pos1to0 - pos0to1[:len(pos1to0)]).max()
|
|
85
|
+
mm1.append(m)
|
|
86
|
+
|
|
84
87
|
with timer('backward-search'):
|
|
85
88
|
def forward_search(s):
|
|
86
89
|
j = 0
|
|
87
90
|
while j < len(s) and s[j] == 1:
|
|
88
91
|
j += 1
|
|
89
92
|
return j
|
|
90
|
-
|
|
93
|
+
|
|
91
94
|
def backward_search(s, m):
|
|
92
95
|
if m >= len(s):
|
|
93
96
|
return False, len(s), 0
|
|
@@ -95,7 +98,9 @@
|
|
|
95
98
|
c = forward_search(t)
|
|
96
99
|
return True, m, c
|
|
97
100
|
|
|
101
|
+
mm2 = []
|
|
98
|
-
for
|
|
102
|
+
for _i in range(N):
|
|
103
|
+
s = ss[_i]
|
|
99
104
|
m = 0
|
|
100
105
|
i = forward_search(s)
|
|
101
106
|
m = i
|
|
@@ -108,10 +113,28 @@
|
|
|
108
113
|
i += j
|
|
109
114
|
if c > m:
|
|
110
115
|
m = c
|
|
116
|
+
mm2.append(m)
|
|
117
|
+
|
|
118
|
+
with timer('forward-search'):
|
|
119
|
+
mm3 = []
|
|
120
|
+
for _i in range(N):
|
|
121
|
+
s = ss[_i]
|
|
111
|
-
|
|
122
|
+
m = 0
|
|
123
|
+
c = 0
|
|
124
|
+
for v in s:
|
|
125
|
+
if v == 1:
|
|
126
|
+
c += 1
|
|
127
|
+
else:
|
|
128
|
+
if c > m:
|
|
129
|
+
m = c
|
|
130
|
+
c = 0
|
|
131
|
+
if c > m:
|
|
132
|
+
m = c
|
|
133
|
+
mm3.append(m)
|
|
112
134
|
|
|
113
|
-
assert
|
|
135
|
+
assert np.all(mm0 == mm1)
|
|
114
|
-
assert
|
|
136
|
+
assert np.all(mm0 == mm2)
|
|
137
|
+
assert np.all(mm0 == mm3)
|
|
115
138
|
```
|
|
116
139
|
|
|
117
140
|
---
|
5
edit
answer
CHANGED
|
@@ -145,4 +145,8 @@
|
|
|
145
145
|
Pythonでそれをやるのは少しちぐはぐ感が残ってしまいます。
|
|
146
146
|
C++などで書き換えるだけで、もとのアルゴリズムで高速に処理できることが見込まれるためです。
|
|
147
147
|
|
|
148
|
+
（重複するようなケースが出現する場合、キャッシュをうまく使うことも重要です。
|
|
149
|
+
https://pypi.python.org/pypi/fastcache/0.4.3
|
|
150
|
+
メモリと演算のバランスをチューニングするがよいコード書くために大切です。）
|
|
151
|
+
|
|
148
152
|
高速化することも大事ですが、楽して高速化することも大事です。
|
4
edit
answer
CHANGED
|
@@ -112,4 +112,37 @@
|
|
|
112
112
|
|
|
113
113
|
assert m0 == m1
|
|
114
114
|
assert m1 == m2
|
|
115
|
-
```
|
|
115
|
+
```
|
|
116
|
+
|
|
117
|
+
---
|
|
118
|
+
|
|
119
|
+
雑談
|
|
120
|
+
|
|
121
|
+
高速化を行う際には、
|
|
122
|
+
|
|
123
|
+
1. アルゴリズムの改良
|
|
124
|
+
2. コーディングの改良
|
|
125
|
+
|
|
126
|
+
に分けて考えるとスッキリします。
|
|
127
|
+
|
|
128
|
+
今回の場合、最低でもO(N)で各ピクセルを見ないと答えが出ないような問題です。
|
|
129
|
+
すると、探索の打ち切りの可能性を検討した後、コーディングの改良を検討します。
|
|
130
|
+
|
|
131
|
+
（目的とあっていない可能性がありますが、
|
|
132
|
+
最長の1の塊を探索するのであれば、最長になりえない領域をできるだけスキップする作戦を考えます。）
|
|
133
|
+
|
|
134
|
+
次に書き方を工夫します。
|
|
135
|
+
（ブロック化してSIMD命令を利用するのが、C++などのコンパイル言語を使う際に検討する必要があります。）
|
|
136
|
+
Pythonの場合、numpy、opencvのライブラリを出来る限り利用できるようにするのが近道です。
|
|
137
|
+
すると、numpyのメソッド、opencvのメソッド、pythonのbuilt-inメソッドを使用することを検討すべきです。
|
|
138
|
+
|
|
139
|
+
一個ずつピクセルを見ていくより、ベクトルとみなしてsumが速いことは予想できます。
|
|
140
|
+
ならば、sumだけで済むように前処理を検討するのが良さそうです。
|
|
141
|
+
|
|
142
|
+
opencvのオープニングを使うことで先にノイズを消してから、sumを行うのが一番速そうです。
|
|
143
|
+
|
|
144
|
+
他にもバイナリとして扱ってビット演算を用いることで高速化することも考えられます。
|
|
145
|
+
Pythonでそれをやるのは少しちぐはぐ感が残ってしまいます。
|
|
146
|
+
C++などで書き換えるだけで、もとのアルゴリズムで高速に処理できることが見込まれるためです。
|
|
147
|
+
|
|
148
|
+
高速化することも大事ですが、楽して高速化することも大事です。
|
3
edit
answer
CHANGED
|
@@ -34,4 +34,82 @@
|
|
|
34
34
|
1100001 1000001 ...
|
|
35
35
|
1000010 0111110 ...
|
|
36
36
|
...
|
|
37
|
+
```
|
|
38
|
+
|
|
39
|
+
---
|
|
40
|
+
|
|
41
|
+
比較。
|
|
42
|
+
```python
|
|
43
|
+
from itertools import groupby
|
|
44
|
+
import random
|
|
45
|
+
from contextlib import contextmanager
|
|
46
|
+
|
|
47
|
+
import time
|
|
48
|
+
@contextmanager
|
|
49
|
+
def timer(name):
|
|
50
|
+
t0 = time.time()
|
|
51
|
+
yield
|
|
52
|
+
print(f'[{name}] done in {time.time() - t0:.5f} s')
|
|
53
|
+
|
|
54
|
+
slen = 1000
|
|
55
|
+
tslen = 1200
|
|
56
|
+
N = 1000
|
|
57
|
+
|
|
58
|
+
random.seed(0)
|
|
59
|
+
s_org = [1]*(tslen-slen) + [random.randint(0, 1) for _ in range(1000)]
|
|
60
|
+
|
|
61
|
+
with timer('groupby'):
|
|
62
|
+
for _ in range(N):
|
|
63
|
+
s = map(str, s_org)
|
|
64
|
+
ans = [len(list(g)) for k, g in groupby(s)]
|
|
65
|
+
m = max(ans[::2])
|
|
66
|
+
m0 = m
|
|
67
|
+
|
|
68
|
+
with timer('forward-search'):
|
|
69
|
+
s = s_org
|
|
70
|
+
for _ in range(N):
|
|
71
|
+
m = 0
|
|
72
|
+
c = 0
|
|
73
|
+
for v in s:
|
|
74
|
+
if v == 1:
|
|
75
|
+
c += 1
|
|
76
|
+
else:
|
|
77
|
+
if c > m:
|
|
78
|
+
m = c
|
|
79
|
+
c = 0
|
|
80
|
+
if c > m:
|
|
81
|
+
m = c
|
|
82
|
+
m1 = m
|
|
83
|
+
|
|
84
|
+
with timer('backward-search'):
|
|
85
|
+
def forward_search(s):
|
|
86
|
+
j = 0
|
|
87
|
+
while j < len(s) and s[j] == 1:
|
|
88
|
+
j += 1
|
|
89
|
+
return j
|
|
90
|
+
|
|
91
|
+
def backward_search(s, m):
|
|
92
|
+
if m >= len(s):
|
|
93
|
+
return False, len(s), 0
|
|
94
|
+
t = s[m::-1]
|
|
95
|
+
c = forward_search(t)
|
|
96
|
+
return True, m, c
|
|
97
|
+
|
|
98
|
+
for _ in range(N):
|
|
99
|
+
m = 0
|
|
100
|
+
i = forward_search(s)
|
|
101
|
+
m = i
|
|
102
|
+
while i < len(s):
|
|
103
|
+
fforward, j, c = backward_search(s[i:], m)
|
|
104
|
+
i += j
|
|
105
|
+
if fforward:
|
|
106
|
+
j = forward_search(s[i:])
|
|
107
|
+
c += j
|
|
108
|
+
i += j
|
|
109
|
+
if c > m:
|
|
110
|
+
m = c
|
|
111
|
+
m2 = m
|
|
112
|
+
|
|
113
|
+
assert m0 == m1
|
|
114
|
+
assert m1 == m2
|
|
37
115
|
```
|
2
edit
answer
CHANGED
|
@@ -27,10 +27,11 @@
|
|
|
27
27
|
ブロック分けしてdivide-and-conquerでもよいですが。
|
|
28
28
|
|
|
29
29
|
```
|
|
30
|
-
↓ ↓
|
|
30
|
+
↓ ↓↓ ↓
|
|
31
|
-
0000001
|
|
31
|
+
0000001 0111011 ...
|
|
32
|
-
0000010
|
|
32
|
+
0000010 1111011 ...
|
|
33
|
-
1000010
|
|
33
|
+
1000010 0000000 ...
|
|
34
|
-
1100001
|
|
34
|
+
1100001 1000001 ...
|
|
35
|
-
1000010
|
|
35
|
+
1000010 0111110 ...
|
|
36
|
+
...
|
|
36
37
|
```
|
1
edit
answer
CHANGED
|
@@ -20,4 +20,17 @@
|
|
|
20
20
|
|
|
21
21
|
後はデータの性質に依存します。
|
|
22
22
|
`01010101010101010101010101010`のように並んでいるのであれば判定が必要な分遅くなります。
|
|
23
|
-
`11111111110000011100000000011`のようであれば、大幅に探索を減らすことができます。
|
|
23
|
+
`11111111110000011100000000011`のようであれば、大幅に探索を減らすことができます。
|
|
24
|
+
|
|
25
|
+
---
|
|
26
|
+
|
|
27
|
+
ブロック分けしてdivide-and-conquerでもよいですが。
|
|
28
|
+
|
|
29
|
+
```
|
|
30
|
+
↓ ↓
|
|
31
|
+
0000001
|
|
32
|
+
0000010
|
|
33
|
+
1000010
|
|
34
|
+
1100001
|
|
35
|
+
1000010
|
|
36
|
+
```
|