Счетные биты, установленные в классе .Net BitArray

Ответ 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 раз быстрее, чем подход Kernighan с примерно 50% бит, установленным в true в BitArray с 1000 бит. У меня также есть версия VB, если это необходимо.

Ответ 2

вы можете легко справиться с Linq

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

Ответ 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, вы можете считать байты мод вручную.

Ответ 4

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

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

Ответ 5

Существует не более быстрый способ использования 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).

Ответ 6

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

Другой, возможно, более полезный метод - использовать что-то вроде трюк Kernighan, который является 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, но алгоритмически это должно быть лучше.

EDIT: процитировал, где я обнаружил трюк Кернигана, с более подробным объяснением

Ответ 7

Если вы не возражаете копировать код 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);
        }
    }

Ответ 8

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

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;
}

Ответ 9

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

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

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

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

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

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

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

BitArray:

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

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

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

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

Ответ 10

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

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

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