Быстрее ли BitArray в C # для получения битового значения, чем простое соединение с побитовым сдвигом?

17

1). % Co_de%

2). используя var bitValue = (byteValue & (1 << bitNumber)) != 0; с помощью System.Collections.BitArray

  • Что быстрее?
  • В каких ситуациях для .NET-проектов BitArray может быть более полезным, чем простая связь с побитовым сдвигом?
задан Secret 09.05.2013 в 23:51
источник
  • Используя System.Diagnostics.Stopwatch, вы могли бы время, если оно быстрее. Лучше всего попробовать его как можно ближе к производственной среде. –  Corey Ogburn 09.05.2013 в 23:53

2 ответа

23

BitArray сможет обрабатывать произвольное количество логических значений, тогда как byte будет содержать только 8, int только 32 и т. д. Это будет самая большая разница между ними.

Кроме того, BitArray реализует IEnumerable , где интегрального типа, очевидно, нет. Так что все зависит от требований вашего проекта; если вам нужен интерфейс IEnumerable или массив, а затем перейдите к BitArray .

Я бы использовал bool[] для любого решения, просто потому, что он более явный в том , который вы отслеживаете. Т

BitArray или bitfield будет использовать примерно 1/8 пробела bool[] , потому что они «упаковывают» 8 логических значений в один байт, тогда как bool сам по себе займет весь 8- бит. Преимущество пространства использования битового поля или BitArray не будет иметь значения, пока вы не сохраните лоты bools . (Математика остается до читателя :-))

Benchmark

Результаты. Для моей примитивной тестовой среды кажется, что BitArray является бит быстрее, но находится на том же уровне величины, что и сам с интегральным типом. Также тестировалось bool[] , что было неудивительно самым быстрым. Доступ к одному байту в памяти будет менее сложным, чем доступ к отдельным битам в разных байтах.

Testing with 10000000 operations:
   A UInt32 bitfield took 808 ms.
   A BitArray (32) took 574 ms.
   A List<bool>(32) took 436 ms.

код:

class Program
{
    static void Main(string[] args)
    {
        Random r = new Random();
        r.Next(1000);

        const int N = 10000000;

        Console.WriteLine("Testing with {0} operations:", N);

        Console.WriteLine("   A UInt32 bitfield took {0} ms.", TestBitField(r, N));
        Console.WriteLine("   A BitArray (32) took {0} ms.", TestBitArray(r, N));
        Console.WriteLine("   A List<bool>(32) took {0} ms.", TestBoolArray(r, N));

        Console.Read();
    }


    static long TestBitField(Random r, int n)
    {
        UInt32 bitfield = 0;

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < n; i++) {

            SetBit(ref bitfield, r.Next(32), true);
            bool b = GetBit(bitfield, r.Next(32));
            SetBit(ref bitfield, r.Next(32), b);
        }
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }

    static bool GetBit(UInt32 x, int bitnum) {
        if (bitnum < 0 || bitnum > 31)
            throw new ArgumentOutOfRangeException("Invalid bit number");

        return (x & (1 << bitnum)) != 0;
    }

    static void SetBit(ref UInt32 x, int bitnum, bool val)
    {
        if (bitnum < 0 || bitnum > 31)
            throw new ArgumentOutOfRangeException("Invalid bit number");

        if (val)
            x |= (UInt32)(1 << bitnum);
        else
            x &= ~(UInt32)(1 << bitnum);
    }



    static long TestBitArray(Random r, int n)
    {
        BitArray b = new BitArray(32, false);     // 40 bytes

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < n; i++) {

            b.Set(r.Next(32), true);
            bool v = b.Get(r.Next(32));
            b.Set(r.Next(32), v);
        }
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }



    static long TestBoolArray(Random r, int n)
    {
        bool[] ba = new bool[32];

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < n; i++) {

            ba[r.Next(32)] = true;
            bool v = ba[r.Next(32)];
            ba[r.Next(32)] = v;
        }
        sw.Stop();
        return sw.ElapsedMilliseconds;
    }
}
    
ответ дан Jonathon Reinhart 09.05.2013 в 23:54
  • спасибо за ваше уведомление, Джонатон :) –  Secret 10.05.2013 в 00:01
  • Я удалил второй вопрос с исходного сообщения и снова открыл его. Интересно, что у меня есть набор функций SetBit и GetBit в текущем проекте, которые выглядят так же, как эти. –  Robert Harvey♦ 10.05.2013 в 00:22
  • Кроме того, похоже, что ваш код проверяет скорость генератора случайных чисел, а также сдвиг бит. Меня не удивило бы, если генерация случайных чисел займет значительно больше времени. –  Robert Harvey♦ 10.05.2013 в 00:26
  • Я запустил ваш код без изменений на своей машине и получил результаты 1525 мс и 1185 мс соответственно. Затем я изменил ваш случайный r на int всюду, установил его на ноль и снова запустил. Результаты были 581ms и 209ms, что говорит о том, что BitArray более чем в два раза быстрее, а Random потребляет 2/3 времени обработки. Я получил практически те же результаты, что и r до 31 (я использовал 0 и 31 для двух прогонов). –  Robert Harvey♦ 10.05.2013 в 00:49
  • @Trap Есть идеи? –  Jonathon Reinhart 26.03.2014 в 03:41
Показать остальные комментарии
21

@ Джонатон Рейнхарт,

Ваш тест, к сожалению, неубедительный. Он не учитывает эффекты возможной ленивой загрузки, кэширования и / или предварительной выборки (CPU, ОС хоста и / или среды выполнения .NET).

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

Я сделал свой оригинальный тест, построенный с целевой платформой «Любой процессор» и профилем клиента .NET 4.0, работающим на моей машине с процессором i7-3770 и 64-разрядной версией Windows 7.

Что я получил, это:

Testing with 10000000 operations:
   A UInt32 bitfield took 484 ms.
   A BitArray (32) took 459 ms.
   A List<bool>(32) took 393 ms.

, что в значительной степени соответствует вашим наблюдениям.

Однако выполнение теста BitArray перед тестом UInt32 дало следующее:

Testing with 10000000 operations:
   A BitArray (32) took 513 ms.
   A UInt32 bitfield took 456 ms.
   A List<bool>(32) took 417 ms.

Изучив время тестов UInt32 и BitArray, вы заметите, что измеренное время, похоже, не связано с самими тестами, а скорее с порядком, в котором выполняются тесты.

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

Тестовый заказ UInt32, BitArray, BoolArray, UInt32, BitArray, BoolArray :

Testing with 10000000 operations:
   A UInt32 bitfield took 476 ms.
   A BitArray (32) took 448 ms.
   A List<bool>(32) took 367 ms.

   A UInt32 bitfield took 419 ms.  <<-- Watch this.
   A BitArray (32) took 444 ms.    <<-- Watch this.
   A List<bool>(32) took 388 ms.

Тестовый заказ BitArray, UInt32, BoolArray, BitArray, UInt32, BoolArray :

Testing with 10000000 operations:
   A BitArray (32) took 514 ms.
   A UInt32 bitfield took 413 ms.
   A List<bool>(32) took 379 ms.

   A BitArray (32) took 444 ms.    <<-- Watch this.
   A UInt32 bitfield took 413 ms.  <<-- Watch this.
   A List<bool>(32) took 381 ms.

Глядя на второстепенные вызовы методов тестирования, кажется, что по крайней мере на i7 процессорах с современной средой .NET, тест UInt32 быстрее, чем тест BitArray , в то время как Тест BoolArray по-прежнему является самым быстрым.

(Я прошу прощения, что мне пришлось написать свой отзыв на тест Jonathon в качестве ответа, но, как новый пользователь SO, мне не разрешено комментировать ...)

EDIT:

Вместо того, чтобы перетасовывать порядок тестовых методов, вы можете попробовать поставить Thread.Sleep (5000) или подобное прямо перед вызовом первого теста ...

И исходный тест, по-видимому, ставит тест UInt32 в невыгодное положение, поскольку он включает в себя проверку границ « if (bitnum & lt; 0 || bitnum & gt; 31) », которая выполнена 30 миллионов раз. Ни один из двух других тестов не включает такую ​​проверку границ. Однако на самом деле это не вся правда, так как и BitArray, и массив bool выполняют пограничные проверки внутри.

Хотя я не тестировал, я ожидаю, что устранение пограничных проверок сделает тесты UInt32 и BoolArray аналогичным образом, но это не будет хорошим предложением для публичного API.

    
ответ дан elgonzo 26.09.2013 в 14:12
  • Вы должны действительно запускать все свои тесты полностью отдельно и независимо друг от друга, а не просто запускать следующий, а затем следующий. –  Seph 12.11.2013 в 12:58
  • @Seph, вы правы. Для правильного бенчмарка это был бы путь. Тем не менее, код, который я написал, просто предназначался для демонстрации знаменитого принципа «Вы не измеряете то, что, по вашему мнению, вы измеряете»;) –  elgonzo 14.11.2013 в 19:46