Что значит “комбинированный алгоритм для её обслуживания”?

#алгоритм

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


Необходим некоторый пример для ясности как реализовать список используя комбинированный
алгоритм обслуживания.
    

Ответы

Ответ 1

Мне кажется, что, в данном случае, имеется в виду, что надо использовать несколько
алгоритмов, например для поиска:

Class list {
  function search(element) {
    if(this.size > 100){
       //ищем делением пополам например исходя из того что при добавлении мы храним
отсортированный массив
    }
    else {
    //ищем простым перебором т.к. для малого количества это будет быстре
    }
  }
//аналогично для добавления, удаления, используем разное поведение в зависимости
от контекста
}


Ответ 2

Существуют несколько алгоритмов обработки очередей:
  
  
  традиционный алгоритм FIFO;
  приоритетное обслуживание (Priority Queuing), которое также называют «подавляющим»;
  взвешенные очереди (Weighted Queuing);
  взвешенное справедливое обслуживание (Weighted Fair Queuing, WFQ).
  
  
  Возможно комбинированное применение этих алгоритмов. 


(ref)

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


Ответ 3

Немного теории:

Есть различные методы по реализации работы с очередями, такие как:

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

Взвешенное обслуживание - обеспечивает заданное распределение средней пропускной
способности, но не учитывает требований к задержкам.

И тут приходит на помощь - комбинированный алгоритм обслуживания. В алгоритме подобного
рода поддерживается одна приоритетная очередь, а остальные очереди обслуживаются в
соответствии со взвешенным алгоритмом. Обычно приоритетная очередь используется для
чувствительного к задержкам трафика, а остальные — для эластичного трафика (тип трафика,
поддерживаемый IP-сетями) нескольких классов. Каждый класс эластичного трафика получает
некоторый минимум пропускной способности при перегрузках. Этот минимум вычисляется
как процент от пропускной способности, оставшейся от приоритетного трафика.

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

Возможно источник не 100% попадет в твою задачу и не все из этого тебе понадобится,
но само понимание и принцип работы описан.


Ответ 4

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

Сперва обслуживается очередь с самым высоким приоритетом.

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

Допустим есть 3 очереди(кроме главной) с потоком в 10, 5 и 1 элемент в единицу времени.
соответсвующее стрессовое значение 1.6, 3.2 и 16, т.о. каждая очередь будет обрабатываться
пропорционально потоку.
А если заполнять очереди 1 раз, то все очереди закончатся примерно в одно и то же время.

Есть вариант задать фиксированное стрессовое значение заранее, но тогда придется
ограничить разницу приоритетов между очередями.


Ответ 5

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

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

Пример 2:

Есть алгоритм: «очередь с приоритетом» предполагает, что объекты, требующие обработки,
ставятся в очередь, а извлекаются из нее не в порядке занесения, а согласно приоритету. 
       Алгоритмы приоритетного обслуживания очень популярны во многих областях вычислительной
техники, в частности в ОС, когда одним приложениям нужно отдать предпочтение перед
другими при их обработке в мультипрограммной смеси. Весь трафик разбивается на небольшое
количество классов, каждому из которых присваивается приоритет. Приоритетное обслуживание
обычно применяется для класса трафика, чувствительного к задержкам, имеющего небольшую
интенсивность. Тогда обслуживание этого класса не слишком ущемляет остальные классы.
Например, голосовой трафик (чувствителен, но его интенсивность обычно не превышает
8-16 Кбит/c).
       Альтернативой приоритетному обслуживанию являются взвешенные очереди. Они
гарантируют всем классам трафика определенный минимум пропускной способности. Под весом
понимается процент предоставляемой классу трафика пропускной способности от полной
пропускной способности выходного интерфейса. С каждой очередью связывается процент
пропускной способности ресурса, гарантируемый ему при перегрузках этого ресурса. 

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