Задумался над проблемой стояния в очереди.

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

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

Для простоты - принцип ускорения не важен. Ну, например, за то время пока набор с коэффициентом 10 сдвинется на 10 мест, набор с  коэффициентом 15 сдвинется, соответственно на 15. При этом мелкие "конфликты" не важны (пусть не 15, а от 14 до 16, скажем).

В более сложном варианте, приоритет набора может меняться в то время, пока этот набор стоит в очереди.

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

Есть ли какие-то более разумные варианты?

ЗЫ: Чистый интерес, честно говоря. Никакой программы на эту тему не пишу сейчас.

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

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

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

Akina,  тут проблема в том, что 

То есть всю очередь придётся пересчитывать. Ибо в самом хреновом случае поменяются все веса элементов, а это фактически пересоздание очереди.

Вот это я не очень понял. Как это ставить в очередь по параметру?

Ну то есть не в конец очереди, а в середину. В соответствии с расчётным приоритетом.

Понятно. В пронципе, должно вроде работать. Вот, примерно, так получается, если я все правильно понял:

Позиция, на которую вставляется новый элемент (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 берем текущую позицию элемента.

Вроде все я понял. Или нет?

Особой точности не будет, но общий принцип должен работать.


 

А что-то типа очереди с приоритетами из стандартнойго набора STL (http://www.cplusplus.com/reference/stl/priority_queue/) не подойдет?...

Раз тут рассматриваются алгоритмы, то вкратце - в очередь встраивать в соответствии с приоритетом. Т.е. очередь - что-то вроде сортированного по приоритету списка.

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

Это сообщение отредактировал(а) disputant - 30.1.2012, 13:23

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

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

Особого смысла сортировать всю очередь нет, ибо приоритеты динамические...

В том и дело, что хочется обойтись без сортировок всей очереди. То, что предлагает Akina, вроде позволяет проводить на каждом шаге мелкие рассчеты и только - гораздо меньше ресурсов съест, чем любая сортировка. Понятно, что в жертву приносится точность.

 Прошу прощения, но C++ для меня странен и загадочен.


Ага. Это-то я и забыл. Тогда при постановке в очередь лучше, наверное, брать не 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

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

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

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

• Тогда чем хуже просто на каждом шаге прибавления элемента увеличивать всем остальным вес на их коэффициент приоритетности.
• Вновьприбывшему элементу давать стартовое значение веса 0.
• При удалении же удалять тот, у которого, на данный момент, вес наибольший.

Это и будет без ошибок. Но при этом накладные расходы будут расти с ростом очереди.

--------------------

Давайте рассмотрим практический пример.

Процесс или компьютер или группа китайских детей выполняет какие-то задания. Та же группа детей выбирает по какому-то алгоритму какое задание выполнять следующим. 

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

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

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

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