ReSQL.ru
     
powered by simpleCommunicator - 2.0.51     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Хитрая очередь с приоритетом без блокировок
25 сообщений из 50, страница 2 из 2
  2  все
Хитрая очередь с приоритетом без блокировок
    #39666347
SergASh
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergASh
Гость
Roman MejtesDima T,

В List<T> для получения элемента коллекции по индексу требует O(1), а у LinkedList O(n).
Вставка в массив это часть алгоритма и она входит в (n), я пренебрегаю данный работой и считаю её за N.
То есть на требования задачи это не влияет
Входящий поток изменений будет включать вставки, удаления и обновления вперемешку. Поэтому если выбрать массив, то его все время придется двигать, а не только вначале. Это выливается в линейную сложность.
...
Рейтинг: 0 / 0
27.06.2018, 09:53
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39666351
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SergAShSortedSet<T> отсортирован по одному ключу. Чтоб найти там элемент по другому ключу нужен полный перебор.
можно использовать несколько SortedSet, по одному на каждый ключ.
...
Рейтинг: 0 / 0
27.06.2018, 10:07
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39666372
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Petro123
Участник
Dima TSergAShSortedSet<T> отсортирован по одному ключу. Чтоб найти там элемент по другому ключу нужен полный перебор.
можно использовать несколько SortedSet, по одному на каждый ключ.+1
Несколько SortedSet над одной коллекцией.
...
Рейтинг: 0 / 0
27.06.2018, 10:29
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39666493
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ViPRos
Участник
Petro123,

лучше использовать MSSQL, там ACID реализован хорошо
...
Рейтинг: 0 / 0
27.06.2018, 13:01
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39666495
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ViPRos
Участник
А еще говорят можно CQRS + ES :):)
...
Рейтинг: 0 / 0
27.06.2018, 13:03
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39666529
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
ViPRosА еще говорят можно CQRS + ES :):)

Рад, что такая хорошая технология сегодня на слуху :)
Но это в свою очередь означает, что её будут применять там, где она совершенно не нужна, для небольших и односложных проектов, ожидается поток разочарования.
...
Рейтинг: 0 / 0
27.06.2018, 13:55
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39666541
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Petro123
Участник
hVostt,
На слуху).
Только тема про уровень программирования пониже).
...
Рейтинг: 0 / 0
27.06.2018, 14:02
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39666558
ВМоисеев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ВМоисеев
Участник
>SergASh, сегодня, 09:39 http://www.sql.ru/forum/actualutils.aspx?action=gotomsg&tid=1296919&msg=21524160][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++ (а может быть второй словарь и не нужен).
...
Рейтинг: 0 / 0
27.06.2018, 14:31
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39666561
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Petro123
Участник
ВМоисеев,
Класс не потокобезопасен. При допиле нужно ставит локи. А по ТЗ нельзя.
...
Рейтинг: 0 / 0
27.06.2018, 14:38
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39666569
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Petro123ВМоисеев,
Класс не потокобезопасен. При допиле нужно ставит локи. А по ТЗ нельзя.
В ТЗ про локи ничего не сказано, только в названии темы "без блокировок", я так понимаю это не из ТЗ, а хотелка ТС`а.
...
Рейтинг: 0 / 0
27.06.2018, 14:48
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39666584
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Petro123
Участник
Dima T,
Я привык в тему выносить главное)).
Ок.
Ждем автора.
...
Рейтинг: 0 / 0
27.06.2018, 15:02
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39666596
ВМоисеев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ВМоисеев
Участник
>Petro123, сегодня, 14:38 http://www.sql.ru/forum/actualutils.aspx?action=gotomsg&tid=1296919&msg=21525291][21525291]
>Класс не потокобезопасен…
Понимаю, но ранее предложил TC применить демфер в виде циклической очереди. Потоки писателя и читателя разделены.
...
Рейтинг: 0 / 0
27.06.2018, 15:09
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667420
Фотография Cat2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cat2
Модератор форума
Программирование всегда есть компромисс между желаниями и возможности.
Возможно ТС стоит переформулировать задачу. Пускай Читатель запрашивает данные только тогда, когда транзакция Обновлятеля закончилась, а не по таймеру
...
Рейтинг: 0 / 0
28.06.2018, 23:11
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667462
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Petro123
Участник
Cat2Программирование всегда есть компромисс+1
...
Рейтинг: 0 / 0
29.06.2018, 07:04
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667499
ВМоисеев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ВМоисеев
Участник
>Cat2, вчера, 23:11 http://www.sql.ru/forum/actualutils.aspx?action=gotomsg&tid=1296919&msg=21529956] [21529956]
>... Пускай Читатель запрашивает …
Подобные конструкции позволяет писать/читать в любой момент разными потоками:

Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
    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), Читатель же обновляет структуры и представляет данные
...
Рейтинг: 0 / 0
29.06.2018, 09:55
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667512
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Petro123
Участник
ВМоисеев,
Переименовал бы ты свои ИЗ и ИЧ и ХУ.
Читать даже не хочется.
...
Рейтинг: 0 / 0
29.06.2018, 10:31
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667515
Фотография Cat2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cat2
Модератор форума
ВМоисеев,

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

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

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

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

Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
class Item
{
  int ID;
  decimal Level;
  bool Commited;
}

class ItemSource
{
  int ID;
  decimal Measurement1;
  ...
  decimal MeasurementN;
}
...
Рейтинг: 0 / 0
29.06.2018, 10:37
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667516
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
ИМХО не надо тут хитрые очереди изобретать, стандартная справится ConcurrentQueue
...
Рейтинг: 0 / 0
29.06.2018, 10:39
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667520
Фотография Cat2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cat2
Модератор форума
Dima TИМХО не надо тут хитрые очереди изобретать, стандартная справится ConcurrentQueue
Я тоже полагаю, что важность решения задачи сильно преувеличена
...
Рейтинг: 0 / 0
29.06.2018, 10:42
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667526
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Petro123
Участник
Cat2метка того, что объект находится в обработке.
Cat2
Код: c#
1.
bool Commited;

почти субд изобрели)).
Согласен что нужен выше уровень постановки.
Удачи аффтару!
...
Рейтинг: 0 / 0
29.06.2018, 10:54
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667555
Фотография Cat2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cat2
Модератор форума
Petro123,

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

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

Мир не познаваем, но можно и должно познать его отдельные законы и проявления
...
Рейтинг: 0 / 0
29.06.2018, 11:34
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667564
ВМоисеев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ВМоисеев
Участник
>Cat2, сегодня, 10:37 http://www.sql.ru/forum/actualutils.aspx?action=gotomsg&tid=1296919&msg=21530617][21530617]
>...для скорости Читателя можно разделить Item на два класса

Покажите, как сиё увеличивает скорострельность.
...
Рейтинг: 0 / 0
29.06.2018, 11:53
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667573
Roman Mejtes
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Roman Mejtes
Участник
если нужна система реального времени, без блокировок, то не надо забывать, что при работе GC для очистки 2 поколения, все остальные потоки тоже блокируются.
...
Рейтинг: 0 / 0
29.06.2018, 12:17
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667578
ВМоисеев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ВМоисеев
Участник
>Dima T, сегодня, 10:39 http://www.sql.ru/forum/actualutils.aspx?action=gotomsg&tid=1296919&msg=21530625] [21530625]
>ИМХО не надо тут хитрые очереди изобретать…
На вкус, на цвет.
Для ограниченных по времени экспериментов применял и примерно такую конструкцию:
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
    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# и не персоналка.
...
Рейтинг: 0 / 0
29.06.2018, 12:25
| Ответить | Цитировать | Написать  
Хитрая очередь с приоритетом без блокировок
    #39667620
Фотография Cat2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Cat2
Модератор форума
ВМоисеев>Cat2, сегодня, 10:37 http://www.sql.ru/forum/actualutils.aspx?action=gotomsg&tid=1296919&msg=21530617][21530617]
>...для скорости Читателя можно разделить Item на два класса

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

Код: c#
1.
2.
3.
decimal Measurement1;
  ...
  decimal MeasurementN;


занимает килобайты, то быстрее пройти по тем объектам, которые изменились со времени прошлого изменения. Я же не задачу решаю, а показываю, как бы я решал
...
Рейтинг: 0 / 0
29.06.2018, 13:45
| Ответить | Цитировать | Написать  
25 сообщений из 50, страница 2 из 2
  2  все
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Хитрая очередь с приоритетом без блокировок
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=20&startmsg=39666347&tid=1399316]:
 0ms
get settings:
 9ms
get forum list:
 12ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 33ms
get topic data:
 8ms
get forum data:
 1ms
get page messages:
 39ms
get tp. blocked users:
 1ms
others: 13ms
total:  122ms
созд. / загр.: 122ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]