Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / WinForms, .Net Framework Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Хитрая очередь с приоритетом без блокировок  [new]
SergASh
Member

Откуда:
Сообщений: 167
Привет всем!

Имеется последовательность элементов вот такого вида:

class Item
{
  int ID;
  decimal Level;
  decimal Measurement1;
  ...
  decimal MeasurementN;
}


Нужно придумать структуру данных для хранения этой последовательности,
чтобы она обслуживала вот такой алгоритм:

Есть два потока - обновлятель и читатель.

Читатель должен иметь возможность
1. Наблюдать эту последовательность всегда упорядоченной по Level
2. Безопасно итерировать по ней без блокировок

Обновлятель должен уметь
1. вставлять новые элементы. Что есть новый и что не новый определяется по Id
2. удалять существующие
3. обновлять измеренные значения. В идеале и Level тоже, но если не получится - переживу
4. избегать копирования больших объемов данных при вставках и удалениях
5. по возможности выполнять перечисленные операции за логарифмическое время

Изменения происходят со скоростью 10^2 в секунду. Длина последовательности порядка 10^4.
Несколько независимых экземпляров этого алгоритма должны работать в одном процессе с
разными, никак не связанными экземплярами последовательностей. Экземпляров этих будет
порядка 10^1.

Читатель просматривает последовательность несколько раз в секунду. Важно, чтобы он всегда
просматривал ее в порядке убывания Level. Допустимо, что во время просмотра обновлятель
что-то поменяет. Главное, чтобы это обновление не обрушило читателю foreach и не привело
к тому, что порядок просмотра перестанет быть упорядочен по Level.

Мысли крутятся вокруг очереди с приоритетом. Но тут есть два независимых ключа, по одному
идет поиск, а по другому - сортировка. Этого известный мне алгоритм очереди с приоритетом
на основе бинарной кучи не поддерживает.

Язык реализации C#.

Спасибо
25 июн 18, 13:33    [21518500]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Cat2
Member

Откуда: Petroskoi, Karjala
Сообщений: 145678
SergASh
1. Наблюдать эту последовательность всегда упорядоченной по Level

А где "эта" последовательность?

Measurement1-MeasurementN ? Как она может быть упорядочена по Level?
25 июн 18, 13:46    [21518546]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Cat2
Member

Откуда: Petroskoi, Karjala
Сообщений: 145678
Извините вопрос снимается. Невнимательно прочитал условие
25 июн 18, 13:47    [21518548]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Cat2
Member

Откуда: Petroskoi, Karjala
Сообщений: 145678
SergASh,

попробуйте ConcurrentBag<T> из

https://msdn.microsoft.com/library/Dd997305(v=VS.100).aspx?f=255&MSPPError=-2147217396

orderby для просмотра можно любой сделать
25 июн 18, 13:56    [21518584]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3658
Cat2,

задание мне тут видится академическое и важно сама реализация такой последовательности.
как я понял из задания, для многопоточности использовать надо ReaderWriterLockSlim
в качестве коллекции использовать LinkedList
Чтоб коллекция всегда была сортированной, нам нужно найти то место, куда вставляем элемент, находим такой элемент через бинарный поиск у которого сложность как раз O(log(n)) и вставляем. Всё остальное, точно так же.
и т.д. и т.п. бесплатное такое точно делать не будут.
25 июн 18, 14:25    [21518696]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
SergASh
2. Безопасно итерировать по ней без блокировок


Roman Mejtes,
А п.п. выше как будет работать без блокировок?
25 июн 18, 14:40    [21518759]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
SergASh
Member

Откуда:
Сообщений: 167
Cat2
SergASh,

попробуйте ConcurrentBag<T> из

orderby для просмотра можно любой сделать


orderby означает копирование всего контейнера и потом сортировку. Это, мягко говоря, не очень эффективно
25 июн 18, 15:11    [21518891]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
SergASh,
Для foreach блокировка по любому нужна при изменении. Неважно на каком уровне кода.
Imho
25 июн 18, 15:15    [21518903]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Cat2
Member

Откуда: Petroskoi, Karjala
Сообщений: 145678
SergASh
Cat2
SergASh,

попробуйте ConcurrentBag<T> из

orderby для просмотра можно любой сделать


orderby означает копирование всего контейнера и потом сортировку. Это, мягко говоря, не очень эффективно

Так как раз и получится "версионная" изолированность обработки, что вроде и надо автору
SergASh
Допустимо, что во время просмотра обновлятель
что-то поменяет. Главное, чтобы это обновление не обрушило читателю foreach и не привело
к тому, что порядок просмотра перестанет быть упорядочен по Level.
25 июн 18, 15:24    [21518937]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
fkthat
Member

Откуда:
Сообщений: 1754
Во время foreach коллекцию менять нельзя в принципе - это в сам .NET встроено. Будет иксепшен.
25 июн 18, 16:48    [21519187]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3658
смысл в том, чтоб вставлять элементы с учётом их положения после сортировки. Так как список изначально (по заданию) сортирован для него доступен бинарый поиск, который соответствующий "логорифмической сложности" O(log2n) что соответствует заданию
Нужно найти положение элемента и вставить его через Insert
в List<T>
Вот примерный, вариант для вставки элемента в коллекцию, с учётом сортировки

        static void Main(string[] args)
        {
            var list = new List<int>(new int[] { 1, 2, 3, 5, 8, 10 });
            int insertItem = 9;
            var index = list.BinarySearch(insertItem);
            if (index < 0)
            {
                list.Insert(-index - 1, insertItem);
            }
            Console.WriteLine(index);
            Console.WriteLine(string.Join(",", list));
            Console.ReadKey();
        }
25 июн 18, 20:58    [21519868]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3658
Roman Mejtes
        static void Main(string[] args)
        {
            var list = new List<int>(new int[] { 1, 2, 3, 5, 8, 10 });
            int insertItem = 9;
            var index = list.BinarySearch(insertItem);
            if (index < 0)
            {
                list.Insert(~index, insertItem);
            }
            Console.WriteLine(index);
            Console.WriteLine(string.Join(",", list));
            Console.ReadKey();
        }

слегка подправил
25 июн 18, 21:01    [21519876]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3658
В данном примере идет вставка с задержкой в 10 мс (10^2 в секунду) элементов MyStruct, генерируются значения случ. образом.
Каждую секунду коллекция перебирается, подсчитывается её размер и суммарный Measurement и отображается на экран
В коллекции _list элементы всегда в обратной сортировке по Level, по этому читая итератором всегда нужная последовательность.
Добавление\Обновление происходит с O(log2n)
Пример на коленке сделан, сильно не судите строго

using System;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApp3
{
    public struct MyStruct
    {
        public MyStruct(int id, decimal level, decimal measurement)
        {
            Id = id;
            Level = level;
            Measurement = measurement;
        }

        public int Id;
        public decimal Level;
        public decimal Measurement;
    }

    class Program
    {
        static Test _test;
        static void Main(string[] args)
        {
            _test = new Test();

            var tokenSource = new CancellationTokenSource();
            var token = tokenSource.Token;
            var task1 = Task.Run(() =>
            {
                while (!token.IsCancellationRequested)
                {
                    OnWrite();
                    Task.Delay(10).Wait();
                }
            });
            var task2 = Task.Run(() =>
            {
                while (!token.IsCancellationRequested)
                {
                    OnRead();
                    Task.Delay(1000).Wait();
                }
            });

            Console.ReadKey();
            tokenSource.Cancel();
            Task.WaitAll(task1, task2);
            foreach (var i in _test.Read())
            {
                Console.WriteLine($"({i.Id:00};{i.Level:0.0000};{i.Measurement:0.0000})");
            }
            Console.ReadKey();
        }

        private static void OnRead()
        {
            decimal result = 0;
            var count = 0;
            foreach (var i in _test.Read())
            {
                result += i.Measurement;
                count++;
            }
            Console.SetCursorPosition(0, 0);
            Console.Write($"{count},{result}");
        }

        static Random _rnd = new Random(0);

        private static void OnWrite()
        {
            var id = _rnd.Next(0, 100);
            var level = (decimal)_rnd.NextDouble();
            var measure = (decimal)_rnd.NextDouble();
            var insertItem = new MyStruct(id, level, measure);
            _test.InsertOrUpdate(insertItem);
        }

        public class Test
        {

            private readonly List<MyStruct> _list;
            private ReaderWriterLockSlim _lock = new ReaderWriterLockSlim();

            public Test()
            {
                _list = new List<MyStruct>();
            }

            public void InsertOrUpdate(MyStruct item)
            {
                _lock.EnterUpgradeableReadLock();
                var index = _list.BinarySearch(item, Comparer<MyStruct>.Create((x, y) => y.Level.CompareTo(x.Level)));
                _lock.EnterWriteLock();
                if (index < 0)
                {
                    _list.Insert(~index, item);
                }
                else
                {
                    _list[index] = item;
                }
                _lock.ExitWriteLock();
                _lock.ExitUpgradeableReadLock();
            }

            public IEnumerable<MyStruct> Read()
            {
                _lock.EnterReadLock();
                foreach (var i in _list)
                {
                    yield return i;
                }
                _lock.ExitReadLock();
            }
        }
    }
}
25 июн 18, 22:13    [21520037]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Dima T
Member

Откуда:
Сообщений: 14347
Roman Mejtes, внутри List обычный массив, как следствие вставка и удаление требуют сдвига всех последующих элементов, что не быстро и чем ближе к началу - тем медленнее.
26 июн 18, 09:32    [21520673]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
ВМоисеев
Member

Откуда: Редкино
Сообщений: 2056
>SergASh, вчера, 13:33 [21518500]
>… Есть два потока - обновлятель и читатель.
Рассмотри вариант, когда обновлятель измерения пишет не в основной список, а в промежуточный циклический массив.
Читатель с нужной для него скоростью сначала обрабатывает циклический массив с переписью информации в основной список, а уж затем сканирует основной список.
26 июн 18, 11:26    [21521279]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
refreg
Member

Откуда: Саратов
Сообщений: 776
fkthat
Во время foreach коллекцию менять нельзя в принципе - это в сам .NET встроено. Будет иксепшен.
А если свой Enumerator реализовать?
26 июн 18, 12:46    [21521660]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3658
Dima T,

В List<T> для получения элемента коллекции по индексу требует O(1), а у LinkedList O(n).
Вставка в массив это часть алгоритма и она входит в (n), я пренебрегаю данный работой и считаю её за N.
То есть на требования задачи это не влияет.
А вообще есть класс SortedSet<T>, в нём сразу реализовано бинарное дерево и всё остальное, можно использовать его. По сути тоже самое. B для вставки, удаления и извлечения объекта там сложно O(log n)
26 июн 18, 12:54    [21521707]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
fkthat
Member

Откуда:
Сообщений: 1754
refreg
fkthat
Во время foreach коллекцию менять нельзя в принципе - это в сам .NET встроено. Будет иксепшен.
А если свой Enumerator реализовать?


Если свой, то, как бы, можно. Только при этом можно легко нарваться на всякие неприятные вещи, типа, перечисления одного и того же элемента два раза, или наоборот пропуска какого-нибудь элемента. От этого в стандартные коллекции фреймворка и встроена защита в виде запрета на изменение.
26 июн 18, 15:20    [21522382]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
fkthat,
Даже не в ошибке дело, а в самом смысле.
Как будем ходить по элементам если спереди могут всё грохнуть, сзади и прямо под ногами другим потоком?
Смысл foreach - обойти список весь, а не топать где ступенька появилась.
Единственный вариант без блока это версионность, но подходит ли по условию это к ТС.
26 июн 18, 15:44    [21522508]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
refreg
Member

Откуда: Саратов
Сообщений: 776
fkthat
refreg
пропущено...
А если свой Enumerator реализовать?
Если свой, то, как бы, можно. Только при этом можно легко нарваться на всякие неприятные вещи, типа, перечисления одного и того же элемента два раза, или наоборот пропуска какого-нибудь элемента. От этого в стандартные коллекции фреймворка и встроена защита в виде запрета на изменение.
То есть ты против тех задания?
26 июн 18, 16:32    [21522694]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
ViPRos
Member

Откуда:
Сообщений: 9710
Petro123
fkthat,
Даже не в ошибке дело, а в самом смысле.
Как будем ходить по элементам если спереди могут всё грохнуть, сзади и прямо под ногами другим потоком?
Смысл foreach - обойти список весь, а не топать где ступенька появилась.
Единственный вариант без блока это версионность, но подходит ли по условию это к ТС.

надо CQRS + ES :)
26 июн 18, 16:33    [21522697]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
ВМоисеев
Member

Откуда: Редкино
Сообщений: 2056
>SergASh, вчера, 13:33 [21518500]

>Имеется последовательность…

int ID можно ли рассматривать в качестве индекса "последовательности (вектора) порядка 10^4"?
26 июн 18, 19:00    [21523107]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
SergASh
Member

Откуда:
Сообщений: 167
ВМоисеев
int ID можно ли рассматривать в качестве индекса "последовательности (вектора) порядка 10^4"?


По ID элементы последовательности уникальны. Но они идут не подряд, а случайно. Так что выделить память под все возможные айди не получится если в этом был вопрос
27 июн 18, 09:39    [21524160]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
SergASh
Member

Откуда:
Сообщений: 167
Roman Mejtes
Dima T,

А вообще есть класс SortedSet<T>, в нём сразу реализовано бинарное дерево и всё остальное, можно использовать его. По сути тоже самое. B для вставки, удаления и извлечения объекта там сложно O(log n)


SortedSet<T> отсортирован по одному ключу. Чтоб найти там элемент по другому ключу нужен полный перебор.
27 июн 18, 09:45    [21524176]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
SergASh
Member

Откуда:
Сообщений: 167
Petro123
fkthat,
Как будем ходить по элементам если спереди могут всё грохнуть, сзади и прямо под ногами другим потоком?
Смысл foreach - обойти список весь, а не топать где ступенька появилась.
Единственный вариант без блока это версионность, но подходит ли по условию это к ТС.


Эта дилемма понятна. Либо версионность и копирование, либо скорость и хождение по постоянно меняющейся структуре. В этой задаче выбор в пользу последнего.
Если вам известен способ достичь версионности более экономно, чем копированием, то хотелось бы узнать как.
27 июн 18, 09:48    [21524188]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / WinForms, .Net Framework Ответить