Сортировка "наобо рот"

From

Alexey Krasnov (2:5066/196.96)

To

Andrew Ezhguroff

Date

2002-10-13T20:19:20Z

Area

RU.ALGORITHMS

Здравствуй.

 Andrew Ezhguroff => Oleg Khovayko, 12 Октябрь 2002 года, 23:14:

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

 AE> Можно добавлять "новые" очереди не в конец, а сортировать по времени
 AE> отправки последних сообщений из очередей (что немного увеличит
 AE> накладные расходы, зато первым будет получать сообщение процесс,
 AE> который ждет дольше всего).

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

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

Всего хорошего.
-+- GoldED+/386 1.1.4.7. -- : Paul Van Dyk - Live At Home London (Essential Mix 04
---
 * Origin: В лесу родилась ёлочка... в лесу и умрёт. (2:5066/196.96)