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

From

Vovanius Uryvaeff (2:5020/175.2)

To

Alexey Krasnov

Date

2002-10-16T18:54:08Z

Area

RU.ALGORITHMS

From: "Vovanius Uryvaeff" <micro-s@vniiofi.ru>

Sun Oct 13 2002 20:04, Alexey Krasnov wrote to Andrew Ezhguroff:

 AK> Здравствуй.

 AK>  Andrew Ezhguroff => Alexey Krasnov, 12 Октябрь 2002 года, 19:21:

 AE>> Как я понимаю, устройств достаточно мало (раз байтовый адрес)? Ну так
 AE>> организуй отдельные очереди для каждого устройства:
 AE>> loop {бесконечный цикл}
 AE>>   for текущая_очередь:=1 to максимальный_номер_очереди do
 AE>>     if не_пусто(очереди[текущая_очередь]) then
 AE>>       отправка_сообщения(очереди[текущая_очередь])
 AE>>     end if
 AE>>   end for
 AE>> end loop
 AK> Хм. При явном превосходстве количества сообщений в одной из очередей
 AK> желательно конечно обращаться к ней почаще, перемешивая ее с сообщениями
 AK> из других. То есть, опять-таки встает вопрос выбора последовательности
 AK> опросов с наиболее "гладким" распределением.

Для каждой очереди можно посчитать коэффициент K=N*T,
где N - число сообщений в очереди, T - время на обработку пакета в денной
очереди, и посылать каждый раз из той очереди, кде К окажется наибольшим, и
устройство свободно.
(если T одинаково, то его можно считать 1)
Тогда в случае
1 1 1 1 1 2 3 4 5
пакеты будут посланы в порядке
1 2 1 3 1 4 1 5 1

а если, например T1 = 1, T2 = 2 и почередь
1 1 1 1 1 1 2 2 2 2 2 2
2 1 1 2 1 1 2 1 1 2 пауза 2 пауза 2

сможете найти пример, в котором такая стратегия неоптимальна?

EMail send to vovanius<yxo>xakep.ru, please.

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)