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

編集履歴

質問編集履歴

12

s

2020/09/16 15:38

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -19,10 +19,10 @@
19
19
  | | 合計のカウント | 1以上の要素数 | 2以上の要素数 | 2の要素数 |
20
20
  |------------------|---------|---------|---------|--------|
21
21
  | 質問記載コード | 1358ms | 1294ms | 1452ms | 1458ms |
22
- | SHOMI さんのコード | 1074ms (-284ms) | 1215ms (-79ms) | 1280ms (-172ms) | 1256ms (-202ms) |
22
+ | SHOMI さんのコード | 1074ms (-284) | 1215ms (-79) | 1280ms (-172) | 1256ms (-202) |
23
- | kazuma\-sさんのコード | 1068ms (-290ms) | 1140ms (-154ms) | 1137ms (-315ms) | 1144ms (-314ms) |
23
+ | kazuma\-sさんのコード | 1068ms (-290) | 1140ms (-154) | 1137ms (-315) | 1144ms (-314) |
24
- | kazuma\-sさんのコード2 | 978ms (-380ms) | 949ms (-345ms) | 1026ms (-426ms) | 996ms (-462ms) |
24
+ | kazuma\-sさんのコード2 | 978ms (-380) | 949ms (-345) | 1026ms (-426) | 996ms (-462) |
25
- | kichirb3 さんのコード | 957ms (-401ms) | 854ms (-440ms) | 786ms (-666ms) | 986ms (-472ms) |
25
+ | kichirb3 さんのコード | 957ms (-401) | 854ms (-440) | 786ms (-666) | 986ms (-472) |
26
26
 
27
27
  ----
28
28
 

11

d

2020/09/16 15:38

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -3,15 +3,33 @@
3
3
  [ビットカウントの分割統治法](https://www.kaeruspoon.net/articles/720) のようにビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
4
4
  プログラムは C++ で書いており、下記問題を計算する部分の呼び出し回数が多く、ボトルネックとなっているため、少しでも演算回数を減らしたいというのが質問の背景です。
5
5
 
6
- ## 追記 9/16
6
+ ## 追記 9/17
7
7
 
8
- 沢山のご回答、アイデアをいただきありがとうございます。
8
+ 沢山のアイデア、サンプルコードありがとうございます。
9
- 皆さんに回答いただいた内容を理解し、実際に試してみようと思いますが、時間がかかりそうなので、質問のクローズまで何日か時間がかかるかもしれません。
9
+ 実行時間を検証した結果、以下のようになりました。
10
10
 
11
+ * C++17
11
- テストケースとベンチマーク用のコードを作ったのですが、まだ皆さんのコードを試すところまでできていませんが、今日はここまでにします。
12
+ * Visual Studio 2019
12
13
 
13
- * [Gtihub snippets/292090 (作りかけ)](https://github.com/nekobean/snippets/tree/master/292090)
14
+ * [ベンチマーク 検証コード](https://github.com/nekobean/snippets/tree/master/292090)
15
+ * テストケース: 今回解きたい全パターン 40万件弱
16
+ * CPU: Core™ i9-9900K 3.6 GHz
17
+ * 40万件*100回=4000万回の計算時間を算出したら以下のようになりました。
14
18
 
19
+ | | 合計のカウント | 1以上の要素数 | 2以上の要素数 | 2の要素数 |
20
+ |------------------|---------|---------|---------|--------|
21
+ | 質問記載コード | 1358ms | 1294ms | 1452ms | 1458ms |
22
+ | SHOMI さんのコード | 1074ms (-284ms) | 1215ms (-79ms) | 1280ms (-172ms) | 1256ms (-202ms) |
23
+ | kazuma\-sさんのコード | 1068ms (-290ms) | 1140ms (-154ms) | 1137ms (-315ms) | 1144ms (-314ms) |
24
+ | kazuma\-sさんのコード2 | 978ms (-380ms) | 949ms (-345ms) | 1026ms (-426ms) | 996ms (-462ms) |
25
+ | kichirb3 さんのコード | 957ms (-401ms) | 854ms (-440ms) | 786ms (-666ms) | 986ms (-472ms) |
26
+
27
+ ----
28
+
29
+ 皆さんにご回答いただいた内容を理解していこうと思いますが、時間がかかると思うので一旦質問はクローズします。
30
+ 全員 BA としたいのですが仕様上できないので、最初にビット演算のコードを使った回答をしていただいた SHOMI さんを BA に選択します。
31
+ ありがとうございました。d
32
+
15
33
  ## 問題設定
16
34
 
17
35
  各値が **0 ~ 4** である長さが **9** の配列があるとします。

10

環境、言語について補足

2020/09/16 15:37

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -1,5 +1,4 @@
1
1
  ビット列のカウント、比較について、以下の問題の演算回数を削減する方法がもしあれば教えていただきたいです。
2
- サンプルコードが C++/Python ですが、ビット演算はどの言語にもあると思うので、特に言語を限定した質問ではないです。
3
2
 
4
3
  [ビットカウントの分割統治法](https://www.kaeruspoon.net/articles/720) のようにビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
5
4
  プログラムは C++ で書いており、下記問題を計算する部分の呼び出し回数が多く、ボトルネックとなっているため、少しでも演算回数を減らしたいというのが質問の背景です。
@@ -27,6 +26,15 @@
27
26
 
28
27
  例えば、`[0, 2, 0, 2, 2, 1, 1, 1, 4]` の場合、ビット列での表現は `100|001|001|001|010|010|000|010|000` になります。(`|` は区切りがわかりやすいように入れています)
29
28
 
29
+ ## 言語・環境について
30
+
31
+ * 動作環境は **C++17** です。
32
+ * コンパイラは Visual Studio 2019 Update6
33
+ * 今は int (32bit) にビット値を格納しています。28~32bitは未使用で0になっています。
34
+ * 計算量削減以外に C++ に特化した最適化方法のアイデア等でも大丈夫です。
35
+
36
+ サンプルコードが C++/Python ですが、ビット演算はどの言語にもあると思うので、ビット演算を使用した計算法であれば、特に言語を限定した質問ではないです。
37
+
30
38
  ## 質問内容
31
39
 
32
40
  このときにこのビット列から以下を求めたいのですが、サンプルコードのように各ブロックごとに取り出して加算していくやり方しか思いつきません。ビット演算などを活用し、より少ない演算回数で計算できる方法がもしあれば教えていただきたいです。

9

d

2020/09/15 18:48

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -11,7 +11,7 @@
11
11
 
12
12
  テストケースとベンチマーク用のコードを作ったのですが、まだ皆さんのコードを試すところまでできていませんが、今日はここまでにします。
13
13
 
14
- * [Gtihub snippets/292090](https://github.com/nekobean/snippets/tree/master/292090)
14
+ * [Gtihub snippets/292090 (作りかけ)](https://github.com/nekobean/snippets/tree/master/292090)
15
15
 
16
16
  ## 問題設定
17
17
 

8

演算子の優先順位修正

2020/09/15 18:35

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -81,7 +81,7 @@
81
81
  {
82
82
  int cnt = 0;
83
83
  for (int i = 0; i < 9; ++i) {
84
- if ((x >> i * 3) & 0b111 >= 2)
84
+ if (((x >> i * 3) & 0b111) >= 2)
85
85
  cnt++;
86
86
  }
87
87
  std::cout << cnt << std::endl;
@@ -91,7 +91,7 @@
91
91
  {
92
92
  int cnt = 0;
93
93
  for (int i = 0; i < 9; ++i) {
94
- if ((x >> i * 3) & 0b111 == 2)
94
+ if (((x >> i * 3) & 0b111) == 2)
95
95
  cnt++;
96
96
  }
97
97
  std::cout << cnt << std::endl;

7

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

2020/09/15 18:34

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -4,6 +4,15 @@
4
4
  [ビットカウントの分割統治法](https://www.kaeruspoon.net/articles/720) のようにビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
5
5
  プログラムは C++ で書いており、下記問題を計算する部分の呼び出し回数が多く、ボトルネックとなっているため、少しでも演算回数を減らしたいというのが質問の背景です。
6
6
 
7
+ ## 追記 9/16
8
+
9
+ 沢山のご回答、アイデアをいただきありがとうございます。
10
+ 皆さんに回答いただいた内容を理解し、実際に試してみようと思いますが、時間がかかりそうなので、質問のクローズまで何日か時間がかかるかもしれません。
11
+
12
+ テストケースとベンチマーク用のコードを作ったのですが、まだ皆さんのコードを試すところまでできていませんが、今日はここまでにします。
13
+
14
+ * [Gtihub snippets/292090](https://github.com/nekobean/snippets/tree/master/292090)
15
+
7
16
  ## 問題設定
8
17
 
9
18
  各値が **0 ~ 4** である長さが **9** の配列があるとします。

6

d

2020/09/15 18:31

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -1,6 +1,8 @@
1
- ビット列のカウント、比較について、以下の問題をより効率的に計算する方法がもしあれば教えていただきたいです。
1
+ ビット列のカウント、比較について、以下の問題の演算回数を削減する方法がもしあれば教えていただきたいです。
2
+ サンプルコードが C++/Python ですが、ビット演算はどの言語にもあると思うので、特に言語を限定した質問ではないです。
2
3
 
4
+ [ビットカウントの分割統治法](https://www.kaeruspoon.net/articles/720) のようにビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
3
- サンプルコードが Python ですが、ビット演算はどの言語にもあると思うので、特に言語を限定した質問ではないです。(実際は C++ で書いてます。)
5
+ プログラムは C++ で書いており、下記問題を計算する部分の呼び出し回数が多く、ボトルネックとなっているため、少しでも演算回数を減らしたいというのが質問の背景です。
4
6
 
5
7
  ## 問題設定
6
8
 
@@ -19,8 +21,8 @@
19
21
  ## 質問内容
20
22
 
21
23
  このときにこのビット列から以下を求めたいのですが、サンプルコードのように各ブロックごとに取り出して加算していくやり方しか思いつきません。ビット演算などを活用し、より少ない演算回数で計算できる方法がもしあれば教えていただきたいです。
22
- [ビットカウントの分割統治法](https://www.kaeruspoon.net/articles/720) のようにビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
23
24
 
25
+
24
26
  1. 元の配列の各値の合計
25
27
  1. 元の配列の各値が1以上の要素数
26
28
  1. 元の配列の各値が2以上の要素数
@@ -88,6 +90,71 @@
88
90
  }
89
91
  ```
90
92
 
93
+ 少し演算回数を減らしたコード
94
+
95
+ ```cpp
96
+ #include <iostream>
97
+ #include <vector>
98
+
99
+ /**
100
+ * @brief マスク
101
+ */
102
+ const std::vector<int> mask = {
103
+ 7, 7 << 3, 7 << 6, 7 << 9, 7 << 12, 7 << 15, 7 << 18, 7 << 21, 7 << 24,
104
+ };
105
+
106
+ /**
107
+ * @brief 2以上かどうか調べるときのマスク
108
+ */
109
+ const std::vector<int> ge2 = {
110
+ 6, 6 << 3, 6 << 6, 6 << 9, 6 << 12, 6 << 15, 6 << 18, 6 << 21, 6 << 24,
111
+ };
112
+
113
+ int main()
114
+ {
115
+ int x = 69510160;
116
+
117
+ // 各値の合計
118
+ {
119
+ int cnt = 0;
120
+ for (int i = 0; i < 9; ++i)
121
+ cnt += (x >> i * 3) & 0b111;
122
+
123
+ std::cout << cnt << std::endl;
124
+ }
125
+
126
+ // 各値が1以上の要素数
127
+ {
128
+ int cnt = 0;
129
+ for (int i = 0; i < 9; ++i) {
130
+ if (x & mask[i])
131
+ cnt++;
132
+ }
133
+ std::cout << cnt << std::endl;
134
+ }
135
+
136
+ // 各値が2以上の要素数
137
+ {
138
+ int cnt = 0;
139
+ for (int i = 0; i < 9; ++i) {
140
+ if (x & ge2[i])
141
+ cnt++;
142
+ }
143
+ std::cout << cnt << std::endl;
144
+ }
145
+
146
+ // 各値が2の要素数
147
+ {
148
+ int cnt = 0;
149
+ for (int i = 0; i < 9; ++i) {
150
+ if (((x >> i * 3) & 0b111) == 2)
151
+ cnt++;
152
+ }
153
+ std::cout << cnt << std::endl;
154
+ }
155
+ }
156
+ ```
157
+
91
158
  ## Python
92
159
 
93
160
  ```python

5

d

2020/09/15 16:16

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -1,6 +1,6 @@
1
1
  ビット列のカウント、比較について、以下の問題をより効率的に計算する方法がもしあれば教えていただきたいです。
2
2
 
3
- サンプルコードが Python ですが、特に言語を限定した質問ではないです。
3
+ サンプルコードが Python ですが、ビット演算はどの言語にもあると思うので、特に言語を限定した質問ではないです。(実際は C++ で書いてます。)
4
4
 
5
5
  ## 問題設定
6
6
 
@@ -19,7 +19,7 @@
19
19
  ## 質問内容
20
20
 
21
21
  このときにこのビット列から以下を求めたいのですが、サンプルコードのように各ブロックごとに取り出して加算していくやり方しか思いつきません。ビット演算などを活用し、より少ない演算回数で計算できる方法がもしあれば教えていただきたいです。
22
- ビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
22
+ [ビットカウントの分割統治法](https://www.kaeruspoon.net/articles/720) のようにビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
23
23
 
24
24
  1. 元の配列の各値の合計
25
25
  1. 元の配列の各値が1以上の要素数

4

d

2020/09/15 15:28

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -38,7 +38,7 @@
38
38
  1. 元の配列の各値が2以上の要素数: 4
39
39
  1. 元の配列の各値が2の要素数: 3
40
40
 
41
- ## コード
41
+ ## C++
42
42
 
43
43
  ```cpp
44
44
  #include <iostream>
@@ -88,6 +88,8 @@
88
88
  }
89
89
  ```
90
90
 
91
+ ## Python
92
+
91
93
  ```python
92
94
  from functools import reduce
93
95
 

3

d

2020/09/15 15:23

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -40,6 +40,54 @@
40
40
 
41
41
  ## コード
42
42
 
43
+ ```cpp
44
+ #include <iostream>
45
+
46
+ int main()
47
+ {
48
+ int x = 69510160;
49
+
50
+ // 各値の合計
51
+ {
52
+ int cnt = 0;
53
+ for (int i = 0; i < 9; ++i)
54
+ cnt += (x >> i * 3) & 0b111;
55
+
56
+ std::cout << cnt << std::endl;
57
+ }
58
+
59
+ // 各値が1以上の要素数
60
+ {
61
+ int cnt = 0;
62
+ for (int i = 0; i < 9; ++i) {
63
+ if ((x >> i * 3) & 0b111)
64
+ cnt++;
65
+ }
66
+ std::cout << cnt << std::endl;
67
+ }
68
+
69
+ // 各値が2以上の要素数
70
+ {
71
+ int cnt = 0;
72
+ for (int i = 0; i < 9; ++i) {
73
+ if ((x >> i * 3) & 0b111 >= 2)
74
+ cnt++;
75
+ }
76
+ std::cout << cnt << std::endl;
77
+ }
78
+
79
+ // 各値が2の要素数
80
+ {
81
+ int cnt = 0;
82
+ for (int i = 0; i < 9; ++i) {
83
+ if ((x >> i * 3) & 0b111 == 2)
84
+ cnt++;
85
+ }
86
+ std::cout << cnt << std::endl;
87
+ }
88
+ }
89
+ ```
90
+
43
91
  ```python
44
92
  from functools import reduce
45
93
 

2

d

2020/09/15 15:20

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -19,6 +19,7 @@
19
19
  ## 質問内容
20
20
 
21
21
  このときにこのビット列から以下を求めたいのですが、サンプルコードのように各ブロックごとに取り出して加算していくやり方しか思いつきません。ビット演算などを活用し、より少ない演算回数で計算できる方法がもしあれば教えていただきたいです。
22
+ ビット演算を活用してなにか上手くできないかと考えているのですが、なかなか思いつきません。
22
23
 
23
24
  1. 元の配列の各値の合計
24
25
  1. 元の配列の各値が1以上の要素数
@@ -28,6 +29,8 @@
28
29
  * どれか1つだけでもよいです。
29
30
  * コードでなくとも、アイデアだけでも助かります。
30
31
 
32
+ ----
33
+
31
34
  例: `[0, 2, 0, 2, 2, 1, 1, 1, 4]` (`69510160`)の場合
32
35
 
33
36
  1. 元の配列の各値の合計: 13

1

d

2020/09/15 14:45

投稿

tiitoi
tiitoi

スコア21960

title CHANGED
File without changes
body CHANGED
@@ -20,17 +20,20 @@
20
20
 
21
21
  このときにこのビット列から以下を求めたいのですが、サンプルコードのように各ブロックごとに取り出して加算していくやり方しか思いつきません。ビット演算などを活用し、より少ない演算回数で計算できる方法がもしあれば教えていただきたいです。
22
22
 
23
- * 元の配列の各値の合計
23
+ 1. 元の配列の各値の合計
24
- * 元の配列の各値が1以上の要素数
24
+ 1. 元の配列の各値が1以上の要素数
25
- * 元の配列の各値が2以上の要素数
25
+ 1. 元の配列の各値が2以上の要素数
26
- * 元の配列の各値が2の要素数
26
+ 1. 元の配列の各値が2の要素数
27
27
 
28
+ * どれか1つだけでもよいです。
29
+ * コードでなくとも、アイデアだけでも助かります。
30
+
28
31
  例: `[0, 2, 0, 2, 2, 1, 1, 1, 4]` (`69510160`)の場合
29
32
 
30
- * 元の配列の各値の合計: 13
33
+ 1. 元の配列の各値の合計: 13
31
- * 元の配列の各値が1以上の要素数: 7
34
+ 1. 元の配列の各値が1以上の要素数: 7
32
- * 元の配列の各値が2以上の要素数: 4
35
+ 1. 元の配列の各値が2以上の要素数: 4
33
- * 元の配列の各値が2の要素数: 3
36
+ 1. 元の配列の各値が2の要素数: 3
34
37
 
35
38
  ## コード
36
39