回答編集履歴

10

追記

2020/04/06 21:38

投稿

hayataka2049
hayataka2049

スコア30935

test CHANGED
@@ -179,3 +179,73 @@
179
179
 
180
180
 
181
181
  int16やint8にすれば多少速くなりますが、8bitだと128個1が続いただけでオーバーフローなので都合が悪いでしょう。
182
+
183
+
184
+
185
+ ---
186
+
187
+
188
+
189
+ 行方向走査で、配列のコピーをやめてインプレース処理にすると関数自体の速度は1秒を切ります(0.6くらい)。使いたいかどうかはわかりませんが、一応載せておきます。
190
+
191
+ ```python
192
+
193
+ @jit("i4[:,:](i4[:,:])", nopython=True)
194
+
195
+ def f2_i(B):
196
+
197
+ for i in range(B.shape[0]): # 行のループ
198
+
199
+ before = 0
200
+
201
+ start_pos = 0
202
+
203
+ cnt = 0
204
+
205
+ for j in range(B.shape[1]): # 列のループ
206
+
207
+ if B[i, j] == 1: # 1のとき
208
+
209
+ if before == 0: # 直前の状態が0なら1にして数え始める
210
+
211
+ start_pos = j
212
+
213
+ before = 1
214
+
215
+ cnt += 1 # 数える
216
+
217
+ else: # 0のとき
218
+
219
+ if before != 1: # 直前の状態が0なら無視して続ける
220
+
221
+ continue
222
+
223
+ else: # 直前の状態が1のとき
224
+
225
+ # 1が出た範囲をcntで埋める
226
+
227
+ B[i, start_pos:j] = cnt
228
+
229
+
230
+
231
+ # 状態をリセットする
232
+
233
+ before = 0
234
+
235
+ cnt = 0
236
+
237
+ # 行が終わって状態が1のとき
238
+
239
+ if before == 1:
240
+
241
+ B[i, start_pos:B.shape[1]] = cnt
242
+
243
+ return B
244
+
245
+
246
+
247
+ ```
248
+
249
+
250
+
251
+ 逆に言うとコピーに時間がかかると思うので、新しい配列を返すつもりであれば本体の処理の高速化で受けられる恩恵はそんなにないのかもしれません。

9

追記

2020/04/06 21:38

投稿

hayataka2049
hayataka2049

スコア30935

test CHANGED
@@ -172,4 +172,10 @@
172
172
 
173
173
 
174
174
 
175
+ (ベンチマーク取ってるページがありましたが、これを見るとnumbaでいいじゃんとなる・・・
176
+
177
+ [Python を高速化する Numba, Cython 等を使って Julia Micro-Benchmarks してみた - Qiita](https://qiita.com/yniji/items/b7acffa02f03a94882e5))
178
+
179
+
180
+
175
181
  int16やint8にすれば多少速くなりますが、8bitだと128個1が続いただけでオーバーフローなので都合が悪いでしょう。

8

追記

2020/04/06 18:38

投稿

hayataka2049
hayataka2049

スコア30935

test CHANGED
@@ -168,7 +168,7 @@
168
168
 
169
169
 
170
170
 
171
- どちらにしても、処理時間のかなりの割合は1.6GBもある配列の生成とコピーで食っています。関数自体は一瞬で返るみたなので、これでいでしょう。
171
+ どちらにしても、処理時間のかなりの割合は1.6GBもある配列の生成とコピーで食っています。うことで、これで実用上問題にはならないでしょう。Cythonで同じロジックをやるともう少し速い可能性はあるのですが、numbaのjitコンパイルだって優秀です。
172
172
 
173
173
 
174
174
 

7

追記

2020/04/06 18:35

投稿

hayataka2049
hayataka2049

スコア30935

test CHANGED
@@ -168,7 +168,7 @@
168
168
 
169
169
 
170
170
 
171
- どちらにしても、処理時間のかなりの割合は1.6GBもある配列の生成で食っています。関数自体は一瞬で返るみたいなので、これでいいでしょう。
171
+ どちらにしても、処理時間のかなりの割合は1.6GBもある配列の生成とコピーで食っています。関数自体は一瞬で返るみたいなので、これでいいでしょう。
172
172
 
173
173
 
174
174
 

6

追記

2020/04/06 18:32

投稿

hayataka2049
hayataka2049

スコア30935

test CHANGED
@@ -2,7 +2,11 @@
2
2
 
3
3
 
4
4
 
5
- 方針としては、とにかくpython側で処理してしまうと遅いので、配列ごとnumbaに投げます。numba側のプログラムの書き方は見ての如くです。
5
+ 方針としては、とにかくpython側で処理してしまうと遅いので、配列ごとnumbaに投げます。
6
+
7
+
8
+
9
+ numba側のプログラムの書き方は見ての如くです。CとかFORTRANのノリで書いてください。numpyの関数を呼び出すよりそっちの方が速いのです(新たなnumpy配列を返す関数はメモリ上に新たな配列を作るのですべて本質的には遅いのです)。
6
10
 
7
11
 
8
12
 

5

passよりcontinueの方が意味が明確だし、もしかしたら微妙に最適化されるかもと思って(測った限り効いてない)

2020/04/06 18:30

投稿

hayataka2049
hayataka2049

スコア30935

test CHANGED
@@ -44,7 +44,7 @@
44
44
 
45
45
  if before != 1: # 直前の状態が0なら無視して続ける
46
46
 
47
- pass
47
+ continue
48
48
 
49
49
  else: # 直前の状態が1のとき
50
50
 
@@ -128,7 +128,7 @@
128
128
 
129
129
  if before != 1: # 直前の状態が0なら無視して続ける
130
130
 
131
- pass
131
+ continue
132
132
 
133
133
  else: # 直前の状態が1のとき
134
134
 

4

追記

2020/04/06 18:23

投稿

hayataka2049
hayataka2049

スコア30935

test CHANGED
@@ -92,6 +92,8 @@
92
92
 
93
93
  入力を転置して与えてください。結果も転置されたものが出てきます。
94
94
 
95
+ (転置がビューかコピーかで変わるかな? とも思ったのですが、これで速くなったのでたぶんいいのでしょう)
96
+
95
97
 
96
98
 
97
99
  ```python

3

追記

2020/04/06 18:21

投稿

hayataka2049
hayataka2049

スコア30935

test CHANGED
@@ -163,3 +163,7 @@
163
163
 
164
164
 
165
165
  どちらにしても、処理時間のかなりの割合は1.6GBもある配列の生成で食っています。関数自体は一瞬で返るみたいなので、これでいいでしょう。
166
+
167
+
168
+
169
+ int16やint8にすれば多少速くなりますが、8bitだと128個1が続いただけでオーバーフローなので都合が悪いでしょう。

2

送信エラー

2020/04/06 18:15

投稿

hayataka2049
hayataka2049

スコア30935

test CHANGED
@@ -159,3 +159,7 @@
159
159
 
160
160
 
161
161
  こちらは6秒でした。
162
+
163
+
164
+
165
+ どちらにしても、処理時間のかなりの割合は1.6GBもある配列の生成で食っています。関数自体は一瞬で返るみたいなので、これでいいでしょう。

1

追記

2020/04/06 18:12

投稿

hayataka2049
hayataka2049

スコア30935

test CHANGED
@@ -79,3 +79,83 @@
79
79
 
80
80
 
81
81
  2万の正方行列で10秒くらいでした。
82
+
83
+
84
+
85
+ ---
86
+
87
+
88
+
89
+ 列方向に見ていくのはキャッシュ効率の観点からするとあまり好ましくありません。ということで、同じロジックで列ベクトルではなく行ベクトルを扱うバージョンの関数も作ってみました。
90
+
91
+
92
+
93
+ 入力を転置して与えてください。結果も転置されたものが出てきます。
94
+
95
+
96
+
97
+ ```python
98
+
99
+ @jit("i4[:,:](i4[:,:])", nopython=True)
100
+
101
+ def f_trans(A):
102
+
103
+ B = A.copy()
104
+
105
+ for i in range(B.shape[0]): # 行のループ
106
+
107
+ before = 0
108
+
109
+ start_pos = 0
110
+
111
+ cnt = 0
112
+
113
+ for j in range(B.shape[1]): # 列のループ
114
+
115
+ if B[i, j] == 1: # 1のとき
116
+
117
+ if before == 0: # 直前の状態が0なら1にして数え始める
118
+
119
+ start_pos = j
120
+
121
+ before = 1
122
+
123
+ cnt += 1 # 数える
124
+
125
+ else: # 0のとき
126
+
127
+ if before != 1: # 直前の状態が0なら無視して続ける
128
+
129
+ pass
130
+
131
+ else: # 直前の状態が1のとき
132
+
133
+ for k in range(start_pos, j): # 1が出た範囲をcntで埋める
134
+
135
+ B[i, k] = cnt
136
+
137
+ # 状態をリセットする
138
+
139
+ before = 0
140
+
141
+ cnt = 0
142
+
143
+ # 行が終わって状態が1のとき
144
+
145
+ if before == 1:
146
+
147
+ for k in range(start_pos, B.shape[1]):
148
+
149
+ B[i, k] = cnt
150
+
151
+
152
+
153
+ return B
154
+
155
+
156
+
157
+ ```
158
+
159
+
160
+
161
+ こちらは6秒でした。