LINUX.ORG.RU

Кровь, кишки, java concurrency

 


0

1

Нужно реализовать хитрую конкурентную структуру данных. Название даже еще не придумал :). Интерфейс сходен с блокирующей очередью: неблокирующий метод put, блокирующий метод take(). Очередь работает как временное окно, которое содержит уникальный set элементов, а метод take() возвращяет каждый элемент не чаще, чем раз в T миллисекунд. Элементы проверяются на равенство стандартно, через equals. То есть для всего входного потока сообщений, есть подпоследовательность элементов внутри которого все элементы equals. А на выходе мы хотим полить эту последовательность, получая апдейт элемента не чаще, чем раз в T. Когда мы первый раз делаем take() элементы возвращяются сразу, в FIFO порядке, затем последующий апдейт по мере поступления в очередь, но не чаще, чем раз в T.

Дополнительные плюшки: нужно иметь возможность перезапросить апдейт (неблокирующий метод get), который так же записывает последнее время использования элемента, еще нужна возможность вернуть элемент в очередь (не смогли обработать).

У меня есть страшненький прототип этой штуки. Не надеюсь, что кто-то будет продумывать весь этот гемор за меня, но вдруг делал что-то похожее.

★★★★★

Последнее исправление: maxcom (всего исправлений: 1)

Ответ на: комментарий от PolarFox

На вход летят несколько апдейтов в секунду на некоторые значения (порядка 1000 элементов). Все эти апдейты обрабатывать не нужно. Но есть требование в 1 секунду для максимальной latency обработки одного элемента.

dizza ★★★★★
() автор топика

Кольцевой буфер указателей на таймстамп записи не подойдет?

P.S. Если уж put, то тогда уже get.

rimsleur
()
Ответ на: комментарий от rimsleur

А как на кольцевом буфере сделать блокирующую операцию, которая просыпается по истечении таймера?

В моей реализации элементы валяются в DelayQueue + мепа таймстемпов, которые и определяют порядок. Для обеспечения уникальности элементов конкарент мепа рядом лежит.

dizza ★★★★★
() автор топика
Ответ на: комментарий от dizza

На кольцевом наверное никак. Думаю, тогда я не совсем понял, что нужно. Хотя не уверен что понимаю сейчас. А что значит блокирующую? Что и для чего нужно блокировать?

Что если список таймстампов держать сортированным?

rimsleur
()
Ответ на: комментарий от rimsleur

Когда мы делаем take(), то этот метод не возвращяет управление сразу, а дожидается, когда выполнятся 2 условия: очередь должна быть не пуста, а следующий элемент должен быть последний раз вытащен не менее чем за T времени.

Что если список таймстампов держать сортированным?

Да эту проблему уже решил. Таймстемпы хранятся в двоичной куче, которая отдает наименьший за O(1).

dizza ★★★★★
() автор топика
Ответ на: комментарий от dizza

Таймстемпы хранятся в двоичной куче, которая отдает наименьший за O(1)

Что за куча такая? Обычно нужно log(N), чтобы при изъятии наименьшего элемента поправить кучу.

kamre ★★★
()
Ответ на: комментарий от dizza

Сор, не обращяйте внимание на этот комент.

dizza ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.