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

UPDATE: Здесь моя реализация хешированных хронометров. Пожалуйста, дайте мне знать, если у вас есть идея улучшить производительность и concurrency. (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);
    }
}

ОБНОВЛЕНИЕ. Я решил эту проблему, используя Иерархические и хэш-хромированные колеса. (19-Jan-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() (или уменьшениеKey() и max()).

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

Ответы

Ответ 1

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

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

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

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

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

Ответ 2

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

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

n * insert + n * delete-min > n log n.

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

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

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

Ответ 3

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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

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