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

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

В List<T> для получения элемента коллекции по индексу требует O(1), а у LinkedList O(n).
Вставка в массив это часть алгоритма и она входит в (n), я пренебрегаю данный работой и считаю её за N.
То есть на требования задачи это не влияет

Входящий поток изменений будет включать вставки, удаления и обновления вперемешку. Поэтому если выбрать массив, то его все время придется двигать, а не только вначале. Это выливается в линейную сложность.
27 июн 18, 09:53    [21524204]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Dima T
Member

Откуда:
Сообщений: 13844
SergASh
SortedSet<T> отсортирован по одному ключу. Чтоб найти там элемент по другому ключу нужен полный перебор.

можно использовать несколько SortedSet, по одному на каждый ключ.
27 июн 18, 10:07    [21524256]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
Dima T
SergASh
SortedSet<T> отсортирован по одному ключу. Чтоб найти там элемент по другому ключу нужен полный перебор.

можно использовать несколько SortedSet, по одному на каждый ключ.
+1
Несколько SortedSet над одной коллекцией.
27 июн 18, 10:29    [21524380]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
ViPRos
Member

Откуда:
Сообщений: 9560
Petro123,

лучше использовать MSSQL, там ACID реализован хорошо
27 июн 18, 13:01    [21524967]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
ViPRos
Member

Откуда:
Сообщений: 9560
А еще говорят можно CQRS + ES :):)
27 июн 18, 13:03    [21524971]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
hVostt
Member

Откуда:
Сообщений: 15624
ViPRos
А еще говорят можно CQRS + ES :):)


Рад, что такая хорошая технология сегодня на слуху :)
Но это в свою очередь означает, что её будут применять там, где она совершенно не нужна, для небольших и односложных проектов, ожидается поток разочарования.
27 июн 18, 13:55    [21525142]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
hVostt,
На слуху).
Только тема про уровень программирования пониже).
27 июн 18, 14:02    [21525183]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
ВМоисеев
Member

Откуда: Редкино
Сообщений: 1979
>SergASh, сегодня, 09:39 [21524160]
>...Но они идут не подряд, а случайно…
Тогда рассмотри такой вариант:
1. Создаём одномерный массив aItem и nItem - текущий индекс записи след. Item
2. Создаём
SortedDictionary<decimal, int> sdLevel = new SortedDictionary<decimal, int>();
3. Создаём
SortedDictionary<decimal, int> sdID = new SortedDictionary<decimal, int>();

При добавлении Item пишем в массив по индексу nItem, добавляем индекс в словари и nItem++ (а может быть второй словарь и не нужен).
27 июн 18, 14:31    [21525268]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
ВМоисеев,
Класс не потокобезопасен. При допиле нужно ставит локи. А по ТЗ нельзя.
27 июн 18, 14:38    [21525291]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Dima T
Member

Откуда:
Сообщений: 13844
Petro123
ВМоисеев,
Класс не потокобезопасен. При допиле нужно ставит локи. А по ТЗ нельзя.

В ТЗ про локи ничего не сказано, только в названии темы "без блокировок", я так понимаю это не из ТЗ, а хотелка ТС`а.
27 июн 18, 14:48    [21525340]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
Dima T,
Я привык в тему выносить главное)).
Ок.
Ждем автора.
27 июн 18, 15:02    [21525393]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
ВМоисеев
Member

Откуда: Редкино
Сообщений: 1979
>Petro123, сегодня, 14:38 [21525291]
>Класс не потокобезопасен…
Понимаю, но ранее предложил TC применить демфер в виде циклической очереди. Потоки писателя и читателя разделены.
27 июн 18, 15:09    [21525421]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Cat2
Member

Откуда: Petroskoi, Karjala
Сообщений: 145633
Программирование всегда есть компромисс между желаниями и возможности.
Возможно ТС стоит переформулировать задачу. Пускай Читатель запрашивает данные только тогда, когда транзакция Обновлятеля закончилась, а не по таймеру
28 июн 18, 23:11    [21529956]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
Cat2
Программирование всегда есть компромисс
+1
29 июн 18, 07:04    [21530243]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
ВМоисеев
Member

Откуда: Редкино
Сообщений: 1979
>Cat2, вчера, 23:11 [21529956]
>... Пускай Читатель запрашивает …
Подобные конструкции позволяет писать/читать в любой момент разными потоками:

    int ИЗ=0;  //-- индекс элемента записи
    int ИЧ=0;  //-- индекс элемента чтения
    const int Размер=128;  //-- размер циклической очереди
    const int Маска=~128;  //-- маска размера циклической очереди
    Item[] aItem=new Item[Размер];
 
    //-- Читаем Item из циклической очереди (буфера, массива)
    //=================================================
    Item fЧитаемItem() { 
      Item item= 0;
      if(ИЗ!=ИЧ) { item=aItem[ИЧ]; ИЧ = ++ИЧ & Маска; }
      return item; 
    }
    //-- Пишем Item в циклическую очередь
    //=================================================
    void fПишемItem(Item item) { aItem[ИЗ]=item; ИЗ = ++ИЗ & Маска; }
  }



Пусть Обновлятель только пишет данные (Item), Читатель же обновляет структуры и представляет данные
29 июн 18, 09:55    [21530474]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
ВМоисеев,
Переименовал бы ты свои ИЗ и ИЧ и ХУ.
Читать даже не хочется.
29 июн 18, 10:31    [21530588]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Cat2
Member

Откуда: Petroskoi, Karjala
Сообщений: 145633
ВМоисеев,

Да можно всякого напридумывать. Транзакционные механизмы известны.

Было бы интересно услышать от ТС физический смысл задачи, тогда оценить риски получения неверной информации было бы легче.

У меня впечатление, что это какие-то датчики и их считыватели

SergASh
Длина последовательности порядка 10^4.

Длина последовательности в 10000 - это вообще тьфу, но для скорости Читателя можно разделить Item на два класса.
В одном классе только ID и Level, а так же возможно, метка того, что объект находится в обработке.

class Item
{
  int ID;
  decimal Level;
  bool Commited;
}

class ItemSource
{
  int ID;
  decimal Measurement1;
  ...
  decimal MeasurementN;
}
29 июн 18, 10:37    [21530617]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Dima T
Member

Откуда:
Сообщений: 13844
ИМХО не надо тут хитрые очереди изобретать, стандартная справится ConcurrentQueue
29 июн 18, 10:39    [21530625]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Cat2
Member

Откуда: Petroskoi, Karjala
Сообщений: 145633
Dima T
ИМХО не надо тут хитрые очереди изобретать, стандартная справится ConcurrentQueue

Я тоже полагаю, что важность решения задачи сильно преувеличена
29 июн 18, 10:42    [21530641]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Petro123
Member

Откуда: Загрузочный сектор Москвы (AutoPOI.ru)
Сообщений: 38643
Cat2
метка того, что объект находится в обработке.

Cat2
bool Commited;
почти субд изобрели)).
Согласен что нужен выше уровень постановки.
Удачи аффтару!
29 июн 18, 10:54    [21530672]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Cat2
Member

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

Я субдами думаю :)

=================
Как убежденный агностик, я уверен, что нет общих решений, но в каждом конкретном случае можно и нужно находить наилучшее решение.

Мир не познаваем, но можно и должно познать его отдельные законы и проявления
29 июн 18, 11:34    [21530806]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
ВМоисеев
Member

Откуда: Редкино
Сообщений: 1979
>Cat2, сегодня, 10:37 [21530617]
>...для скорости Читателя можно разделить Item на два класса

Покажите, как сиё увеличивает скорострельность.
29 июн 18, 11:53    [21530892]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3408
если нужна система реального времени, без блокировок, то не надо забывать, что при работе GC для очистки 2 поколения, все остальные потоки тоже блокируются.
29 июн 18, 12:17    [21530951]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
ВМоисеев
Member

Откуда: Редкино
Сообщений: 1979
>Dima T, сегодня, 10:39 [21530625]
>ИМХО не надо тут хитрые очереди изобретать…
На вкус, на цвет.
Для ограниченных по времени экспериментов применял и примерно такую конструкцию:
    int ИЗ = 0;  //-- индекс элемента записи
    int ИЧ = 0;  //-- индекс элемента чтения
    const int Размер = 128;  //-- размер циклической очереди
    const int Маска = ~128;  //-- маска размера циклической очереди
    Item[] aItem = new Item[Размер];

    //-- Читаем Item из циклической очереди
    //=================================================
    Item fЧитаемItem() { return (ИЗ != ИЧ)? aItem[ИЧ++ & Маска]:null; }
    
    //-- Пишем Item в циклическую очередь
    //=================================================
    void fПишемItem(Item item) { aItem[ИЗ++ & Маска]=item; }


но это был не C# и не персоналка.
29 июн 18, 12:25    [21530991]     Ответить | Цитировать Сообщить модератору
 Re: Хитрая очередь с приоритетом без блокировок  [new]
Cat2
Member

Откуда: Petroskoi, Karjala
Сообщений: 145633
ВМоисеев
>Cat2, сегодня, 10:37 [21530617]
>...для скорости Читателя можно разделить Item на два класса

Покажите, как сиё увеличивает скорострельность.

Если последовательность

decimal Measurement1;
  ...
  decimal MeasurementN;

занимает килобайты, то быстрее пройти по тем объектам, которые изменились со времени прошлого изменения. Я же не задачу решаю, а показываю, как бы я решал
29 июн 18, 13:45    [21531247]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2]      все
Все форумы / WinForms, .Net Framework Ответить