Когда я должен использовать BitVector32? - PullRequest
Новая
       33

Когда я должен использовать BitVector32?

5 голосов
/ 23 февраля 2011

Я работаю над проектом, в котором в определенный момент мне нужно в течение одного месяца показать, какие дни еще доступны. Есть функция, которая вычисляет, какие дни доступны. Мои коллеги сказали: «О, мы знаем, вы должны вернуть BitVector32. Это наиболее эффективно при работе со списком логических значений». Я бы использовал List<bool> или что-то в этом роде. A BitVector32 кажется мне чем-то для вещей низкого уровня, когда вы на самом деле работаете с битами.

Итак, вопрос в том. Вы должны использовать BitVector32 всякий раз, когда вам нужен какой-то список логических значений, содержащий менее 32 элементов, или вы должны использовать его только для вещей низкого уровня?

Ответы [ 2 ]

4 голосов
/ 23 февраля 2011

Использование списка легко расширяется на другие периоды времени. Скажем, вы хотите показать два месяца сразу. О, это больше, чем 32. Мне нужно изменить тип возврата и везде, где он используется. Большой! И BitVector32 даже не реализует IEnumerable<T>.

И если только он не находится в тесной петле, удобочитаемость и удобство обслуживания обеспечивают максимальную эффективность. И издержки при распределении списков не так велики, если вы не делаете это миллион раз в секунду.

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

2 голосов
/ 09 июля 2012

BitVector32 - это оболочка (или вы можете назвать это абстракцией) вокруг битовых операций c #. Например, следующие два оператора возвращают один и тот же результат:

  • 1 << 1 </li>
  • BitVector32.CreateMask (1)

Допустим, существует целочисленный массив, содержащий несколько повторяющихся чисел. Мы хотим найти все дубликаты. Конечно, вы можете просто использовать функцию GroupBy в Linq, но давайте представим, что у нас нет Linq.

  1. Первый вариант - метод перебора, где каждый элемент будет сравниваться с каждым элементом в данном массиве: 

    foreach(int i in list) 
{
    foreach(int j in list)
    {
        if (i == j) 
        {
            // print this or store it in the result list
        }
    }
}

  2. Поскольку метод грубой силы приведет к продолжительности N квадратов, что довольно неэффективно, мы можем подумать об использовании HashSet, который обеспечит постоянное время поиска, или O (1) 

    HashSet<int> hashSet = new HashSet<int>();

foreach(int i in list)
{    
    if (hashSet.Contains(i))
    {
        // print the duplicate or add it to the result list
    }
    else
    {
        hashSet.Add(i);
    }
}

Этот подход приведет к линейному времени работы или O (n). Однако, это требует дополнительной памяти n * 4 байта (при условии, что мы говорим о 32-разрядном целом числе)

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

    bool[] masks = new bool[list.Length];

for (int i = 0; i < list.length; i++) 
{
    if (masks[list[i]])
    {
        // print or add to the result list
    }
    else
    {
        masks[list[i]] = true;
    }
}

он использует логический массив вместо HashSet. Он имеет то же время выполнения, что и O (n), но требует 1/4 объема памяти, поскольку тип bool занимает 1 байт (8 бит), а целое число занимает 4 байта (32 бита)

  1. Наконец, мы можем решить эту проблему, используя класс BitVector32 или собственные операции сдвига битов. 

    int check = 0;
for (int i=0; i < list.Length; i++)
{
    int mask = 1 << list[i];
    if (check & mask == mask) 
    {
        // print or add list[i] to the result list
    }
    else
    {
        check = check | mask;
    }
}

Это также приведет к линейному времени выполнения всего с 32 битами памяти. Таким образом, использование памяти n / 32. Конечно, это не сработает, если максимальное значение в массиве больше 32. Мы можем использовать 64-разрядное целое число без знака, чтобы увеличить количество слотов в маске, но оно по-прежнему имеет очень короткий предел. В этом случае, если вы создаете массив BitVectory32 и вы можете сдвинуть бит в объект BitVector32 в следующем индексе массива. Например, код будет выглядеть примерно так: 

BitVector32[] bitVectorArray = new BitVector32[maxValue / 32];
bitVectorArray[list[i] / 32] = 1 << list[i] % 32;

Таким образом, вам не нужно ограничиваться 32-битным пределом размера. Вы можете увеличивать размер большой маски до бесконечности, пока позволяет объем памяти. Итак, соберите все вместе: 

// This code assumes you know the range of the number in the array
BitVector32[] bitVectorArray = new BitVector32[maxValue / 32];

for (int i=0; i < list.Length; i++)
{
    int mask = 1 << list[i] % 32;

    if (bitVectorArray[(list[i] - 1)/32][i] & mask == mask) 
    {
        // print or add list[i] to the result list
    }
    else
    {
        bitVectorArray[(list[i] - 1)/32] = bitVectorArray[list[i] / 32] | mask;
    }
}
...