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

    @Degot Автор вопроса
    Я использовал 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;
    }
    }
    Ответ написан
    Комментировать
  • Какой структурой можно повесить lock на диапазон?

    @Degot Автор вопроса
    Я реализовал RangeLocker, который делает требуемое на основе spinLock'ов при создании блока + ManualResetEvent для каскада разблокирований.

    Для нахождения родительских блокировок я использую алгоритм художника на основе _painterBuffer.
    При создании блокировки я прохожусь по требуемому диапазону и прописываю индекс новой блокировки, собирая родительские. Из родителей я собираю Unlock event'ы и жду их завершения WaitHandle.WaitAll(parentsUnlockEvents);

    При Release'е блокировки, я прохожу по _painterBuffer и ставлю -1 там, где индекс равен индексу текущей блокировки.

    using System.Runtime.CompilerServices;
    namespace test_range_locking;
    
    internal class Program
    {
        private readonly Random _random = Random.Shared;
        private const int _bufferSize = 20;
        private byte[] _buffer = new byte[_bufferSize];
    
        private RangeLocker _locker;
    
        private readonly int _tasksQty;
        private readonly int _loopsQty;
        public Program(int tasksQty, int loopsQty)
        {
            _tasksQty = tasksQty;
            _loopsQty = loopsQty;
        }
    
        static void Main(string[] args)
        {
            new Program(3, 3).Run();
            Console.WriteLine("Done");
            Console.ReadLine();
        }
    
        private void Run()
        {
            _locker = new RangeLocker(_bufferSize, 4);
            var padding = _tasksQty.ToString().Length;
    
            var tasks = Enumerable.Range(0, _tasksQty)
                .Select(i => Task.Run(() => InternalTask($"{i}".PadLeft(padding, ' '), _loopsQty)))
                .ToArray();
            Task.WaitAll(tasks);
        }
    
        private void InternalTask(string taskId, int loops)
        {
    
            for (var idx = loops - 1; idx >= 0; idx--)
            {
                var start = _random.Next(0, _bufferSize);
                var len = _random.Next(1, _bufferSize - start + 1);
                using (var @lock = _locker.Aquire(taskId, start, len))
                {
                    Thread.Sleep(2000);
                }
            }
        }
    }
    
    internal class RangeLocker
    {
        private readonly int _bufferSize;
    
        private int[] _painterBuffer;
        private ulong[] _parentIndices;
    
        private RangeLock[] _locks;
        private int _locksBufferSize;
        private int _locksHead;
        private int _locksQuantity;
    
        private Semaphore _semaphoreFreeLocksQuantity;
        private int _mainSpinLock;
        public RangeLocker(int bufferSize, int maximumLocksQty)
        {
            _bufferSize = bufferSize;
            _locksBufferSize = maximumLocksQty;
    
            _painterBuffer = new int[_bufferSize];
            _painterBuffer.AsSpan().Fill(-1);
    
            _parentIndices = new ulong[BitUtils.GetRequiredNumberOfUlongs(_locksBufferSize)];
    
            _locks = new RangeLock[_locksBufferSize];
    
            _locksHead = 0;
            _locksQuantity = 0;
            _mainSpinLock = 0;
    
            _semaphoreFreeLocksQuantity = new Semaphore(_locksBufferSize, _locksBufferSize);
        }
    
        internal IDisposable Aquire(string taskId, int offset, int length)
        {
            Console.WriteLine($"THR {taskId} -> Try {offset} -> {offset + length - 1}");
    
            _semaphoreFreeLocksQuantity.WaitOne();
    
            var notified = false;
            while (Interlocked.CompareExchange(ref _mainSpinLock, 1, 0) != 0)
            {
                if (!notified)
                {
                    Console.WriteLine($"THR {taskId} -> Waiting for Main");
                    notified = true;
                }
            }
    
            Console.WriteLine($"THR {taskId} -> In Main");
    
            var lockPosition = _locksHead;
            ref var range = ref _locks[lockPosition];
    
            var parentsUnlockEvents = GatherParents(offset, length, lockPosition, out var debugParents);
    
            range.Lock(offset, length);
    
            _locksHead = GetNextFreePosition(_locksHead);
    
            Interlocked.Increment(ref _locksQuantity);
    
            Console.WriteLine($"THR {taskId} -> Main Released -> Free: {_locksBufferSize - _locksQuantity}");
            _mainSpinLock = 0;
    
            if (parentsUnlockEvents.Length > 0)
            {
                Console.WriteLine($"THR {taskId} -> Waiting for parents: {debugParents}");
                WaitHandle.WaitAll(parentsUnlockEvents);
                Console.WriteLine($"THR {taskId} -> Parents released");
            }
    
            Console.WriteLine($"THR {taskId} -> LOCK {lockPosition}: {offset} -> {offset + length - 1}");
            return new RangeUnlocker(this, lockPosition);
        }
    
        private ManualResetEvent[] GatherParents(int offset, int length, int lockPosition, out string debugParents)
        {
            debugParents = "";
    
            BitUtils.SetAllFalse(_parentIndices);
    
            var painterIndex = 0;
            var candidateParent = -1;
    
            for (var idx = length - 1; idx >= 0; idx--)
            {
                painterIndex = offset + idx;
                candidateParent = _painterBuffer[painterIndex];
                if (candidateParent >= 0)
                {
                    BitUtils.SetBitTrue(candidateParent, _parentIndices);
                }
    
                _painterBuffer[painterIndex] = lockPosition;
            }
    
            var parentsQty = BitUtils.GetIndexesForPositivesCount(_parentIndices);
            var parentsUnlockEvents = default(List<ManualResetEvent>);
            var parentsStr = "";
    
            if (parentsQty > 0)
            {
                var usedParentIndices = new List<int>();
                parentsUnlockEvents = new List<ManualResetEvent>();
                var parentsIndices = BitUtils.GetIndexesForPositives(_parentIndices);
                var parentIndex = -1;
    
                for (var idx = parentsQty - 1; idx >= 0; idx--)
                {
                    parentIndex = parentsIndices[idx];
                    ref var parent = ref _locks[parentIndex];
    
                    if (parent.Locked)
                    {
                        usedParentIndices.Add(parentIndex);
                        parentsUnlockEvents.Add(parent.UnlockEvent);
                    }
                }
    
                parentsQty = parentsUnlockEvents.Count;
    
                if (parentsQty > 0)
                {
                    debugParents = string.Join(", ", usedParentIndices);
                }
            }
    
            BitUtils.SetAllFalse(_parentIndices);
            return parentsQty > 0 ? parentsUnlockEvents.ToArray() : Array.Empty<ManualResetEvent>();
        }
    
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private int GetNextFreePosition(int position)
        {
            var foundPosition = GetBufferPosition(position + 1);
    
            while (_locks[foundPosition].Locked)
            {
                foundPosition = GetBufferPosition(foundPosition + 1);
            }
    
            return foundPosition;
        }
    
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private int GetBufferPosition(int position)
        {
            return position % _locksBufferSize;
        }
    
        private void Release(int lockPosition)
        {
            var notified = false;
            while (Interlocked.CompareExchange(ref _mainSpinLock, 1, 0) != 0)
            {
                if (!notified)
                {
                    Console.WriteLine($"UNLOCK {lockPosition} -> Waiting for Main");
                    notified = true;
                }
            }
    
            Console.WriteLine($"UNLOCK {lockPosition} -> In Main");
    
            ref var range = ref _locks[lockPosition];
    
            var offset = range.Offset;
            var painterIndex = 0;
            for (var idx = range.Length - 1; idx >= 0; idx--)
            {
                painterIndex = offset + idx;
                if (_painterBuffer[painterIndex] == lockPosition)
                {
                    _painterBuffer[painterIndex] = -1;
                }
            }
    
    
            Console.WriteLine($"UNLOCK {lockPosition}: {range.Offset} -> {range.Offset + range.Length - 1}");
            range.Unlock();
    
            Interlocked.Decrement(ref _locksQuantity);
            Console.WriteLine($"UNLOCK {lockPosition} -> Main Released -> Free: {_locksBufferSize - _locksQuantity}");
    
            _semaphoreFreeLocksQuantity.Release();
    
            Console.WriteLine($"UNLOCK {lockPosition} -> Semaphore.Release()");
    
            _mainSpinLock = 0;
            Console.WriteLine($"UNLOCK {lockPosition} -> Release()");
    
        }
    
        private struct RangeLock
        {
            public ManualResetEvent UnlockEvent { get; private set; }
            public bool Locked { get; private set; }
    
            public int Offset { get; private set; }
            public int Length { get; private set; }
    
            private bool _initialized = false;
    
            public RangeLock()
            {
            }
    
            private void Initialize()
            {
                if (!_initialized)
                {
                    UnlockEvent = new ManualResetEvent(true);
                    Locked = false;
                    _initialized = true;
                }
            }
            public void Lock(int offset, int length)
            {
                Initialize();
    
                if (Locked)
                {
                    throw new Exception("Already locked");
                }
    
                UnlockEvent.Reset();
                Locked = true;
                Offset = offset;
                Length = length;
            }
    
            public void Unlock()
            {
                if (!Locked)
                {
                    throw new Exception("Already unlocked");
                }
    
                UnlockEvent.Set();
                Locked = false;
            }
    
        }
    
        private class RangeUnlocker : IDisposable
        {
            private bool _disposed;
            private readonly RangeLocker _locker;
            private readonly int _lockPosition;
            public RangeUnlocker(RangeLocker locker, int lockPosition)
            {
                _locker = locker;
                _lockPosition = lockPosition;
            }
    
            protected virtual void Dispose(bool disposing)
            {
                if (!_disposed)
                {
                    if (disposing)
                    {
                        _locker.Release(_lockPosition);
                    }
                    _disposed = true;
                }
            }
    
            public void Dispose()
            {
                Dispose(disposing: true);
                GC.SuppressFinalize(this);
            }
        }
    }
    Ответ написан
    Комментировать
  • Как ускорить поиск элементов из статичного string[] по подстроке?

    @Degot Автор вопроса
    Я сравнил несколько вариантов: Contains, SqliteFTS, Words. И выбрал реализацию Words.
    Псевдо-C#:
    var strings = new string[]; //25 млн записей
    
    var words = new Dictionary<string,HashSet<int>>();
    //формирование "справочника"
    var str = string.Empty;
    for(var stringId = strings.Length - 1; stringId >= 0; stringId--)
    {
        str = strings[stringId];
        var stringWords = NormalizeString(str).Split(' ');
        foreach(var stringWord in stringWords )
        {
            words[stringWord].Add(stringId);
        }
    }
    
    //поиск
    var searchTermWords= NormilizeString(searchTerm).Split(' ')
    var foundIds = new HashSet<int>();
    foreach(var searchTermWord in searchTermWords)
    {
       foreach(var matchWord in words.Keys.Where(x => x.Contains(searcgTermWord)))
       {
      if (words.TryGetValue(matchWord, out var stringIds))
      {
        if (foundIds  == null)
        {
            foundIds = stringIds;
        }
        else
        {
            foundIds = stringIds.Where(x => foundIds .Contains(x)).ToHashSet();
        }
     }
     else
     {
         foundIds  = null;
     }
    }
    }
    
    Console.WriteLine($"Найдено строк: {foundIds.Count} ");


    Тесты разных вариантов для списка объектов с 4мя строковыми полями:
    Поиск: 100 циклов поиска 1-3 символьной подстроки по одному полю
    
    records: ~5 000 000
    
    TestContains (ms):
      -> Max: 434, Avg: 295.56, Median: 281
    
    TestSqliteFTS (ms):
      CREATE -> 111
      INSERT DATA -> 34697 //INSERT INTO temp_table(object_id, поле0, поле1, поле2,  поле3)
      INSERT INDEX -> 161683 // INSERT INTO fts_index(object_id, поле0, поле1, поле2,  поле3 ) SELECT * FROM temp_table
      DROP DATA -> 1191
      VACUUM -> 15849
    
      -> sqlite.db (FTS5: 1.6GB, tokenize = 'trigram', content='',columnsize=0, detail='column')
      -> Max: 10, Avg: 1.16, Median: 0
      
    TestWords (ms):
      CREATE -> 89
      INSERT DATA -> 98851 //INSERT INTO temp_table(word_id, object_id)
      AGGREGATE DATA -> 28504 //SELET object_id FROM temp_table WHERE @word_id  -> FastPFor -> INSERT word_id, object_ids_as_bytes
      DROP DATA -> 1360
      CREATE INDICES-> 9
      VACUUM -> 262
    
      -> sqlite.db (CUSTOM: 9.5MB, (tbl: fields -> id, value), (tbl: words -> id, field_id, value), (tbl: data -> word_id INTEGER, integersQty INTEGER, bytes BLOB))
      -> Max: 128, Avg: 18.78, Median: 1
      
      Статы:
        field_id    wordsQty   maxRefsQty  avgRefsQty  maxRefsBytes    avgRefsBytes
        0           24075	    6461929	    271         910000          52
        1	        5339	    23858735	4515	    3336816         667
        2       	3602	    6766040     1913        952808          295
        3	        11825	    7595099     744         1069508         123
    
    
    records: ~25 000 000
    
    TestContains (ms):
      -> Max: 2568, Avg: 1524.47, Median: 1437.5
    
    TestSqliteFTS (ms):
      CREATE -> 135
      INSERT DATA -> 255882 //INSERT INTO temp_table(object_id, поле0, поле1, поле2,  поле3)
      INSERT INDEX -> 1022499 // INSERT INTO fts_index(object_id, поле0, поле1, поле2,  поле3 ) SELECT * FROM temp_table
      DROP DATA -> 370118
      VACUUM -> 1230845
      
      -> sqlite.db (FTS5: 8.1GB, tokenize = 'trigram', content='',columnsize=0, detail='column')
      -> Max: 587, Avg: 11.53, Median: 0
    
    TestWords (ms):
      CREATE -> 107
      INSERT DATA -> 581050 //INSERT INTO temp_table(word_id, object_id)
      AGGREGATE DATA -> 132700 //SELET object_id FROM temp_table WHERE @word_id  -> FastPFor -> INSERT word_id, object_ids_as_bytes
      DROP DATA -> 6855
      CREATE INDICES-> 32
      VACUUM -> 1161
    
      -> sqlite.db (CUSTOM: 35MB, (tbl: fields -> id, value), (tbl: words -> id, field_id, value), (tbl: data -> word_id INTEGER, integersQty INTEGER, bytes BLOB))
      -> Max: 492, Avg: 64,87, Median: 1
      
      Статы:
        field_id    wordsQty   maxRefsQty  avgRefsQty  maxRefsBytes    avgRefsBytes    
        0       	24075	    32570729	1355        4586324         205
        1	        5339	    120257135	22577       16818780        3192
        2	        3602	    34103240	9566        4802092         1372
        3	        11825	    38282299	3723        5390372         542


    P.S. После тестирования FastPFor, WAH, RoamingBitmap и LZO для хранения индексов (слово -> индекс строки[]) остановился на Delta + LZO. Итоговый размер индекса: 17MB. Максимальное время поиска 600ms, среднее 7ms.
    Ответ написан
  • Как локализовать набор панорам имея мэппинг точек?

    @Degot Автор вопроса
    Использовать openMVG
    Ответ написан
    Комментировать