Лучший способ преобразовать массив целых чисел в представление битов в C ++? - PullRequest
Новая
       93

Лучший способ преобразовать массив целых чисел в представление битов в C ++?

2 голосов
/ 23 января 2020

Я видел некоторые похожие вопросы по теме c, но я относительно новичок в программировании и не могу понять какой-то язык, используемый в решениях.

Предположим, у меня есть 2 конечных набора A, B представлены в виде массивов, где: 

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

Мне нужны наборы битов (векторы столбцов V), которые представляют A и B. 

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

Таким образом, я могу легко суммировать row (k) и получить количество появлений для значения k во всех моих наборах от A_1 до A_n.

Я ищу самый быстрый способ сделать это. Я могу приблизительно представить, как я мог бы сначала инициализировать матрицу битовых векторов (устанавливая каждое значение в 0), а затем l oop через каждый набор A_i, устанавливая соответствующую запись моей матрицы в 1, но это решение кажется бесполезным, потому что я все еще приходится l oop через каждый элемент в каждом наборе A_i.

Я пытаюсь избежать необходимости l oop через каждый элемент каждого набора, вместо этого получая количество появлений путем суммирования строк битов , но я не могу понять, как элегантно сделать это преобразование эффективным по времени способом.

Мотивация: я пытаюсь реализовать алгоритм дерева решений ID3 и пытаюсь использовать битовые векторы для вычисления пропорций метки для расчета энтропии.

1 Ответ

2 голосов
/ 23 января 2020

Ключевым моментом в презентации является то, что вы явно не формируете наборы только для создания из них наборов битов, а создаете наборы вместо наборов.

Короче говоря, вы иметь 

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, чем через counts[labels[i]]++;) гораздо чаще, чем вы делаете выше.

Обратите внимание, что это просто эскиз - у std::vector<bool> нет встроенного способа получить popcnt. Вы должны надеяться, что ваш компилятор распознает рукописный. Либо используйте boost::dynamic_bitset, либо другую библиотеку, либо рукописную.

...