Какой правильный класс коллекции для хранения сортируемого списка?

Question

[mitaichik]

Добрый день.

Условно, Есть список из 5000 объектов.
Список постоянно обновляется - какие-то объекты удаляются, какие-то добавляются.
Сами объекты надо периодически обновлять (просто вызов определенной функции)
Какие-то из них обновляются по событию извне (закономерности нет, скажем случайный объект обновляется по случайному событию)
Остальные нужно постоянно обновлять принудительно (параллельно, в 4 потока)

Задача : сделать так, чтоб при принудительном обновлении в первую очередь обновлялись объекты, которые не обновлялись дольше всего.

Как я вижу решение. Берется какой-то сортированный map - где ключ - последне время обновление. Значение - сам обхект.
Из этого мапа берем первые 4 объекта и пихаем обновление в executer. Выполняется обновление объекта, обновляем ключ, для этого объекта;
После их обновления - берем следующие 4 объекта и так в бесконечном цикле.

Вот только я не нашел подходящего мапа. Из похожего - ConcurrentSkipListMap но там нет возможности взять первые n элементов. Есть похожая коллекция? Или как еще реализовать этот алгоритм?

Comments

[Dmitry Roo]

И - иммутабельность.

Answer 1

[Wataru]

Достаточно списка. При принудительном обновлении берите первый элемент из списка. При любом обновлении перемещайте объект(ы) в конец. Можно перед началом из списка элемент удалить, а после конца в конце вернуть.

Тут вам еще понадобится какая-то структура, чтобы по объекту получить итератор на него в списке. Если у вас объекты каким-то id определяются, то это может быть

std::unordered_map<int, std::list<Object>::iterator>

.

Вам нужен какой-то потокобезопасный список, да. Доставать из списка первые 4 элемента можно и циклом, по одному. Операция быстрая. Или пусть каждый поток сам достает из списка первый элемент, лоча для этого список.

А вообще, есть и Lock-free списки. Если у вас обновления сами по себе очень быстрые операции, то такая структура может быть в итоге работать быстрее.

Edit: простите за C++-ый код. Не заметил, что вопрос с java тегом. В общем, тут нужны какой-то список и hashmap из id в итераторы в этом листе.

Comments

[mitaichik]

Да, согласен. Начал вчера делать и пришел к выводу что мап то и не нужен - достаточно списка.
Тем более что для java (не знаю как в других языках) нет возможности изменить ключ для значения, точно так же приходится удалять и добавлять.

Answer 2

[Александр]

Не сказано главного: какого размера map ? т е сколько объектов ? десятки, сотни, десятки тысяч ?
Второе, что не сказано - с какой частотой надо принудительно обновлять, и с какой частотой валятся события на обновление. Одно дело раз в 20мс другое дело раз в минуту. Либо же надо поддерживать эту структуру сортированной при любом обновлении ?
Wataru вам предлагает вполне ризонно список использовать. Если у вас ключ - это время, то вам мап не нужен вообще. Возьмите очередь (Deque) и пихайте только что обновленный объект в конец.
Для принудительного обновления: берете первые 4 из очереди и раздаете в потоки.
Для обновления по событию: придется сначала найти объект в очереди. Для этого пройтись по ней итератором. Это позволяет, например, ConcurrentLinkedDeque Итератор там потокобезопасен, но не итерирует вставки, которые были после взятия итератора. Т е может быть такой момент, что пока вы итерируете, придет ещё одно событие и всунет вам новый объект который в итератор не попадет. Либо ваш поток обновит порядок, а итератор этого не увидит, поэтому приходящее событие нужно будет ручками синхронизировать с выдачей элементов на принудительное обновление. И что-то лучшее боюсь тут сложно придумать. Дайте больше информации о масштабах задачи. Если объектов много, то возможно вместо простой очереди использовать какой-нибудь TreeMap или ещё что-то такое, где есть доступ по индексу.

Comments

[Wataru]

Более тооо, я предлагал еще по id объектов хранить итератор в списке, чтобы не надо было обходить весь список для поиска объекта. Ну и, я не специалист по жаве, но думаю, что там тоже из дека нельзя удалять элементы из центра. Нужен именно list.

Answer 3

[mayton2019]

Задача : сделать так, чтоб при принудительном обновлении в первую очередь обновлялись объекты, которые не обновлялись дольше всего.

Мне не очень понятно, что мешает их обновить сразу?

Стоимость операций с HashMap, TreeMap достаточно дешевая чтобы этим вопросом вообще не
беспокоиться.

Если бы у тебя было очень много объектов и они не влазали бы в heap, то тогда я-бы предложил
LRU Cache (Last Recently Used). Но у тебя 5000 объектов. Это мало для БД и кеша горячих объектов.