Какой самый быстрый способ найти позицию последовательности 0-bit заданной длины в int[]?

Question

[Владимир]

Имеется 65536 бит которые храняться в виде массива int[] . Необходимо найти позицию i последовательности 0-bit заданной длины n. Сейчас делаю просто перебором в цикле с проверкой каждого бита. Есть ли более быстрые/современные методы?

Answer 1

[Wataru]

Зависит от длины n. Если n маленькое то можно прикладывать маску. Байт x содержит 3 ноля в последних битах, если ~x &0x7 == 0x7. Аналогично, сдвигая маску из трех единиц (0x7) можно приложить ко всем позициям.

Если n большое, то надо чтобы было много нулевых байт в массиве подряд. Тут можно использовать SSE инструкции для массового сравнения байт с нулями.

Потом, можно еще распараллелить поиск в несколько потоков. Каждый поток ищет последовательность, начинающаюся в отдельном куске массива.

Answer 2

[Владимир]

Я использовал ulong[] в конечном варианте. Делаю маски, считаю PopCount, Traling/Leading Zeros и пропускаю кусками

using System.Numerics;
namespace test_bit_masks;

internal class Program
{
    private const int _bitsShiftUlong = 6;
    private const int _bitsPerByte = 8;
    private const int _bitsPerUlong = sizeof(ulong) * _bitsPerByte;

    static void Main(string[] args)
    {
        var randomFillPercentage = 30;
        var minSequenceLength = 1;
        var maxSequenceLength = byte.MaxValue;
        var bitsQuantity = ushort.MaxValue;

        var testsQuantity = 1_000;

        var bits = new ulong[(int)((uint)(bitsQuantity - 1 + (1 << _bitsShiftUlong)) >> _bitsShiftUlong)];

        RandomFill(randomFillPercentage, bitsQuantity, ref bits);

        foreach (var _ in Enumerable.Range(0, testsQuantity))
        {
            var requiredQty = Random.Shared.Next(minSequenceLength, maxSequenceLength);
            var start = Random.Shared.Next(0, bitsQuantity);
            var res = TryFindFreeSlotsNewVersion(start, bitsQuantity, requiredQty, ref bits, out var shift, false);
        }

       
        Console.WriteLine($"Done");
        Console.ReadLine();
    }

    private static void RandomFill(int fillPercentage, int bitsQuantity, ref ulong[] bits)
    {
        var number = bitsQuantity * fillPercentage / 100;
        var rnd = Random.Shared;
        foreach (var i in Enumerable.Range(0, number))
        {
            var index = rnd.Next(0, bitsQuantity);
            bits[index >> _bitsShiftUlong] |= 1ul << index;
        }

    }

    private static bool TryFindFreeSlotsNewVersion(int start, int bitsQuantity, int requiredQuantity, ref ulong[] bits, out int shift, bool debug = false)
{
    var position = start;

    var candidateShift = 0;
    var lastArrayIndex = bits.Length - 1;
    var lastArrayItemBitsToReset = bits.Length * _bitsPerUlong - bitsQuantity;
    var testShift = 0;
    var startAdjusted = false;
    var lastPosition = start + bitsQuantity;
    var top = Console.CursorTop;

    var remainingQuantity = requiredQuantity;
    var partialCapture = false;
    var found = false;
    while (!found)
    {
        position = start + testShift;

        if (position >= lastPosition) break;

        if (debug)
        {
            Console.CursorTop = top;
            Console.WriteLine();
        }

        var bufferPosition = (start + testShift) % bitsQuantity;

        var arrayItemIndex = bufferPosition >> _bitsShiftUlong;
        var v = bits[arrayItemIndex];

        var mask = 1UL << bufferPosition;
        var maskForValue = mask | ~(mask - 1);
        var arrayItemPosition = bufferPosition % _bitsPerUlong;
        var maskedValue = v & maskForValue;

        if (debug)
        {
            Console.WriteLine(new string(Convert.ToString((long)v, 2).PadLeft(_bitsPerUlong, '0').Reverse().ToArray()));
            Console.WriteLine(new string(Convert.ToString((long)maskForValue, 2).PadLeft(_bitsPerUlong, '0').Reverse().ToArray()));
            Console.WriteLine(new string(Convert.ToString((long)maskedValue, 2).PadLeft(_bitsPerUlong, '0').Reverse().ToArray()));
            Console.WriteLine(new string(Convert.ToString((long)(1UL << arrayItemPosition), 2).PadLeft(_bitsPerUlong, '0').Replace("0", " ").Replace("1", "↑").Reverse().ToArray()));
        }

        if (debug)
        {
            Console.ReadKey();
        }

        var isLastArrayIndex = arrayItemIndex == lastArrayIndex;

        var maximumCount = BitOperations.PopCount(maskForValue);
        var totalFreeCount = maximumCount - BitOperations.PopCount(maskedValue) - (isLastArrayIndex ? lastArrayItemBitsToReset : 0);

        var trailingZeroCount = BitOperations.TrailingZeroCount(maskedValue);
        var availableFreeSlotsForCurrentPosition = trailingZeroCount - arrayItemPosition;
        var isOnLastZeroes = availableFreeSlotsForCurrentPosition == maximumCount;

        if (isOnLastZeroes && isLastArrayIndex)
        {
            availableFreeSlotsForCurrentPosition = availableFreeSlotsForCurrentPosition - lastArrayItemBitsToReset;
        }

        if (partialCapture && availableFreeSlotsForCurrentPosition == _bitsPerUlong)
        {
            if (!isLastArrayIndex)
            {
                remainingQuantity -= availableFreeSlotsForCurrentPosition;
                testShift += availableFreeSlotsForCurrentPosition;
            }
            else
            {
                partialCapture = false;
                remainingQuantity = requiredQuantity;
            }

        }
        else if (partialCapture && availableFreeSlotsForCurrentPosition < remainingQuantity)
        {
            partialCapture = false;
            remainingQuantity = requiredQuantity;
        }
        else if (partialCapture && availableFreeSlotsForCurrentPosition >= remainingQuantity)
        {
            found = true;
        }
        else
        {
            if (!startAdjusted || (totalFreeCount >= remainingQuantity || isOnLastZeroes))
            {
                if (availableFreeSlotsForCurrentPosition >= remainingQuantity)
                {
                    candidateShift = testShift;
                    found = true;
                }
                else if (availableFreeSlotsForCurrentPosition == 0)
                {
                    if (!startAdjusted)
                    {
                        startAdjusted = true;

                        if (testShift > 0)
                        {
                            lastPosition = lastPosition + testShift - 1;
                        }
                    }

                    testShift++;
                }
                else if (availableFreeSlotsForCurrentPosition < remainingQuantity)
                {
                    if (isOnLastZeroes && !isLastArrayIndex)
                    {
                        candidateShift = testShift;
                        remainingQuantity -= availableFreeSlotsForCurrentPosition;
                        partialCapture = true;

                    }

                    testShift += availableFreeSlotsForCurrentPosition;

                }

            }
            else
            {
                var leadingZeroCount = BitOperations.LeadingZeroCount(maskedValue);
                if (isLastArrayIndex)
                {
                    leadingZeroCount = leadingZeroCount - lastArrayItemBitsToReset;
                    testShift += maximumCount - lastArrayItemBitsToReset - leadingZeroCount;
                }
                else
                {
                    testShift += maximumCount - leadingZeroCount;
                }
            }
        }

    }
    shift = candidateShift;
    return found;
}
}

Answer 3

[vadimr]

Согласен с Wataru. Очень многое зависит от длины паттерна и от статистики распределения данных. Также решение зависит от архитектуры процессора. В общем, мало данных.