Приоритетная очередь, которая позволяет эффективно обновлять приоритет?
https://stackoverflow.com/questions/450180
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Обновить:Вот моя реализация хэшированных колес газораспределения.Пожалуйста, дайте мне знать, если у вас есть идея улучшить производительность и параллелизм.(20 января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 января2009)
Я пытаюсь реализовать специальный таймер на Java, который оптимизирован для обработки таймаута.Например, пользователь может зарегистрировать задачу с мертвой линией, и таймер может уведомить метод обратного вызова пользователя о завершении мертвой линии.В большинстве случаев зарегистрированная задача будет выполнена в течение очень короткого промежутка времени, поэтому большинство задач будут отменены (например,задача.отменить()) или перенести на будущее (напримерзадача.Перенесена позже (1, временная единица.ВТОРАЯ)).
Я хочу использовать этот таймер для обнаружения незанятого подключения к сокету (напримерзакройте соединение, если в течение 10 секунд не будет получено ни одного сообщения) и запишите тайм-аут (напримервызовите исключение, если операция записи не будет завершена в течение 30 секунд.) В большинстве случаев тайм-аут не наступит, клиент отправит сообщение, и ответ будет отправлен, если только не возникнет странная проблема с сетью..
Я не могу использовать java.util.Timer или java.util.concurrent.ScheduledThreadPoolExecutor, потому что они предполагают, что время ожидания большинства задач истекло.Если задача отменена, отмененная задача сохраняется в ее внутренней куче до тех пор, пока не будет вызван ScheduledThreadPoolExecutor.purge(), а это очень дорогостоящая операция.(O(NlogN) возможно?)
В традиционных кучах или очередях приоритетов, которые я изучал на своих занятиях CS, обновление приоритета элемента во многих случаях было дорогостоящей операцией (O (logN), потому что это может быть достигнуто только путем удаления элемента и повторной вставки его с новым значением приоритета.Некоторые кучи, такие как куча Фибоначчи, имеют O (1) время выполнения операций DecreaseKey () и min (), но что мне нужно, по крайней мере, это быстрое увеличение Key() и min() (или уменьшение Key() и max ()).
Знаете ли вы какую-либо структуру данных, которая была бы высоко оптимизирована для данного конкретного варианта использования?Одна стратегия, о которой я думаю, - это просто хранить все задачи в хэш-таблице и повторять все задачи каждую секунду или около того, но это не так красиво.
Решение
Как насчет того, чтобы попытаться отделить обработку обычного случая, когда все быстро завершается, от случаев ошибки?
Используйте как хеш-таблицу, так и очередь с приоритетами. Когда задача запускается, она помещается в хеш-таблицу, а если она быстро завершается, она удаляется за O (1).
Каждую секунду вы сканируете хеш-таблицу, и любые задачи, которые были длительными, например, 0,75 секунды, перемещаются в очередь с приоритетами. Очередь приоритетов всегда должна быть небольшой и простой в обращении. Это предполагает, что одна секунда намного меньше времени ожидания, которое вы ищете.
Если сканирование хеш-таблицы происходит слишком медленно, вы можете использовать две хеш-таблицы, в основном одну для четных секунд и одну для нечетных секунд. Когда задача запускается, она помещается в текущую хеш-таблицу. Каждую секунду все задачи из текущей хеш-таблицы перемещаются в очередь с приоритетами и меняются местами, так что текущая хэш-таблица теперь пуста, а нетоковая таблица содержит задачи, запущенные от одной до двух секунд назад.
Там параметры намного сложнее, чем просто использование очереди приоритетов, но их довольно легко реализовать, они должны быть стабильными.
Другие советы
Насколько мне известно (я написал статью о новой очереди приоритетов, в которой также были рассмотрены прошлые результаты), ни одна реализация очереди приоритетов не получает границ куч Фибоначчи, а также ключа увеличения с постоянным временем.
Есть небольшая проблема с тем, чтобы понять это буквально.Если бы вы могли получить ключ увеличения в O (1), тогда вы могли бы получить удаление в O (1) - просто увеличьте ключ до + бесконечности (вы можете обрабатывать очередь, заполненную множеством + бесконечностей, используя некоторые стандартные приемы амортизации).Но если find-min также равен O (1), это означает, что delete-min = find-min + delete становится O (1).Это невозможно в очереди приоритетов на основе сравнения, потому что граница сортировки подразумевает (вставьте все, затем удалите по одному), что
n * вставить + n * удалить-min > n log n.
В чем суть здесь заключается в том, что если вы хотите, чтобы приоритетная очередь поддерживала увеличение ключа в O (1), то вы должны принять одно из следующих наказаний:
- Не должно основываться на сравнении.На самом деле, это довольно хороший способ обойти проблемы, например Веб - деревья.
- Примите O (log n) для вставок, а также O (n log n) для создания кучи (учитывая n начальных значений).Это отстой.
- Примите O (log n) для поиска-мин.Это вполне приемлемо, если вы никогда на самом деле делай найти-минимум (без сопутствующего удаления).
Но, опять же, насколько мне известно, никто не использовал последний вариант.Я всегда рассматривал это как возможность для получения новых результатов в довольно простой области структур данных.
Используйте Колесо хеширования - иерархия хэширования Google Колеса Timing 'для получения дополнительной информации. Это обобщение ответов, сделанных людьми здесь. Я бы предпочел хешированное колесо ГРМ с большим размером колеса, чем иерархическое колесо ГРМ.
Некоторая комбинация хэшей и структур 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 от этого), и вы помещаете очередь низкого уровня в очередь высокого уровня только в том случае, если ее длительность превышает это значение.
И рискуя заявить очевидное, вы не хотите, чтобы ваши очереди были включены истекший время.Ключи должны быть начать время.Для каждой записи в очередях прошедшее время должно постоянно обновляться, но время начала каждой записи не меняется.
Существует ОЧЕНЬ простой способ сделать все вставки и удаления в O (1), используя тот факт, что 1) приоритет основан на времени и 2) у вас, вероятно, есть небольшое фиксированное количество длительностей тайм-аута. <Ол>
Если у вас есть m различных длительностей тайм-аута, сложность для каждой операции всей структуры составляет O (log m). Вставка - O (log m) из-за необходимости искать, в какую очередь вставлять. Remove-min - это O (log m) для восстановления кучи. Отмена - это O (1), но в худшем случае O (log m), если вы отменяете заголовок очереди. Поскольку m - это небольшое фиксированное число, O (log m) по существу равно O (1). Он не масштабируется с количеством задач.
Ваш конкретный сценарий предлагает мне круговой буфер. Если макс. Тайм-аут составляет 30 секунд, и мы хотим собирать сокеты, по крайней мере, каждую десятую секунды, а затем использовать буфер из 300 двусвязных списков, по одному на каждую десятую секунды в этом периоде. Чтобы «увеличить» время для записи, удалите ее из списка, в котором она находится, и добавьте его к списку для нового десятого секунды (обе операции в постоянном времени). Когда период заканчивается, пожните все, что осталось в текущем списке (возможно, передав его в поток жнеца) и продвиньте указатель текущего списка.
У вас есть жесткое ограничение на количество элементов в очереди - есть ограничение для сокетов TCP.
Поэтому проблема ограничена. Я подозреваю, что любая умная структура данных будет медленнее, чем использование встроенных типов.
Есть ли веская причина не использовать java.lang.PriorityQueue? Не обрабатывает ли remove () ваши операции отмены за время log (N)? Затем реализуйте собственное ожидание в зависимости от времени, пока элемент находится в начале очереди.
Я думаю, что было бы лучше сохранить все задачи в списке и выполнить их итерацию.
Вы должны (собираетесь) запустить сервер на какой-то довольно сложной машине, чтобы достичь пределов, где эта стоимость будет важна?
