将整数数组转换为 C++ 中的位集表示的最佳方法？

Question

我看过一些关于该主题的类似问题，但我对编程还比较陌生，无法理解解决方案中使用的某些语言。

假设我有 2 个有限集 A、B 表示为数组，其中：

int A[2] = {1, 3};
int B[2] = {1, 2};

我想要代表 A 和 B 的位集（列向量 V）。

    v1 v2
(1) 1, 1
(2) 0, 1
(3) 1, 0

这样我就可以轻松地对行 (k) 求和，并得到值 k 在我的所有集合 A_1 到 A_n 中出现的次数。

我正在寻找最快的方法来做到这一点。我可以粗略地想象我如何首先初始化一个位向量矩阵（将每个值设置为 0），然后循环遍历每个集合 A_i，将我的矩阵的相应条目设置为 1，但是这个解决方案似乎没有用，因为我仍然必须遍历每个集合中的每个元素 A_i.

我试图通过对位行求和来获取出现次数，从而避免遍历每个集合的每个元素，但我无法弄清楚如何以省时的方式优雅地进行此转换.

动机：我正在尝试实现ID3决策树算法，并尝试使用位向量来计算标签的比例以进行熵计算。

Answer 1

演示文稿中的关键是您没有明确地形成集合只是为了从中构建位集，而是构造位集而不是集合的。

简而言之，你有

std::vector<double> unsortedDataInRow(numDataInRow) = ...;
std::vector<int> labels(numLabels) = ...;

然后你获得

std::vector<unsigned> sortedIndices = getSortedIndices(unsortedDataInRow);

这样 unsortedDataInRow[sortedIndices[i]] 就可以排序了。但不是从它们构建 std::vector<int> sortedLabels，而是填充

std::vector<std::vector<bool>> bitsets(numLabels, std::vector<bool>(numDataInRow));
// this gets zero-initialized

这样 bitsets[label][i] == (unsortedLabels[sortedIndices[i]] == label):

for (auto sortedIndex : sortedIndices)
  bitsets[unsortedLabels[sortedIndices]][sortedIndex] = true;

这有助于提高性能，因为您（大概）在 InfoGain 中进行标签计数（即确定 P(c)，然后通过 popcnt 比通过 [=20] 可以更快地完成=]) 比你做上面的更频繁。

请注意，这只是一个草图 - std::vector<bool> 没有获取 popcnt 的内置方法。您必须希望您的编译器能够识别手写的。或者，使用 boost::dynamic_bitset 或其他一些库，或手写库。

Best way to transform an array of ints into a bitset representation in C++?