teratail
回答率
85.48%
質問するログイン新規登録
トップに関する質問ビット列のカウント、比較方法について

編集履歴

質問編集履歴

12

s

2020/09/16 15:38

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -40,13 +40,13 @@
40
40
 
41
41
  | 質問記載コード | 1358ms | 1294ms | 1452ms | 1458ms |
42
42
 
43
- | SHOMI さんのコード | 1074ms (-284ms) | 1215ms (-79ms) | 1280ms (-172ms) | 1256ms (-202ms) |
43
+ | SHOMI さんのコード | 1074ms (-284) | 1215ms (-79) | 1280ms (-172) | 1256ms (-202) |
44
-
44
+
45
- | kazuma\-sさんのコード | 1068ms (-290ms) | 1140ms (-154ms) | 1137ms (-315ms) | 1144ms (-314ms) |
45
+ | kazuma\-sさんのコード | 1068ms (-290) | 1140ms (-154) | 1137ms (-315) | 1144ms (-314) |
46
-
46
+
47
- | kazuma\-sさんのコード2 | 978ms (-380ms) | 949ms (-345ms) | 1026ms (-426ms) | 996ms (-462ms) |
47
+ | kazuma\-sさんのコード2 | 978ms (-380) | 949ms (-345) | 1026ms (-426) | 996ms (-462) |
48
-
48
+
49
- | kichirb3 さんのコード | 957ms (-401ms) | 854ms (-440ms) | 786ms (-666ms) | 986ms (-472ms) |
49
+ | kichirb3 さんのコード | 957ms (-401) | 854ms (-440) | 786ms (-666) | 986ms (-472) |
50
50
 
51
51
 
52
52
 

11

d

2020/09/16 15:38

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -8,21 +8,57 @@
8
8
 
9
9
 
10
10
 
11
- ## 追記 9/16
11
+ ## 追記 9/17
12
-
13
-
14
-
12
+
13
+
14
+
15
- 沢山のご回答、アイデアをいただきありがとうございます。
15
+ 沢山のアイデア、サンプルコードありがとうございます。
16
-
17
- 皆さんに回答いただいた内容を理解し、実際に試してみようと思いますが、時間がかかりそうなので、質問のクローズまで何日か時間がかかるかもしれません。
16
+
18
-
19
-
20
-
21
- テストケースとベンチマーク用のコードを作ったのですが、まだ皆さんのコードを試すところまでできていませんが、今日はここまでにします。
17
+ 実行時間を検証した結果、以下のようになりました。
18
+
19
+
20
+
22
-
21
+ * C++17
22
+
23
-
23
+ * Visual Studio 2019
24
-
24
+
25
+
26
+
25
- * [Gtihub snippets/292090 (作りかけ)](https://github.com/nekobean/snippets/tree/master/292090)
27
+ * [ベンチマーク 検証コード](https://github.com/nekobean/snippets/tree/master/292090)
28
+
29
+ * テストケース: 今回解きたい全パターン 40万件弱
30
+
31
+ * CPU: Core™ i9-9900K 3.6 GHz
32
+
33
+ * 40万件*100回=4000万回の計算時間を算出したら以下のようになりました。
34
+
35
+
36
+
37
+ | | 合計のカウント | 1以上の要素数 | 2以上の要素数 | 2の要素数 |
38
+
39
+ |------------------|---------|---------|---------|--------|
40
+
41
+ | 質問記載コード | 1358ms | 1294ms | 1452ms | 1458ms |
42
+
43
+ | SHOMI さんのコード | 1074ms (-284ms) | 1215ms (-79ms) | 1280ms (-172ms) | 1256ms (-202ms) |
44
+
45
+ | kazuma\-sさんのコード | 1068ms (-290ms) | 1140ms (-154ms) | 1137ms (-315ms) | 1144ms (-314ms) |
46
+
47
+ | kazuma\-sさんのコード2 | 978ms (-380ms) | 949ms (-345ms) | 1026ms (-426ms) | 996ms (-462ms) |
48
+
49
+ | kichirb3 さんのコード | 957ms (-401ms) | 854ms (-440ms) | 786ms (-666ms) | 986ms (-472ms) |
50
+
51
+
52
+
53
+ ----
54
+
55
+
56
+
57
+ 皆さんにご回答いただいた内容を理解していこうと思いますが、時間がかかると思うので一旦質問はクローズします。
58
+
59
+ 全員 BA としたいのですが仕様上できないので、最初にビット演算のコードを使った回答をしていただいた SHOMI さんを BA に選択します。
60
+
61
+ ありがとうございました。d
26
62
 
27
63
 
28
64
 

10

環境、言語について補足

2020/09/16 15:37

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -1,7 +1,5 @@
1
1
  ビット列のカウント、比較について、以下の問題の演算回数を削減する方法がもしあれば教えていただきたいです。
2
2
 
3
- サンプルコードが C++/Python ですが、ビット演算はどの言語にもあると思うので、特に言語を限定した質問ではないです。
4
-
5
3
 
6
4
 
7
5
  [ビットカウントの分割統治法](https://www.kaeruspoon.net/articles/720) のようにビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
@@ -56,6 +54,24 @@
56
54
 
57
55
 
58
56
 
57
+ ## 言語・環境について
58
+
59
+
60
+
61
+ * 動作環境は **C++17** です。
62
+
63
+ * コンパイラは Visual Studio 2019 Update6
64
+
65
+ * 今は int (32bit) にビット値を格納しています。28~32bitは未使用で0になっています。
66
+
67
+ * 計算量削減以外に C++ に特化した最適化方法のアイデア等でも大丈夫です。
68
+
69
+
70
+
71
+ サンプルコードが C++/Python ですが、ビット演算はどの言語にもあると思うので、ビット演算を使用した計算法であれば、特に言語を限定した質問ではないです。
72
+
73
+
74
+
59
75
  ## 質問内容
60
76
 
61
77
 

9

d

2020/09/15 18:48

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -24,7 +24,7 @@
24
24
 
25
25
 
26
26
 
27
- * [Gtihub snippets/292090](https://github.com/nekobean/snippets/tree/master/292090)
27
+ * [Gtihub snippets/292090 (作りかけ)](https://github.com/nekobean/snippets/tree/master/292090)
28
28
 
29
29
 
30
30
 

8

演算子の優先順位修正

2020/09/15 18:35

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -164,7 +164,7 @@
164
164
 
165
165
  for (int i = 0; i < 9; ++i) {
166
166
 
167
- if ((x >> i * 3) & 0b111 >= 2)
167
+ if (((x >> i * 3) & 0b111) >= 2)
168
168
 
169
169
  cnt++;
170
170
 
@@ -184,7 +184,7 @@
184
184
 
185
185
  for (int i = 0; i < 9; ++i) {
186
186
 
187
- if ((x >> i * 3) & 0b111 == 2)
187
+ if (((x >> i * 3) & 0b111) == 2)
188
188
 
189
189
  cnt++;
190
190
 

7

追記及び指摘いただいたバグ修正

2020/09/15 18:34

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -10,6 +10,24 @@
10
10
 
11
11
 
12
12
 
13
+ ## 追記 9/16
14
+
15
+
16
+
17
+ 沢山のご回答、アイデアをいただきありがとうございます。
18
+
19
+ 皆さんに回答いただいた内容を理解し、実際に試してみようと思いますが、時間がかかりそうなので、質問のクローズまで何日か時間がかかるかもしれません。
20
+
21
+
22
+
23
+ テストケースとベンチマーク用のコードを作ったのですが、まだ皆さんのコードを試すところまでできていませんが、今日はここまでにします。
24
+
25
+
26
+
27
+ * [Gtihub snippets/292090](https://github.com/nekobean/snippets/tree/master/292090)
28
+
29
+
30
+
13
31
  ## 問題設定
14
32
 
15
33
 

6

d

2020/09/15 18:31

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -1,8 +1,12 @@
1
- ビット列のカウント、比較について、以下の問題をより効率的に計算する方法がもしあれば教えていただきたいです。
1
+ ビット列のカウント、比較について、以下の問題の演算回数を削減する方法がもしあれば教えていただきたいです。
2
-
3
-
4
-
2
+
5
- サンプルコードが Python ですが、ビット演算はどの言語にもあると思うので、特に言語を限定した質問ではないです。(実際は C++ で書いてます。)
3
+ サンプルコードが C++/Python ですが、ビット演算はどの言語にもあると思うので、特に言語を限定した質問ではないです。
4
+
5
+
6
+
7
+ [ビットカウントの分割統治法](https://www.kaeruspoon.net/articles/720) のようにビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
8
+
9
+ プログラムは C++ で書いており、下記問題を計算する部分の呼び出し回数が多く、ボトルネックとなっているため、少しでも演算回数を減らしたいというのが質問の背景です。
6
10
 
7
11
 
8
12
 
@@ -40,7 +44,7 @@
40
44
 
41
45
  このときにこのビット列から以下を求めたいのですが、サンプルコードのように各ブロックごとに取り出して加算していくやり方しか思いつきません。ビット演算などを活用し、より少ない演算回数で計算できる方法がもしあれば教えていただきたいです。
42
46
 
43
- [ビットカウントの分割統治法](https://www.kaeruspoon.net/articles/720) のようにビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
47
+
44
48
 
45
49
 
46
50
 
@@ -178,6 +182,136 @@
178
182
 
179
183
 
180
184
 
185
+ 少し演算回数を減らしたコード
186
+
187
+
188
+
189
+ ```cpp
190
+
191
+ #include <iostream>
192
+
193
+ #include <vector>
194
+
195
+
196
+
197
+ /**
198
+
199
+ * @brief マスク
200
+
201
+ */
202
+
203
+ const std::vector<int> mask = {
204
+
205
+ 7, 7 << 3, 7 << 6, 7 << 9, 7 << 12, 7 << 15, 7 << 18, 7 << 21, 7 << 24,
206
+
207
+ };
208
+
209
+
210
+
211
+ /**
212
+
213
+ * @brief 2以上かどうか調べるときのマスク
214
+
215
+ */
216
+
217
+ const std::vector<int> ge2 = {
218
+
219
+ 6, 6 << 3, 6 << 6, 6 << 9, 6 << 12, 6 << 15, 6 << 18, 6 << 21, 6 << 24,
220
+
221
+ };
222
+
223
+
224
+
225
+ int main()
226
+
227
+ {
228
+
229
+ int x = 69510160;
230
+
231
+
232
+
233
+ // 各値の合計
234
+
235
+ {
236
+
237
+ int cnt = 0;
238
+
239
+ for (int i = 0; i < 9; ++i)
240
+
241
+ cnt += (x >> i * 3) & 0b111;
242
+
243
+
244
+
245
+ std::cout << cnt << std::endl;
246
+
247
+ }
248
+
249
+
250
+
251
+ // 各値が1以上の要素数
252
+
253
+ {
254
+
255
+ int cnt = 0;
256
+
257
+ for (int i = 0; i < 9; ++i) {
258
+
259
+ if (x & mask[i])
260
+
261
+ cnt++;
262
+
263
+ }
264
+
265
+ std::cout << cnt << std::endl;
266
+
267
+ }
268
+
269
+
270
+
271
+ // 各値が2以上の要素数
272
+
273
+ {
274
+
275
+ int cnt = 0;
276
+
277
+ for (int i = 0; i < 9; ++i) {
278
+
279
+ if (x & ge2[i])
280
+
281
+ cnt++;
282
+
283
+ }
284
+
285
+ std::cout << cnt << std::endl;
286
+
287
+ }
288
+
289
+
290
+
291
+ // 各値が2の要素数
292
+
293
+ {
294
+
295
+ int cnt = 0;
296
+
297
+ for (int i = 0; i < 9; ++i) {
298
+
299
+ if (((x >> i * 3) & 0b111) == 2)
300
+
301
+ cnt++;
302
+
303
+ }
304
+
305
+ std::cout << cnt << std::endl;
306
+
307
+ }
308
+
309
+ }
310
+
311
+ ```
312
+
313
+
314
+
181
315
  ## Python
182
316
 
183
317
 

5

d

2020/09/15 16:16

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -2,7 +2,7 @@
2
2
 
3
3
 
4
4
 
5
- サンプルコードが Python ですが、特に言語を限定した質問ではないです。
5
+ サンプルコードが Python ですが、ビット演算はどの言語にもあると思うので、特に言語を限定した質問ではないです。(実際は C++ で書いてます。)
6
6
 
7
7
 
8
8
 
@@ -40,7 +40,7 @@
40
40
 
41
41
  このときにこのビット列から以下を求めたいのですが、サンプルコードのように各ブロックごとに取り出して加算していくやり方しか思いつきません。ビット演算などを活用し、より少ない演算回数で計算できる方法がもしあれば教えていただきたいです。
42
42
 
43
- ビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
43
+ [ビットカウントの分割統治法](https://www.kaeruspoon.net/articles/720) のようにビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
44
44
 
45
45
 
46
46
 

4

d

2020/09/15 15:28

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -78,7 +78,7 @@
78
78
 
79
79
 
80
80
 
81
- ## コード
81
+ ## C++
82
82
 
83
83
 
84
84
 
@@ -178,6 +178,10 @@
178
178
 
179
179
 
180
180
 
181
+ ## Python
182
+
183
+
184
+
181
185
  ```python
182
186
 
183
187
  from functools import reduce

3

d

2020/09/15 15:23

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -82,6 +82,102 @@
82
82
 
83
83
 
84
84
 
85
+ ```cpp
86
+
87
+ #include <iostream>
88
+
89
+
90
+
91
+ int main()
92
+
93
+ {
94
+
95
+ int x = 69510160;
96
+
97
+
98
+
99
+ // 各値の合計
100
+
101
+ {
102
+
103
+ int cnt = 0;
104
+
105
+ for (int i = 0; i < 9; ++i)
106
+
107
+ cnt += (x >> i * 3) & 0b111;
108
+
109
+
110
+
111
+ std::cout << cnt << std::endl;
112
+
113
+ }
114
+
115
+
116
+
117
+ // 各値が1以上の要素数
118
+
119
+ {
120
+
121
+ int cnt = 0;
122
+
123
+ for (int i = 0; i < 9; ++i) {
124
+
125
+ if ((x >> i * 3) & 0b111)
126
+
127
+ cnt++;
128
+
129
+ }
130
+
131
+ std::cout << cnt << std::endl;
132
+
133
+ }
134
+
135
+
136
+
137
+ // 各値が2以上の要素数
138
+
139
+ {
140
+
141
+ int cnt = 0;
142
+
143
+ for (int i = 0; i < 9; ++i) {
144
+
145
+ if ((x >> i * 3) & 0b111 >= 2)
146
+
147
+ cnt++;
148
+
149
+ }
150
+
151
+ std::cout << cnt << std::endl;
152
+
153
+ }
154
+
155
+
156
+
157
+ // 各値が2の要素数
158
+
159
+ {
160
+
161
+ int cnt = 0;
162
+
163
+ for (int i = 0; i < 9; ++i) {
164
+
165
+ if ((x >> i * 3) & 0b111 == 2)
166
+
167
+ cnt++;
168
+
169
+ }
170
+
171
+ std::cout << cnt << std::endl;
172
+
173
+ }
174
+
175
+ }
176
+
177
+ ```
178
+
179
+
180
+
85
181
  ```python
86
182
 
87
183
  from functools import reduce

2

d

2020/09/15 15:20

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -40,6 +40,8 @@
40
40
 
41
41
  このときにこのビット列から以下を求めたいのですが、サンプルコードのように各ブロックごとに取り出して加算していくやり方しか思いつきません。ビット演算などを活用し、より少ない演算回数で計算できる方法がもしあれば教えていただきたいです。
42
42
 
43
+ ビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
44
+
43
45
 
44
46
 
45
47
  1. 元の配列の各値の合計
@@ -55,6 +57,10 @@
55
57
  * どれか1つだけでもよいです。
56
58
 
57
59
  * コードでなくとも、アイデアだけでも助かります。
60
+
61
+
62
+
63
+ ----
58
64
 
59
65
 
60
66
 

1

d

2020/09/15 14:45

投稿

tiitoi
tiitoi

スコア21956

test CHANGED
File without changes
test CHANGED
@@ -42,13 +42,19 @@
42
42
 
43
43
 
44
44
 
45
- * 元の配列の各値の合計
45
+ 1. 元の配列の各値の合計
46
46
 
47
- * 元の配列の各値が1以上の要素数
47
+ 1. 元の配列の各値が1以上の要素数
48
48
 
49
- * 元の配列の各値が2以上の要素数
49
+ 1. 元の配列の各値が2以上の要素数
50
50
 
51
- * 元の配列の各値が2の要素数
51
+ 1. 元の配列の各値が2の要素数
52
+
53
+
54
+
55
+ * どれか1つだけでもよいです。
56
+
57
+ * コードでなくとも、アイデアだけでも助かります。
52
58
 
53
59
 
54
60
 
@@ -56,13 +62,13 @@
56
62
 
57
63
 
58
64
 
59
- * 元の配列の各値の合計: 13
65
+ 1. 元の配列の各値の合計: 13
60
66
 
61
- * 元の配列の各値が1以上の要素数: 7
67
+ 1. 元の配列の各値が1以上の要素数: 7
62
68
 
63
- * 元の配列の各値が2以上の要素数: 4
69
+ 1. 元の配列の各値が2以上の要素数: 4
64
70
 
65
- * 元の配列の各値が2の要素数: 3
71
+ 1. 元の配列の各値が2の要素数: 3
66
72
 
67
73
 
68
74