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

我看到了一些关于这个话题的类似问题，但我对编程还比较新手，无法理解一些解决方案中使用的语言。

假设我有两个有限集合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决策树算法，并试图使用位向量来计算标签的比例以进行熵计算。

回答：

演示的关键在于，你不是为了构建位集而显式地形成这些集合，而是直接构建位集来替代集合。

简而言之，你有

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));// 这会初始化为零

以便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。你必须希望你的编译器能识别手写的popcnt。或者，使用boost::dynamic_bitset，或其他库，或手写的版本。

学技术