Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > очередь для тех, кто без очереди

Автор: _Y_ 29.1.2012, 18:23

Задумался над проблемой стояния в очереди. Имеем очередь. Не важно какую. Например, очередь наборов данных, обрабатываемых каким-то процессом. Новый набор ставится в хвост и по мере обработки предшественников продвигается в голову (ну очереди за пивом все знают). Но, каждый набор данных имеет "коэффициент ветеранности". Чем выше коэффициент - тем быстрее набор данных должен продвигаться из конца в голову.  Для простоты - принцип ускорения не важен. Ну, например, за то время пока набор с коэффициентом 10 сдвинется на 10 мест, набор с  коэффициентом 15 сдвинется, соответственно на 15. При этом мелкие "конфликты" не важны (пусть не 15, а от 14 до 16, скажем). В более сложном варианте, приоритет набора может меняться в то время, пока этот набор стоит в очереди. ------------------  Мне в голову пришло только присвоить каждому набору счетчик и с каждым шагом очереди увеличивать его у всех стоящих в соответствии с коэффициентом. На каждом следующем шаге считать головным набор с наибольшим значением счетчика. Но не чувствуется это разумным - длинная очередь будет жрать ресурсы за счет постоянных пересчетов коэффициентов. Есть ли какие-то более разумные варианты? ЗЫ: Чистый интерес, честно говоря. Никакой программы на эту тему не пишу сейчас.

Автор: tzirechnoy 29.1.2012, 18:44

Классический вариант: сделайте три очереди. Выбирайте 1 элемент из первой (низкоприоритетной), 6 из второй (среднего приоритета)  и 9 из третьей (высокого приоритета). Это не совсем то, что Вы просили -- но приоритеты обеспечивает.

Автор: 1000000dollars 29.1.2012, 19:01

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

Автор: Akina 29.1.2012, 20:24

Цитата(_Y_ @  29.1.2012,  19:23 ) Есть ли какие-то более разумные варианты? Навскидку: я бы для каждого задания ввёл... ммм... ну, скажем, "время гарантированного поступления на обработку"... и ставил бы в очередь именно по этому параметру. Для расчёта же такого времени для новопоступившего задания хранил бы текущий "суммарный вес" очереди, корректируя его после постановки или изъятия в обработку очередного задания.  Соответственно "время гарантированного поступления на обработку" расчитывается, исходя из текущего времени, веса нового задания и среднего веса заданий в очереди.

Автор: 1000000dollars 29.1.2012, 22:14

Akina,  тут проблема в том, что  Цитата(_Y_ @  29.1.2012,  18:23 ) приоритет набора может меняться в то время, пока этот набор стоит в очереди. То есть всю очередь придётся пересчитывать. Ибо в самом хреновом случае поменяются все веса элементов, а это фактически пересоздание очереди.

Автор: _Y_ 29.1.2012, 22:51

Цитата(Akina @  29.1.2012,  20:24 ) "время гарантированного поступления на обработку"... и ставил бы в очередь именно по этому параметру. Вот это я не очень понял. Как это ставить в очередь по параметру?

Автор: Akina 29.1.2012, 23:04

Цитата(_Y_ @  29.1.2012,  23:51 ) Как это ставить в очередь по параметру?  Ну то есть не в конец очереди, а в середину. В соответствии с расчётным приоритетом.

Автор: _Y_ 30.1.2012, 11:50

Цитата(Akina @  29.1.2012,  23:04 ) не в конец очереди, а в середину. В соответствии с расчётным приоритетом.  Понятно. В пронципе, должно вроде работать. Вот, примерно, так получается, если я все правильно понял: Позиция, на которую вставляется новый элемент (p): p = L * K / k где K - средний коеффициент приоритета по всей очереди. L - длина очереди. k - коеффициент приоритета нового элемента. Понятно, что если k < K, элемент ставится в конец. После добавления элемента пересчитываем К и L: K = (K * L + k) / (L + 1) L = L + 1 При отправлении первого элемента на обработку, сначала: L = L - 1 после чего преобразуя первую формулу: K = (K * (L + 1) - k0) / L где k0 - коеффициент приоритета изьятого элемента. Последняя формула особой точности не обеспечивает, но это, по условию задачи, и не обязательно. При изменении приоритета поступаем так же, как и при постановке в очетредь, но вместо длины всей очереди L берем текущую позицию элемента. Вроде все я понял. Или нет? Особой точности не будет, но общий принцип должен работать.

Автор: disputant 30.1.2012, 13:23

А что-то типа очереди с приоритетами из стандартнойго набора STL (http://www.cplusplus.com/reference/stl/priority_queue/) не подойдет?... Раз тут рассматриваются алгоритмы, то вкратце - в очередь встраивать в соответствии с приоритетом. Т.е. очередь - что-то вроде сортированного по приоритету списка. В более сложном варианте динамического приоритета без время от времени выполняемого пересчета, похоже, не обойтись. Но его можно реализовывать как сортировку (если только повышение приоритета, то просто устойчивую, если может быть и понижение - о принципе сортировки надо думать).

Автор: Akina 30.1.2012, 15:27

Цитата(_Y_ @  30.1.2012,  12:50 ) Вроде все я понял. Или нет? Не всё. У тебя не учитывается, сколько элемент уже простоял в очереди... и элемент с наинизшим приоритетом имеет шанс вообще не добраться до исполнения.

Автор: 1000000dollars 30.1.2012, 16:04

Цитата(disputant @  30.1.2012,  13:23 ) время от времени выполняемого пересчета, похоже, не обойтись. Но его можно реализовывать как сортировку Зачем всю-то очередь сортировать? Когда из очереди надо забрать элемент, один проход пузырьком ставит нужный элемент в начало, а дальше обычная выборка.  Ну или поиск делать, вместо сортировки. Особого смысла сортировать всю очередь нет, ибо приоритеты динамические...

Автор: _Y_ 30.1.2012, 16:59

В том и дело, что хочется обойтись без сортировок всей очереди. То, что предлагает Akina, вроде позволяет проводить на каждом шаге мелкие рассчеты и только - гораздо меньше ресурсов съест, чем любая сортировка. Понятно, что в жертву приносится точность. Цитата(disputant @  30.1.2012,  13:23 ) из стандартнойго набора STL   Прошу прощения, но C++ для меня странен и загадочен. Цитата(Akina @  30.1.2012,  15:27 ) У тебя не учитывается, сколько элемент уже простоял в очереди. Ага. Это-то я и забыл. Тогда при постановке в очередь лучше, наверное, брать не L - длину очереди, а некую условную длину очереди M рассчитываемую с учетом того, сколько уже простоял последний элемент. Например так: М = L * (t - t0)/(tl - t0), где t0 - время когда в очередь был поставлен элемент, в настоящий момент являющийся головным. tl - время когда в очередь был поставлен элемент, в настоящий момент являющийся последним. t - настоящий момент времени. Понятно, что при этом новый элемент, имеющий низкий приоритет, получит место в двух трамвайных остановках от хвоста очереди. Такой просто становится в конец. Т.е. формула p = L * K / k будет заменена на p = ( L * (t - t0)/(tl - t0) ) * K / k IF (p > L + 1) p = L + 1

Автор: ksnk 30.1.2012, 17:13

_Y_, Какие накладные расходы существуют? Очередь это массив (доступны все элементы) или список (доступны только голова-хвост)? Не дорого ли к каждому сообщению приписывать его вес? Если недорого, то вес всей очереди будет вычисляться из суммы весов всех сообщений. Каждое сообщение, после постановки в очередь очередного сообщения, увеличивает свой вес. Снятое с очереди сообщение уменьшает вес очереди.  Так гарантированно все сообщения будут обслужены, без малоприоритетных пробок.

Автор: _Y_ 30.1.2012, 18:09

ksnk, но это, как понимаю, подразумевает на каждом шаге обращаться к каждому элементу (переприсваивать вес).  Тогда чем хуже просто на каждом шаге прибавления элемента увеличивать всем остальным вес на их коэффициент приоритетности. Вновьприбывшему элементу давать стартовое значение веса 0. При удалении же удалять тот, у которого, на данный момент, вес наибольший. Это и будет без ошибок. Но при этом накладные расходы будут расти с ростом очереди. -------------------- Давайте рассмотрим практический пример. Процесс или компьютер или группа китайских детей выполняет какие-то задания. Та же группа детей выбирает по какому-то алгоритму какое задание выполнять следующим.  Пока очередь заданий небольшая, можно на каждом шаге ее пересортировывать или пересчитывать вес каждого ждущего задания. А теперь предположим бурный рост китайской экономики. Заданий приходит все больше и больше. А выполняется заданий все меньше и меньше. Поскольку дети все больше времени тратят на выбор того, что же делать следующим. Поэтому и флеймлю я на тему как уменьшить время рассчетов (уж во всяком случае не растить его с ростом очереди), пожертвовав взамен точностью - не очень важно что будет сшито первым: правый кед или левый.

Автор: Akina 30.1.2012, 18:19

Цитата(_Y_ @  30.1.2012,  17:59 ) Тогда при постановке в очередь лучше, наверное, брать не L - длину очереди, а некую условную длину очереди M рассчитываемую с учетом того, сколько уже простоял последний элемент.   Для этого прекрасно подходит системное время - при условии, что известно среднее время исполнения запроса, и разброс невелик. Иначе да, приходится вводить некий синтетический аналог.

Автор: _Y_ 30.1.2012, 18:28

Цитата(Akina @  30.1.2012,  18:19 ) при условии, что известно среднее время исполнения запроса, и разброс невелик А на что повлияют эти условия? Вроде бы продвижение в очереди оценивается по времени стояния. При этом не столь важно сколько времени ушло на каждый шаг.

Автор: ksnk 30.1.2012, 18:59

Тогда нужно определить задачу поточнее    Интересно рассматривать случай, когда поток сообщений слегка "заваливает" очередь сообщений. То есть система обработки сообщений уже не справляется с нагрузкой, и очередь медленно растет, но ресурсы системы позволяют жить в таком состоянии достаточно долго. Примерное определение приоритета: Приоритет означает, что при "заваливании" очереди сообщениями с приоритетом 10 и 1 на каждое обработанное сообщение с приоритетом 1 будет обработано 10 сообщений с 10-м приоритетом. Итого, задача:  Устроить все таким образом, чтобы сообщение с любым приоритетом не "застревало" в очереди навечно, при условии примерно равномерного "заваливания" очереди сообщениями с разным приоритетом. Можно предложить "поиск в глубину". Все сообщения вставляются в конец очереди. При изымании сообщения из очереди будем просматривать X сообщений в глубину очереди и искать среди них сообщение с максимальным приоритетом. У всех сообщений, которые "пропустили" свою очередь - повышать приоритет на 1. Так получится, что очередь будет двигаться, приоритет примерно будет соблюдаться и расходы на обслуживание очереди не будут зависеть от величины очереди.

Автор: Akina 30.1.2012, 22:37

Цитата(ksnk @  30.1.2012,  19:59 ) Итого, задача:  Устроить все таким образом, чтобы сообщение с любым приоритетом не "застревало" в очереди навечно, при условии примерно равномерного "заваливания" очереди сообщениями с разным приоритетом. О том и речь... Допустим, некое сообщение категории "нахрен не надо" приходит на обработку. В полночь... очередь - на 8 часов. Соответственно мы назначаем этому сообщению время обработки 8:00... время идёт... и вот 8:00... и мы обрабатываем именно это сообщение, несмотря на то, что в очереди подпрыгивает парочка секунду назад пришедших сообщений с пометкой "супер-пупер-гипер-срочно". Это при условии, что очередь не переполняется. Если же она переполняется, вместо времени вводим синтетику, которая позволяет дробить любой интервал, тем самым устанавливая нужный порядок обработки. Или, как вариант (который мне лично нравится меньше), вводим динамическую важность сообщения, которая зависит от исходной важности и времени сидения под дверью кабинета обработчика. Главная идея - если было принято решение, что сообщение А обрабатывается раньше сообщения Б, то это решение окончательно и ничем не может быть изменено.

Автор: _Y_ 31.1.2012, 00:14

Так, вроде бы, формула  p = ( L * (t - t0)/(tl - t0) ) * K / k  и обеспечивает отсутствие застревания для любого, даже самого медленного, элемента.  С одной стороны мы забираем элементы и знаменатель (tl - t0) все время уменьшается.  С другой стороны, каждый следующий элемент добавляется через какое-то время после предидущего. Значит t все время растет по сравнению с постоянным tl(i) некоего медленного элемента.  Рано или поздно даже элементы с самым большим приоритетом будут встваляться после этого i-того медленного.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)