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