c # bitarray индекс положительных битов

Question

У меня есть ac # BitArray, который довольно большой (500 000) в длину, и я пытаюсь получить индекс всех положительных битов, установленных в массиве.в настоящее время я достигаю этого следующим образом:

public int[] GetIndexesForPositives()
{
    var idIndexes = new int[GetPositiveCount + 1];
    var idx = 0;
    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                idIndexes[idx++] = i;
            }
        }
    return idIndexes;
}

Я создаю пустой массив размером с известные положительные биты, затем прыгаю над битарным массивом и добавляю значение индекса в возвращаемый массив.* Это означает, что я должен выполнить 500 000 циклов над массивом, и это не совсем быстро.(занимает около 15 мс).

Я знаю, что BitArray использует целочисленный массив под обложками (я использовал его, чтобы написать функцию GetPositiveCount - через логарифм, который я получил из стека).сделать это так же?

Answer 1

Если вы можете поменять BitArray на BCL в пользу «бросить свой собственный», вы можете сделать это лучше.Вот несколько вещей, которые вы можете сделать:

1. Пропускать фрагменты из 64, для которых не установлены биты
2. Для блоков из 64, в которых есть биты, перечислять только 1 бит вместо всехбиты с использованием x & (x - 1) и ваш любимый быстрый 2log найден здесь (использование наивного 64-шагового метода не даст никакого ускорения)
3. Сохраните дополнительный битрейр, который хранит для каждого64-битный блок, ненулевой ли он.Примените методику от маркера 2 к , что bitarray, чтобы пропустить все диапазоны нулей за один раз.
4. Примените пулю 3 рекурсивно для гигантских битрейров

Все четыреони помогают только в том случае, если ожидается, что битовый массив будет разреженным, а наихудшим случаем будет O (n), если он не разреженный.Если пуля 3 применяется до тех пор, пока вершина не является единственным продолговатым, то в O (1) она может определить, является ли весь битовый массив пустым или нет.

Answer 2

Если вы можете получить массив int, лежащий в основе BitArray, это должно обеспечить гораздо лучшую производительность:

Предполагая, что вы не знаете, сколько битов установлено:

public static int[] GetIndexesForPositives()
{
    var idIndexes = new List<int>();
    System.Reflection.FieldInfo field = data.GetType().GetField("m_array", System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance);
    int[] values = field.GetValue(data) as int[];

    for (var i = 0; i < values.Length; i++)
    {
        int _i = values[i];
        if (_i != 0)
        {
            for (var j = 0; j < 32; j++)
            {
                if ((_i & (1 << j)) != 0)
                {
                    idIndexes.Add(i * 32 + j);
                }
            }
        }
    }
    return idIndexes.ToArray();
}

Если вы знаете количество установленных битов, вы можете сделать это вместо:

public static int[] GetIndexesForPositives(int length)
{
    var idIndexes = new int[length];
    var idx = 0;
    System.Reflection.FieldInfo field = data.GetType().GetField("m_array", System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance);
    int[] values = field.GetValue(data) as int[];

    for (var i = 0; i < values.Length; i++)
    {
        int _i = values[i];
        if (_i != 0)
        {
            for (var j = 0; j < 32; j++)
            {
                if ((_i & (1 << j)) != 0)
                {
                    idIndexes[idx++] = i * 32 + j;
                }
            }
        }
}

В моих тестах эти два теста работают быстрее, чем ваш метод, даже тот, который не знает, насколько большим будет возвращаемый массив.

Мои результаты проверены с использованием случайного BitArray из 50 миллионов записей:

1) 25001063 records found in 50000000, took 1415.5752ms
2) 25001063 records found in 50000000, took 1099.67ms
3) 25001063 records found in 50000000, took 1045.6862ms
4) 25001063 records found in 50000000, took 745.7762ms"

1) is your code but using an arraylist instead of using some `GetPositiveCount` to get the output length.
2) is your code
3) is my (revised) first example
4) is my (revised) second example

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

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

for (var j = 0; j < 32; j++)
{
     if (_i == 0)
         break;
     if ((_i & (1)) != 0)
     {
         idIndexes.Add(i * 32 + j);
     }
     _i = _i >> 1;
 }

это немного медленнее, если список заполнен> 40% или более, однако, если вы знаете, что список всегда будет 10% 1 с и 90% 0, то это будет работать еще быстрее для вас.

Answer 3

Я бы сделал что-то вроде этого:

public int[] GetIndexesForPositives()
{
    var idIndexes = new LinkedList<int>();

    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                idIndexes.Add(i);
            }
        }
    return idIndexes.ToArray();
}

Если это все еще неприемлемо (поскольку вы снова просматриваете индексы во время выполнения ToArray), просто используйте тот же размер для массива результатов и верните длину найденных индексов:

public int GetIndexesForPositives(out int[] indizes)
{
    indizes = new int[Length];
    var idI = 0;

    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                indizes[idI++] = i;
            }
        }
    return idI;
}

В зависимости от того, действительно ли вам нужны все индизы или только части, вы можете даже подумать о чем-то подобном (но если вам понадобится каждая часть, это будет менее эффективно - сделайте профилирование самостоятельно, пожалуйста):

public IEnumerable<int> GetIndexesForPositives()
{
    for (var i = 0; i < Length; i++)
        {
            if (Get(i))
            {
                yield return i;
            }
        }
}

это предполагает, что ваш Get (i) выполняет свою работу и что ваш массив неизменен.

Answer 4

Вы довольно много раз повторяете 500 000 раз.Интуитивно понятно: если установлен каждый бит, вам нужно создать массив с 500 000 элементов.Вы можете уменьшить количество внешних итераций в 8 или 32 раза, обратившись к базовому байту или целому числу, но тогда вам все равно придется повторять биты.Даже таблица поиска с 256 элементами для каждого возможного значения байта не поможет, так как вам нужно добавить битовый индекс.

Однако, если у вас много нулевых битов (надеюсь, что вы это сделаете), тогда оптимизацияпросто настроить счетчик цикла на 8 или 32, если базовый байт / int равен 0. Поскольку вы знаете, что Get () вернет 0. Кроме того, используйте List <>, чтобы избежать затрат на GetPostitiveCount.

Полностью исключить необходимость в этом массиве и лениво извлекать следующий бит, установленный в 1, было бы безусловно лучшим подходом.