25.06.2018 Хитрая очередь с приоритетом
 
Привет всем!

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

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#.
Хотел было в Алгоритмы написать, но там как на кладбище.

Спасибо.

 
 
 
 
10.12  .NET Reactor
15.11  n
15.11  C# ClickOnce