Очередь приоритетов, которая позволяет эффективно обновлять приоритет?

Question

ОБНОВЛЕНИЕ: Вот my implementation of Hashed Timing Wheels. Пожалуйста, дайте мне знать, если у вас есть идея улучшить производительность и параллелизм. (20-Jan-2009)

// Sample usage: 
public static void main(String[] args) throws Exception { 
    Timer timer = new HashedWheelTimer(); 
    for (int i = 0; i < 100000; i ++) { 
     timer.newTimeout(new TimerTask() { 
      public void run(Timeout timeout) throws Exception { 
       // Extend another second. 
       timeout.extend(); 
      } 
     }, 1000, TimeUnit.MILLISECONDS); 
    } 
} 

UPDATE: Я решил эту проблему с помощью Hierarchical and Hashed Timing Wheels. (19-янв-2009)

Я пытаюсь реализовать таймер специального назначения в Java, который оптимизирован для обработки таймаута. Например, пользователь может зарегистрировать задачу с мертвой линией, и таймер может уведомить метод обратного вызова пользователя, когда мертвая линия завершена. В большинстве случаев зарегистрированная задача будет выполнена в течение очень короткого промежутка времени, поэтому большинство задач будут отменены (например, task.cancel()) или перенесены в будущее (например, task.rescheduleToLater (1, TimeUnit.SECOND)) ,

Я хочу использовать этот таймер для обнаружения соединения в режиме ожидания (например, закрыть соединение, если сообщение не получено за 10 секунд) и тайм-аут записи (например, вызвать исключение, когда операция записи не будет завершена через 30 секунд). В большинстве случаев тайм-аут не произойдет, клиент отправит сообщение, и ответ будет отправлен, если не возникнет странная проблема с сетью.

Я не могу использовать java.util.Timer или java.util.concurrent. ScheduledThreadPoolExecutor, потому что они предполагают, что большинство задач должны быть отключены. Если задача отменена, отмененная задача сохраняется во внутренней куче до тех пор, пока не вызывается ScheduledThreadPoolExecutor.purge(), и это очень дорогостоящая операция. (O (NlogN) возможно?)

В традиционных кучах или очередях приоритетов, которые я изучил в своих классах CS, обновление приоритета элемента было дорогостоящей операцией (O (logN) во многих случаях, поскольку это может быть только достигается за счет удаления элемента и повторной установки его с новым значением приоритета. Некоторые кучи, такие как куча Фибоначчи, имеют O (1) время операции уменьшенияKey() и min(), но мне нужно, по крайней мере, быстрое увеличениеKey() и min() (или reduceKey() и max()).

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

Answer 1

Как насчет того, чтобы отделить раздачу нормального случая, когда вещи быстро заканчиваются из-за ошибок?

Используйте как хэш-таблицу, так и приоритетную очередь. Когда задача запускается, она помещается в хеш-таблицу, и если она быстро заканчивается, она удаляется в O (1) раз.

Каждую секунду вы просматриваете хеш-таблицу и любые задачи, которые были длительное время, скажем, 0,75 секунды, перемещаются в очередь приоритетов. Очередь приоритетов всегда должна быть небольшой и простой в обращении. Это предполагает, что одна секунда намного меньше времени ожидания, которое вы ищете.

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

Варианты намного сложнее, чем просто использование очереди приоритетов, но довольно легко реализуемые должны быть стабильными.

Answer 2

У вас есть ограничение на количество элементов в очереди - ограничение на сокеты TCP ограничено.

Поэтому проблема ограничена. Я подозреваю, что любая умная структура данных будет медленнее, чем использование встроенных типов.

Answer 3

Есть ли веская причина не использовать java.lang.PriorityQueue? Не удаляет() обрабатывает операции отмены в журнале (N)? Затем выполните свое собственное ожидание в зависимости от времени до элемента на передней панели очереди.

Answer 4

Я думаю, что сохранение всех задач в списке и повторение через них было бы лучше.

Вы должны быть (чтобы) запустить сервер на какой-то довольно мясистой машине, чтобы добраться до пределов, где эта стоимость будет важна?

Answer 5

Некоторая комбинация хешей и структур O (logN) должна делать то, что вы просите.

У меня возникает соблазн спорить с тем, как вы анализируете проблему. В своем комментарии выше вы говорите:

Потому что обновление произойдет очень часто. Предположим, мы отправляем M сообщений на соединение, тогда общее время становится O (MNlogN), которое довольно велико. - Trustin Lee (6 часов назад)

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

Так что если ваше приложение имеет миллиард сокетов, то открыто (действительно ли это возможно?) Стоимость вставки составляет всего около 60 сравнений за сообщение.

Я буду держать пари, что это преждевременная оптимизация: вы фактически не измеряли узкие места в вашей системе с помощью инструмента анализа производительности, такого как CodeAnalyst или VTune.

Во всяком случае, возможно, существует множество способов сделать то, что вы просите, как только вы решите, что ни одна структура не будет делать то, что вы хотите, и вам нужна комбинация сильных и слабых сторон различных алгоритмов.

Одна возможность состоит в том, чтобы разделить домен сокета N на некоторое количество ведер размером B, а затем хэш каждого сокета в один из этих (N/B) ведер. В этом ковше находится куча (или что-то еще) с временем обновления O (log B). Если верхняя граница на N не фиксируется заранее, но может меняться, то вы можете создавать больше ведер динамически, что добавляет немного осложнений, но, безусловно, выполнимо.

В худшем случае сторожевой таймер должен искать очереди (N/B) для истечения срока действия, но я полагаю, что сторожевой таймер не требуется для уничтожения простаивающих сокетов в любом конкретном порядке! То есть, если 10 разъемов простаивали в последнем фрагменте времени, ему не нужно искать этот домен для того, чтобы тайм-аут сначала, разобраться с ним, затем найти тот, который тайм-аут второй и т. Д. Он просто должен отсканировать (N/B) набор ведер и перечислить все тайм-ауты.

Если вас не устраивает линейный массив ведер, вы можете использовать очередь очередей очередей, но вы хотите избежать обновления этой очереди в каждом сообщении, иначе вы вернетесь туда, где вы начали. Вместо этого определите время, меньшее, чем фактический тайм-аут.(Скажем, 3/4 или 7/8 из этого), и вы ставите очередь низкого уровня в очередь высокого уровня, если это самое длинное время.

И с риском заявить очевидное, вы не хотите, чтобы ваши очереди наводились на истекли раз. Ключи должны быть начало время. Для каждой записи в очередях прошедшее время необходимо постоянно обновлять, но время начала каждой записи не изменяется.

Answer 6

Ваш конкретный сценарий предлагает мне круговой буфер. Если макс. тайм-аут составляет 30 секунд, и мы хотим использовать сокеты по крайней мере каждую десятую секунды, а затем использовать буфер из 300 дважды связанных списков, по одному на каждую десятую секунды в этот период. Чтобы «увеличить время» в записи, удалите его из списка, в котором он находится, и добавьте его в тот, который используется для нового десятисекундного периода (обе операции с постоянным временем). Когда закончится период, извлеките все оставшееся в текущем списке (возможно, загрузив его в цепочку) и переместите указатель текущего списка.

Answer 7

Использование Hashed Timing Wheel - Google «Хешированные иерархические хромированные колеса» для получения дополнительной информации. Это обобщение ответов, сделанных людьми здесь. Я предпочел бы хромированное колесо синхронизации с большим размером колеса до иерархических колес.

Answer 8

Насколько я знаю (я написал статью о новой очереди приоритетов, которая также рассмотрела прошлые результаты), реализация очереди приоритетов не получает границы кучи Фибоначчи, а также ключ увеличения времени.

Существует небольшая проблема с получением этого буквально. Если вы можете получить ключ увеличения в O (1), то вы можете получить delete в O (1) - просто увеличьте ключ до + бесконечности (вы можете обрабатывать очередь, заполненную множеством + бесконечность, используя некоторые стандартные арифметические трюки). Но если find-min также O (1), это означает, что delete-min = find-min + delete становится O (1). Это невозможно в приоритетной очереди сравнения на основе, так как сортировка оценка подразумевает (вставить все, а затем удалить один за одним), что

п * вставка + п * Ненужное-минутных > н лог н.

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

• Не быть сравнение исходя из. На самом деле, это довольно хороший способ обойти вещи, например. vEB trees.
• Принять O (log n) для вставок, а также O (n log n) для make-heap (с учетом n начальных значений). Это отстой.
• Принять O (log n) для поиска-мин. Это вполне приемлемо, если вы никогда не делали do find-min (без сопровождающего удаления).

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

Answer 9

Существует очень простой способ сделать все вставки и удалить в O (1), воспользовавшись тем, что 1) приоритет основан на времени и 2) вы, вероятно, имеете небольшое фиксированное количество длительностей времени ожидания.

1. Создайте очередную очередь FIFO, чтобы удержать все задачи с таким таймаутом за 10 секунд.Поскольку все задачи имеют одинаковые длительности тайм-аута, вы можете просто вставить их в конец и удалить с самого начала, чтобы сортировать очередь.
2. Создайте еще одну очередь FIFO для задач с 30-секундной продолжительностью таймаута. Создайте больше очередей для других периодов времени ожидания.
3. Чтобы отменить, удалите элемент из очереди. Это O (1), если очередь реализована как связанный список.
4. Перепланирование может быть выполнено как отмена-вставка, так как обе операции O (1). Обратите внимание, что задачи могут быть перенесены в разные очереди.
5. И, наконец, чтобы объединить все очереди FIFO в одну общую очередь приоритетов, запустите головку каждой очереди FIFO в обычной куче. Глава этой кучи будет задачей с скорейшим истечением таймаута из ВСЕХ задач.

Если у вас есть количество различных длительностей времени ожидания, сложность для каждой операции общей структуры равна O (log m). Вставка - O (log m) из-за необходимости искать, в какую очередь вставлять. Remove-min - O (log m) для восстановления кучи. Отмена - это O (1), но в худшем случае O (log m), если вы отменяете голову очереди. Так как m - небольшое фиксированное число, O (log m) по существу O (1). Количество задач не масштабируется.