Продукт Fast Dot для особого случая

Question

Учитывая вектор X размера L, где каждый скалярный элемент X взят из двоичного набора {0,1}, найти произведение точки z = точка (X, Y), если вектор Y размера L состоит целочисленных элементов. Я полагаю, должен существовать очень быстрый способ сделать это.

Допустим, у нас есть L=4; X[L]={1, 0, 0, 1}; Y[L]={-4, 2, 1, 0}, и мы должны найти z=X[0]*Y[0] + X[1]*Y[1] + X[2]*Y[2] + X[3]*Y[3] (что в этом случае даст нам -4).

Очевидно, что X можно представить с помощью двоичных цифр, например, целочисленный тип int32 для L = 32. Затем все, что нам нужно сделать, это найти точечное произведение этого целого числа с массивом из 32 целых чисел. У вас есть идеи или предложения, как это сделать очень быстро?

Answer 1

Вероятно, нет общего ответа на этот вопрос.Вы должны профилировать свой код под всеми различными целями.Производительность будет зависеть от оптимизаций компилятора, таких как разматывание цикла и инструкции SIMD, которые доступны на большинстве современных процессоров (x86, PPC, ARM имеют собственные реализации).

Answer 2

Представляет X, используя связанный список мест, где x[i] = 1. Чтобы найти нужную сумму, вам нужно O(N) операций, где N - размер вашего списка.

Answer 3

Что ж, вы хотите, чтобы все биты прошли, если его 1, и ни одного, если его 0. Таким образом, вы хотите каким-то образом превратить 1 в -1 (то есть 0xffffffff), а 0 остается неизменным. Вот только -X .... так ты и делаешь ...

Y & (-X)

для каждого элемента ... работа выполнена?

Edit2: чтобы дать пример кода, вы можете сделать что-то вроде этого и избежать ветки:

int result=0;
for ( int i = 0; i < L; i++ )
{
   result+=Y[i] & -(int)((X >> i) & 1);
}

Конечно, лучше всего хранить 1 и 0 в массиве целых чисел и избегать сдвигов.

Редактировать: Стоит также отметить, что если значения в Y имеют размер 16 бит, то вы можете выполнить 2 из них и операций за операцию (4, если у вас есть 64-битные регистры). Тем не менее, это означает отрицание значений X 1 на 1 в большее целое число.

то есть YVals = -4, 3 в 16-битном = 0xFFFC, 0x3 ... положить в 1 32-битный и вы получите 0xFFFC0003. Если у вас есть 1, 0 в качестве значений X, тогда вы формируете битовую маску 0xFFFF0000 и 2 вместе, и у вас есть 2 результата в 1 поразрядно, и операция.

Другое редактирование:

ЕСЛИ вам нужен код о том, как сделать 2-й метод что-то вроде , это должно сработать (Хотя оно использует неуказанное поведение, поэтому оно может работать не на каждом компиляторе ... работает на каждом компиляторе, который я '' хотя попадаюсь)

union int1632
{
     int32_t i32;
     int16_t i16[2];
};

int result=0;
for ( int i = 0; i < (L & ~0x1); i += 2 )
{
    int3264 y3264;
    y3264.i16[0] = Y[i + 0];
    y3264.i16[1] = Y[i + 1];

    int3264 x3264;
    x3264.i16[0] = -(int16_t)((X >> (i + 0)) & 1);
    x3264.i16[1] = -(int16_t)((X >> (i + 1)) & 1);

    int3264 res3264;
    res3264.i32  = y3264.i32 & x3264.i32;

    result += res3264.i16[0] + res3264.i16[1];    
}

if ( i < L )
    result+=Y[i] & -(int)((X >> i) & 1);

Надеюсь, компилятор оптимизирует присвоения (Сверху головы, я не уверен, но идея может быть переработана так, чтобы они точно были), и даст вам небольшое ускорение в том, что вам теперь нужно только сделать 1 поразрядно - а не 2. Ускорение было бы незначительным, хотя ...

Answer 4

Вы можете сохранить свой битовый вектор в виде последовательности целых чисел, где каждый int упаковывает пару коэффициентов в биты. Затем, компонентное умножение эквивалентно битам и. При этом вам просто нужно посчитать количество установленных битов, которое можно сделать так:

inline int count(uint32_t x) {
    // see link
}

int dot(uint32_t a, uint32_t b) {
    return count(a & b);
}

Чтобы получить информацию о том, как подсчитать биты, см. http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

Редактировать: Извините, я только что понял, что только один из векторов содержит элементы {0,1}, а другой нет. Этот ответ применим только к случаю, когда оба вектора ограничены коэффициентами из набора {0,1}.