mitaichik
@mitaichik

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

Добрый день.

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

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

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

Вот только я не нашел подходящего мапа. Из похожего - ConcurrentSkipListMap но там нет возможности взять первые n элементов. Есть похожая коллекция? Или как еще реализовать этот алгоритм?
  • Вопрос задан
  • 103 просмотра
Решения вопроса 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Достаточно списка. При принудительном обновлении берите первый элемент из списка. При любом обновлении перемещайте объект(ы) в конец. Можно перед началом из списка элемент удалить, а после конца в конце вернуть.

Тут вам еще понадобится какая-то структура, чтобы по объекту получить итератор на него в списке. Если у вас объекты каким-то id определяются, то это может быть
std::unordered_map<int, std::list<Object>::iterator>
.

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

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

Edit: простите за C++-ый код. Не заметил, что вопрос с java тегом. В общем, тут нужны какой-то список и hashmap из id в итераторы в этом листе.
Ответ написан
@Arlekcangp
Разработчик, Лид, Архитектор ПО
Не сказано главного: какого размера map ? т е сколько объектов ? десятки, сотни, десятки тысяч ?
Второе, что не сказано - с какой частотой надо принудительно обновлять, и с какой частотой валятся события на обновление. Одно дело раз в 20мс другое дело раз в минуту. Либо же надо поддерживать эту структуру сортированной при любом обновлении ?
Wataru вам предлагает вполне ризонно список использовать. Если у вас ключ - это время, то вам мап не нужен вообще. Возьмите очередь (Deque) и пихайте только что обновленный объект в конец.
Для принудительного обновления: берете первые 4 из очереди и раздаете в потоки.
Для обновления по событию: придется сначала найти объект в очереди. Для этого пройтись по ней итератором. Это позволяет, например, ConcurrentLinkedDeque Итератор там потокобезопасен, но не итерирует вставки, которые были после взятия итератора. Т е может быть такой момент, что пока вы итерируете, придет ещё одно событие и всунет вам новый объект который в итератор не попадет. Либо ваш поток обновит порядок, а итератор этого не увидит, поэтому приходящее событие нужно будет ручками синхронизировать с выдачей элементов на принудительное обновление. И что-то лучшее боюсь тут сложно придумать. Дайте больше информации о масштабах задачи. Если объектов много, то возможно вместо простой очереди использовать какой-нибудь TreeMap или ещё что-то такое, где есть доступ по индексу.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
mayton2019
@mayton2019 Куратор тега Java
Bigdata Engineer
Задача : сделать так, чтоб при принудительном обновлении в первую очередь обновлялись объекты, которые не обновлялись дольше всего.

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы