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

Question

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

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

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

我想要代表 A 和 B 的位集(列 vector V)。

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

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

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

我试图避免遍历每个集合的每个元素，而是通过对位行求和来获取出现次数，但我不知道如何以高效的方式优雅地进行此转换。

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

Answer 1

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

简而言之，你已经

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

然后你就得到了

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

这样unsortedDataInRow[sortedIndices[i]]已排序。但不是 build 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 比通过 counts[labels[i]]++; 更快地完成)比您执行上述操作的频率要高得多。

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