Подсчет битов, установленных в .Net BitArray Class

Question

Я реализую библиотеку, в которой я широко использую класс .Net BitArray и мне нужен эквивалент Java-метода BitSet.Cardinality (), то есть метод, который возвращает количество установленных битов. Я думал о реализации его в качестве метода расширения для класса BitArray. Тривиальная реализация состоит в том, чтобы повторять и подсчитывать установленные биты (как показано ниже), но я хотел бы более быструю реализацию, поскольку я выполнял бы тысячи операций над множествами и считал ответ. Есть ли более быстрый способ, чем в примере ниже?

count = 0;

for (int i = 0; i < mybitarray.Length; i++)
{

  if (mybitarray [i])
    count++;
}

Answer 1

Это мое решение, основанное на «лучшем методе подсчета битов» из http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

public static Int32 GetCardinality(BitArray bitArray)
{

    Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];

    bitArray.CopyTo(ints, 0);

    Int32 count = 0;

    // fix for not truncated bits in last integer that may have been set to true with SetAll()
    ints[ints.Length - 1] &= ~(-1 << (bitArray.Count % 32));

    for (Int32 i = 0; i < ints.Length; i++)
    {

        Int32 c = ints[i];

        // magic (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)
        unchecked
        {
        c = c - ((c >> 1) & 0x55555555);
        c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
        c = ((c + (c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
        }

        count += c;

    }

    return count;

}

Согласно моим тестам, это примерно в 60 раз быстрее, чем простой цикл foreach, и все еще в 30 разчем подход Кернигана с приблизительно 50% битов, установленными в true в BitArray с 1000 битами.У меня также есть версия этого VB, если это необходимо.

Answer 2

Вы можете сделать это довольно легко с Linq

BitArray ba = new BitArray(new[] { true, false, true, false, false });
var numOnes = (from bool m in ba
           where m
           select m).Count();

Answer 3

BitArray myBitArray = new BitArray(...

int
    bits = myBitArray.Count,
    size = ((bits - 1) >> 3) + 1,
    counter = 0,
    x,
    c;

    byte[] buffer = new byte[size];
    myBitArray.CopyTo(buffer, 0);

    for (x = 0; x < size; x++)
        for (c = 0; buffer[x] > 0; buffer[x] >>= 1)
            counter += buffer[x] & 1;

Взят из " Установлены счетные биты, по пути Брайана Кернигана " и адаптированы для байтов.Я использую его для битовых массивов от 1 000 000+ битов, и это превосходно.
Если ваши биты не n * 8, то вы можете считать модовый байт вручную.

Answer 4

Я написал свою версию после того, как не нашел ту, которая использует справочную таблицу:

private int[] _bitCountLookup;
private void InitLookupTable()
{
    _bitCountLookup = new int[256];

    for (var byteValue = 0; byteValue < 256; byteValue++)
    {
        var count = 0;
        for (var bitIndex = 0; bitIndex < 8; bitIndex++)
        {
            count += (byteValue >> bitIndex) & 1;
        }
        _bitCountLookup[byteValue] = count;
    }
}

private int CountSetBits(BitArray bitArray)
{
    var result = 0;
    var numberOfFullBytes = bitArray.Length / 8;
    var numberOfTailBits = bitArray.Length % 8;
    var tailByte = numberOfTailBits > 0 ? 1 : 0;
    var bitArrayInBytes = new byte[numberOfFullBytes + tailByte];
    bitArray.CopyTo(bitArrayInBytes, 0);

    for (var i = 0; i < numberOfFullBytes; i++)
    {
        result += _bitCountLookup[bitArrayInBytes[i]];
    }

    for (var i = (numberOfFullBytes * 8); i < bitArray.Length; i++)
    {
        if (bitArray[i])
        {
            result++;
        }
    }
    return result;
}

Answer 5

Если вы не возражаете скопировать код System.Collections.BitArray в свой проект и отредактировать его, вы можете написать как собеседник: (Я думаю, что это самый быстрый. И я пытался использовать BitVector32 [] для реализациимой BitArray, но он все еще такой медленный.)

    public void Set(int index, bool value)
    {
        if ((index < 0) || (index >= this.m_length))
        {
            throw new ArgumentOutOfRangeException("index", "Index Out Of Range");
        }
        SetWithOutAuth(index,value);
    }
    //When in batch  setting values,we need one method that won't auth the index range
    private void SetWithOutAuth(int index, bool value) 
    {
        int v = ((int)1) << (index % 0x20);
        index = index / 0x20;
        bool NotSet = (this.m_array[index] & v) == 0;
        if (value && NotSet)
        {
            CountOfTrue++;//Count the True values
            this.m_array[index] |= v;
        }
        else if (!value && !NotSet)
        {
            CountOfTrue--;//Count the True values
            this.m_array[index] &= ~v;
        }
        else 
            return;
        this._version++;
    }

    public int CountOfTrue { get; internal set; }

    public void BatchSet(int start, int length, bool value)
    {
        if (start < 0 || start >= this.m_length || length <= 0)
            return;
        for (int i = start; i < length && i < this.m_length; i++)
        {
            SetWithOutAuth(i,value);
        }
    }

Answer 6

Если вы действительно хотите максимизировать скорость, вы можете предварительно вычислить таблицу подстановки, где при заданном значении байта у вас будет количество элементов, но BitArray - не самая идеальная структура для этого, так как вам нужно будет использовать отражение чтобы извлечь из него базовое хранилище и оперировать целочисленными типами - см. этот вопрос для лучшего объяснения этого метода.

Другой, возможно, более полезный метод - использовать что-то вроде трюка Кернигана , который равен O (m) для n-битного значения мощности m.

static readonly ZERO = new BitArray (0);
static readonly NOT_ONE = new BitArray (1).Not ();

public static int GetCardinality (this BitArray bits)
{
    int c = 0;
    var tmp = new BitArray (myBitArray);

    for (c; tmp != ZERO; c++)
        tmp = tmp.And (tmp.And (NOT_ONE));

    return c;
}

Это тоже немного более громоздко, чем это было бы, скажем, в C, потому что нет никаких операций, определенных между целочисленными типами и BitArrays, (например, tmp &= tmp - 1, чтобы очистить младший значащий бит набора, был переведен в tmp &= (tmp & ~0x1).

Я понятия не имею, будет ли это быстрее, чем наивная итерация для случая BCL BitArray, но с точки зрения алгоритма это должно быть лучше.

---

РЕДАКТИРОВАТЬ: цитируется, где я обнаружил трюк Кернигана, с более подробным объяснением

Answer 7

Нет более быстрого способа использования BitArray - к чему это приведет, вы должны будете посчитать их - вы можете использовать LINQ для этого или сделать свой собственный цикл, но BitArray не предлагает никакого методаи базовая структура данных - это массив int[] (как видно с помощью Reflector) - так что это всегда будет O (n), где n - это число битов в массиве.

Единственный способ, которым я мог думатьчтобы сделать это быстрее, используйте отражение, чтобы овладеть базовым полем m_array, тогда вы можете обойти проверку границ, которую Get() использует при каждом вызове (см. ниже) - но это немного грязно и может быть толькоСтоит того на очень больших массивах, так как отражение дорого стоит.

public bool Get(int index)
{
    if ((index < 0) || (index >= this.Length))
    {
        throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index"));
    }
    return ((this.m_array[index / 0x20] & (((int) 1) << (index % 0x20))) != 0);
}

Если эта оптимизация действительно важна для вас, вы должны создать свой собственный класс для манипулирования битами, который внутренне может использовать BitArray, но отслеживаетиз числа установленных битов и предлагает соответствующие методы (в основном делегируют BitArray, но добавляют методы, чтобы получить количество установленных битов) - тогда, конечно, этобудет O (1).

Answer 8

Вы можете использовать Linq, но это будет бесполезно и медленнее:

var sum = mybitarray.OfType<bool>().Count(p => p);

Answer 9

У меня была та же проблема, но у меня было больше, чем один метод кардинальности для преобразования. Итак, я решил портировать весь класс BitSet. К счастью, это было автономно.

Вот Суть порта C # .

Буду признателен, если люди сообщат о найденных ошибках - я не Java-разработчик, и у меня ограниченный опыт работы с битовой логикой, поэтому я мог бы перевести некоторые из них неправильно.

Answer 10

Проблема, естественно, в O (n), в результате ваше решение, вероятно, наиболее эффективно.

Поскольку вы пытаетесь подсчитать произвольное подмножество битов, вы не можете подсчитать биты, когда они установлены (будет обеспечивать повышение скорости, если вы не будете устанавливать биты слишком часто).

Вы можете проверить, есть ли у процессора, который вы используете, команда, которая будет возвращать количество установленных бит.Например, процессор с SSE4 может использовать POPCNT в соответствии с этим постом .Это, вероятно, не будет работать для вас, так как .Net не позволяет сборку (потому что она не зависит от платформы).Кроме того, процессоры ARM, вероятно, не имеют эквивалента.

Вероятно, лучшим решением будет поиск таблицы (или переключение, если вы можете гарантировать, что переключатель будет скомпилирован в один переход к currentLocation + byteValue).Это даст вам счет для всего байта.Конечно, BitArray не предоставляет доступ к базовому типу данных, поэтому вам придется создать свой собственный BitArray.Вы также должны были бы гарантировать, что все биты в байте всегда будут частью пересечения, что маловероятно.

Другим вариантом будет использование массива логических значений вместо BitArray.Это имеет то преимущество, что нет необходимости извлекать бит из других в байте.Недостатком является то, что массив будет занимать в 8 раз больше места в памяти, что означает не только потраченное впустую пространство, но и больший объем данных при выполнении итерации по массиву для выполнения подсчета.

Разница между поиском стандартного массиваи поиск BitArray выглядит следующим образом:
Array:

1. offset = index * indexSize
2. Получить память в местоположении + смещение и сохранить в значение

BitArray:

1. index = index / indexSize
2. offset = index * indexSize
3. Получить память в местоположении + смещение и сохранить в значение
4. position = index% indexSize
5. Бит позиции значения сдвига
6. value = значение и 1

За исключением № 2 для массивов и № 3 для большинстваэти команды занимают 1 процессорный цикл для завершения.Некоторые команды могут быть объединены в 1 команду с использованием процессоров x86 / x64, хотя, вероятно, не с ARM, поскольку она использует сокращенный набор инструкций.
Какая из двух (массив или BitArray) работает лучше, будет зависеть от вашей платформы(скорость процессора, инструкции процессора, размеры кэш-памяти процессора, скорость кэш-памяти процессора, объем системной памяти (Ram), скорость системной памяти (CAS), скорость соединения между процессором и RAM), а также разброс индексов, которые вы хотите посчитать(перекрестки чаще всего кластеризованы или они распределены случайным образом).

Подводя итог: вы, вероятно, могли бы найти способ сделать это быстрее, но ваше решение является самым быстрым для васваш набор данных, используя битовую булеву модель в .NET.

Редактировать: , убедитесь, что вы получаете доступ к индексам, которые вы хотите посчитать по порядку.Если вы обращаетесь к индексам 200, 5, 150, 151, 311, 6 в указанном порядке, то вы увеличиваете количество кеш-пропусков, что приводит к увеличению времени ожидания получения значений из ОЗУ.