Самый быстрый способ проверить C# BitArray на ненулевое значение

Я пытаюсь быстро обнаружить коллизии между BitArrays в С# (используя логическую операцию AND), в результате чего один BitArray представляет перекрывающуюся область.

Очевидно, что если результирующий массив состоит только из нулей, коллизии нет. Как это проверить быстрее всего? Простая итерация слишком медленная. Меня не волнует, где коллизии и сколько их — только то, что где-то в массиве есть ненулевое значение.

Кажется, должен быть какой-то быстрый случай, например, «приведение всего битового массива к значению int» (что конкретно не сработает, потому что BitArrays имеют переменный размер), но я не могу его понять.


arrays c# algorithm collision bitarray
person Brent Sodman    schedule 13.02.2016    source источник
comment
Рассматривали ли вы возможность не использовать BitArrays и вместо этого использовать только int?   -  person itsme86    schedule 13.02.2016
comment
Если вы реализуете это самостоятельно, вы также можете избежать вычисления всего пересечения в случае коллизии, и для хранения пересечения не требуется места. BitArray в любом случае довольно медленная реализация.   -  person harold    schedule 13.02.2016
comment
Хорошие идеи от всех. Спасибо за помощь!   -  person Brent Sodman    schedule 14.02.2016

Ответы (1)


arrow_upward
0
arrow_downward

Вам нужен результирующий BitArray метода And()? Если нет, вы можете просто перебрать входные массивы и вернуть true при первом столкновении.

bool collision(BitArray a1, BitArray a2) {
   if (a1 == null || a2 == null) throw new ArgumentException("arguments cannot be null");
   if (a1.Count != a2.Count) throw new ArgumentException("arrays don't have same length");
   for (int i = 0; i < a1.Count; i++)
       if (a1[i] && a2[i]) return true;

   return false;
}

Таким образом, вы предотвращаете зацикливание массива дважды, т.е. один раз для And() и один раз для проверки. В среднем вы пройдете только половину массива один раз, что ускорит работу до 4 раз.

Другой способ. например, @itsme86 предложил использовать целые числа вместо BitArrays

int a1, a2;
bool collision = (a1 & a2) > 0;
person derpirscher    schedule 13.02.2016
comment
Я бы предложил (a1 & a2) != 0, что даст вам 32 полезных бита вместо 31. - person harold; 13.02.2016
comment
Я бы предложил использовать Enumerable.Zip(a1, a2, (l, r) => l & r).All(x => x > 0). - person Aron; 13.02.2016
comment
@harold: хороший момент, в зависимости от количества необходимых битов можно также использовать UInt64 - person derpirscher; 13.02.2016
comment
@ Арон, боже, нет. Весь смысл этого вопроса заключался в эффективности. - person harold; 13.02.2016
comment
@Aron, есть некоторые проблемы с вашим фрагментом: 1. BitArray не реализует System.Collections.Generic.IEnumerable, поэтому его нельзя использовать с Enumerable.Zip 2. Элементы BitArrays являются логическими, поэтому All(x => x>0) не компилируется - person derpirscher; 13.02.2016
comment
@гарольд нет. Суть вопроса была в скорости. Относительно легко добавить старую добрую распараллеливание... - person Aron; 13.02.2016
comment
@ Арон, конечно, вы можете сделать это медленно, а затем сделать его параллельным, но вы также можете сделать это быстро и все еще сделать его параллельным. Нет смысла делать это медленно намеренно. - person harold; 13.02.2016
comment
@harold Я также хотел бы посмотреть, откуда у вас это замедление ... помните, что это все-таки JITed .. - person Aron; 13.02.2016
comment
@Aron, потому что он JIT для замедления кода. LINQ делает это. Приятно писать однострочники, не очень хорошо для производительности. - person harold; 13.02.2016
comment
@harold Код, который я дал, должен отличаться только тем, что в нем больше вызовов функций и v-lookups. Если JITer выполнил свою работу правильно, он должен встроить эти вызовы функций. Поэтому я еще раз спрашиваю, где ваши доказательства медлительности? - person Aron; 13.02.2016
comment
@Aron и третья проблема: он не выполняет исходную задачу, потому что - если он скомпилируется - он проверяет, являются ли ВСЕ элементы коллизиями. - person derpirscher; 13.02.2016
comment
@ Арон, конечно, надеюсь, он неплохо справляется со своей задачей, делая его не таким плохим, как мог бы быть. Что касается доказательств, то вы их тоже не представляете, так что нам остается. Вы, без сомнения, проверяли подобные вещи раньше, как и я, и другие тоже. Результаты всегда одинаковы. LINQ проиграет обычному циклу for. - person harold; 13.02.2016
comment
@derpirscher Извините... я имел в виду .Any() - person Aron; 13.02.2016