Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Сравнение эффективности алгоритмовСодержание книги Поиск на нашем сайте В 1 главе был приведён пример ситуации, когда период обработки Greedy-Balance алгоритма превышал период обработки Sorted-Balance почти в два раза. На практике такая ситуация является исключительной и маловероятной. Для сравнения эффективности алгоритмов будут сгенерированы следующие файлы: количество машин равно 1000, количество задач будет равно 2000, 5000 и 10000. Время выполнения задания будут варьироваться в пределах: от 1 до 50, от 30 до 50, от 50 до 90. Всего будут сгенерированы данные для 1000 тестов. В Таблице 3 представлено сравнение периодов обработки Greedy-Balance и Sorted-Balance алгоритмов.
В первом столбце указано количество задач, участвующий в распределении. Во втором столбце указано минимальное время выполнения одного задания. В третьем столбце указано максимальное время выполнения одного задания. В последующих столбцах указано максимальное, минимальное и среднее значение отношения периода обработки Greedy-Balance и периода обработки Sorted-Balance. Процент вычисляется как: По результатам тестирований, с увеличением количества задач, которых необходимо распределить между машинами, разрыв периодов обработки алгоритмов сокращается. Также на сокращение разрыва влияет промежуток между минимальным и максимальным временем выполнения. Чем меньше промежуток, тем меньше разница между Greedy-Balance и Sorted-Balance алгоритмами. Таким образом, используя Greedy-Balance в системе с большим количество задач и малым промежутком между временем выполнения задач, можно добиться получения очень близкого к Sorted-Balance результата. Выводы по главе Жадные алгоритмы балансировки несложные в реализации. В них используются простые структуры данных, которые можно реализовать на большинстве языков программирования. В то же время, данные алгоритмы нужно использовать в зависимости от количества машин и входящих задач. При небольшом количестве машин применение обычного перебора для поиска машины с минимальной нагрузкой будет оптимальным вариантов, иначе лучше использовать модификации жадных алгоритмов с очередью с приоритетом. При использовании жадных алгоритмов с применением сортировки необходимо учитывать временную сложность её выполнения. С возрастанием количества задач время выполнения такой балансировки начинает увеличиваться. Когда количество задач в несколько раз больше, чем количество машин, и задачи имеют близкое друг к другу время выполнения, использование Greedy-Balance выдаст приближённый к Sorted-Balance результат.
Заключение На сегодняшний день существует большое количество методов балансировки нагрузки. К таким методам также относится применение жадных алгоритмов. Данные алгоритмы на каждом шаге работы выбирают наилучший вариант, чтобы получить в итоге оптимальный результат. Greedy-Balance алгоритм строит решение с периодом обработки
Библиографический список 1. Arregoces M., Portolani M. Data Center Fundamentals. – Cisco Press, 2004. – p. 676 –681. 2. KEMP Technologies: Load Balancing Techniques and Algorithms. [Электронный ресурс] – Режим доступа: https://kemptechnologies.com/load-balancer/load-balancing-algorithms-techniques/. 3. Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. Классика Computers Science. – СПб.: Питер, 2016. – с. 600–605. 4. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: Построение и анализ. – М.: И. Д. Вильямс, 2013. – с. 448. 5. Куроуз Д., Росс К. Компьютерные сети: Нисходящий подход. – М.: Издательство «Э», 2016. – с. 555.
Приложения Приложение 1 AlgorithmTester.cpp: #include "stdafx.h" #include "Balancer.h" #include <fstream> #include <string> #include <ctime>
using namespace std;
void startTesting(string & testName); // функция тестирования алгоритмов
int main() // главная функция { system("chcp 1251"); // установка в консоли русского языка std::ios::sync_with_stdio(false); // отключение синхронизации с stdio для более быстрого чтения из файла string testName; // название файла для чтения cout << "Введите название теста, который будет выполняться" << endl; // вывод текста в консоль cin >> testName; // чтение из консоли названия файла startTesting(testName); // вызов функции тестирования алгоритмов cin.ignore(); // ожидание нажатий клавиш пользователем после выполнения тестов cin.get(); return 0; }
void startTesting(string & testName) { int numberOfMachines, numberOfTasks, numberOfTests; // numberOfMachines - число машин, numberOfTasks - число задач, numberOfTests - число тестов ifstream input("../Tests/" + testName + ".txt"); // открываем файл для чтения из него тестов и заданий clock_t operatingTime[4] = { 0 }; // объявляем массив с временем выполнения всех тестов для каждого алгоритма if (!input.is_open()) // если не получается открыть файл, выходим из функции { cout << "Невозможно открыть файлы тестирования" << endl; input.close(); // закрытие файла return; // выход из функции } input >> numberOfTests >> numberOfMachines >> numberOfTasks; // считываем из файла информацию cout << "Начато тестирование: " << testName << endl; cout << "Число машин: " << numberOfMachines << endl; cout << "Число задач в 1 тесте: " << numberOfTasks << endl; cout << "Общее число тестов: " << numberOfTests << endl; ofstream result("../Tests/result_" + testName + ".txt"); // создаем файл result.txt для вывода информации for (int i = 1; i <= numberOfTests; i++) // в цикле от 1 до числа тестов выполняем тестирование алгоритмов { int taskTime, workTime; // taskTime - время выполнения задания, workTime - время выполнения балансировки Balancer greedyTests[4]; // создаём объекты класса clock_t startTime, finishTime; // startTime - время начала выполнения балансировки for (int task = 0; task < numberOfTasks; task++) // считываем numberOfTasks чисел из файла и добавляем их в балансировщики { input >> taskTime; // считываем из текстового файла время выполнения задания for (int j = 0; j < 4; j++) greedyTests[j].addTask(taskTime); // добавляем в каждый балансировщик данное задание } for (int j = 0; j < 4; j++) // выполнение тестирования { greedyTests[j].setNumberOfMachines(numberOfMachines); // устанавливаем количество машин в балансировщике startTime = clock(); // получаем время начала работы алгоритма greedyTests[j].startBalancing(j); // запускаем балансировку с необходимым алгоритмом finishTime = clock(); // получаем время после работы алгоритма workTime = (finishTime - startTime); // вычисляем время выполнения operatingTime[j] += workTime; // прибавляем время к общему времени result << greedyTests[j].getProcessingPeriod() << "\t" << (double)workTime /1000.0 << "\t"; // вывод в файл периода обработки } result << endl; // переход в файле на следующую строку } for (int j = 0; j < 4; j++) result << "\t" << (double)operatingTime[j] / 1000.0 << "\t"; // вывод в файл времени выполнения всех тестов cout << "Тестирование завершено" << endl; result.close(); // закрытие файлов input.close(); } Balancer.h: #pragma once class Balancer { private: struct Task { int id = 0, processingTime = 0; }; // структура, содержащая информацию о задаче. id - номер задачи, processingTime - время выполнения
struct Machine { int totalTime = 0, id = 0; std::vector<Task> assignedTasks; }; // структура, содержащая информацию о машине. totalTime - сумма времени выполнения всех задач, id - номер машины // assignedTasks - множество поставленных задач
std::vector<Task> sortedTasks; // множество задач для алгоритмов с сортировкой std::queue<Task> tasks; // множество задач для алгоритмов без сортировки std::vector<Machine> machines; // множество машин std::vector<int> priorityList; // список для очереди с приоритетом int numberOfTasks, numberOfMachines; // numberOfTasks - число задач, numberOfMachines - число машин
static bool compareMachines(const Machine &a, const Machine &b); // функция сравнения двух машин static bool compareTasks(const Task &a, const Task &b); // функция сравнения двух задач void updateQueue(); // функция обновления очереди с приоритетом public: Balancer(); // конструктор класса ~Balancer(); // деконструктор класса
void addTask(int _processingTime); // функция добавления задачи void setNumberOfMachines(int numberOfMachines_); // функция установки балансировщику числа машин void greedyBalance(); // функция Greedy Balance алгоритма void sortedBalance(); // функция Sorted Balance алгоритма void greedyBalanceModified(); // функция Greedy Balance алгоритма с очередью с приоритетом void sortedBalanceModified(); // функция Sorted Balance алгоритма с использованием очереди с приоритетом int getProcessingPeriod(); // функция получения периода обработки void startBalancing(int type = 0); // функция запуска балансировки с указанным алгоритмом };
Balancer.cpp: #include "stdafx.h" #include "Balancer.h"
bool Balancer::compareMachines(const Machine & a, const Machine & b) { return a.totalTime < b.totalTime; // если время работы машины 'a' меньше времени работы машины 'b', то возвращается истина, иначе возвращается ложь }
bool Balancer::compareTasks(const Task & a, const Task & b) { return a.processingTime < b.processingTime; // если время выполнения задачи 'a' меньше времени выполнения задачи 'b', то возвращается истина, иначе возвращается ложь }
void Balancer::updateQueue() { int index = 0, left, right, min; // index - текущая вершина, left - левый потомок вершины, right - правый потомок вершины, min - индекс машины с минимальной нагрузкой while (true) { left = 2 * index + 1; // вычисляем левого потомка right = 2 * index + 2; // вычисляем правого потомка min = index; // присваиваем минимальному индексу текущий индекс if (left < numberOfMachines && machines[priorityList[left]].totalTime < machines[priorityList[min]].totalTime) min = left; // если левый потомок имеет меньшую нагрузку, то он становится минимальным if (right < numberOfMachines && machines[priorityList[right]].totalTime < machines[priorityList[min]].totalTime) min = right; // если правый потомок имеет меньшую нагрузку, то он становится минимальным if (index == min) return; // если минимальный индекс не изменился, то выходим из функции std::swap(priorityList[min], priorityList[index]); // поднимаем на вершину минимальным элемент index = min; // текущий индекс становится равен минимальному } }
Balancer::Balancer() { numberOfTasks = 0; // количество задач равно 0 numberOfMachines = 0; // количество машин равно 0 }
Balancer::~Balancer() { }
void Balancer::addTask(int _processingTime) { Task task; // создаём задание task.id = ++numberOfTasks; // устанавливаем заданию номер task.processingTime = _processingTime; // устанавливаем заданию время выполнения tasks.push(task); // добавляем задание в конец множества задач sortedTasks.push_back(task); // добавляем задание в конец множества задач для алгоритмов с сортировкой }
void Balancer::setNumberOfMachines(int numberOfMachines_) { numberOfMachines = 0; // обнуление количества машин machines.resize(numberOfMachines_); // изменяем размер множества машин priorityList.resize(numberOfMachines_); // изменяем размер очереди с приоритетом for (std::vector<Machine>::iterator i = machines.begin(); i!= machines.end(); i++) // перебираем все машины { priorityList[numberOfMachines] = numberOfMachines; // добавляем машину в очередь с приоритетом (*i).id = ++numberOfMachines; // обновляем номер машины } }
void Balancer::greedyBalance() { while (!tasks.empty()) // пока множество задач не пустое { std::vector<Machine>::iterator min = std::min_element(machines.begin(), machines.end(), compareMachines); // находим машину с минимальной нагрузкой Task temp = tasks.front(); // получаем задание из множества задач (*min).assignedTasks.push_back(temp); // присваиваем задание машине (*min).totalTime += temp.processingTime; // прибавляем время выполнения задания к времени работы машины tasks.pop(); // удаляем задание из множества задач } }
void Balancer::sortedBalance() { std::sort(sortedTasks.begin(), sortedTasks.end(), compareTasks); // сортируем множество задач в порядке возрастания времени выполнения while (!sortedTasks.empty()) // пока множество задач не пустое { std::vector<Machine>::iterator min = std::min_element(machines.begin(), machines.end(), compareMachines); // находим машину с минимальной нагрузкой Task temp = sortedTasks.back(); // получаем с конца задание из множества задач (*min).assignedTasks.push_back(temp); // присваиваем задание машине (*min).totalTime += temp.processingTime; // прибавляем время выполнения задания к времени работы машины sortedTasks.pop_back(); // удаляем задание из множества задач } }
void Balancer::greedyBalanceModified() { while (!tasks.empty()) // пока множество задач не пустое { int min = priorityList[0]; // берём индекс машины с минимальной нагрузкой из очереди с приоритетом Task temp = tasks.front(); // берём задание из множества machines[min].assignedTasks.push_back(temp); // добавляем задание в множество задач машины machines[min].totalTime += temp.processingTime; // прибавляем время выполнения задания tasks.pop(); // убираем задание из множества updateQueue(); // обновляем очередь с приоритетом } }
void Balancer::sortedBalanceModified() { std::sort(sortedTasks.begin(), sortedTasks.end(), compareTasks); // сортируем множество задач в порядке возрастания времени выполнения while (!sortedTasks.empty()) // пока множество задач не пустое { int min = priorityList[0]; // берём индекс машины с минимальной нагрузкой из очереди с приоритетом Task temp = sortedTasks.back(); // берём задание из множества machines[min].assignedTasks.push_back(temp); // добавляем задание в множество задач машины machines[min].totalTime += temp.processingTime; // прибавляем время выполнения задания sortedTasks.pop_back(); // убираем задание из множества updateQueue(); // обновляем очередь с приоритетом } }
int Balancer::getProcessingPeriod() { int result = 0; // обнуляем результат for (std::vector<Machine>::iterator i = machines.begin(); i!= machines.end(); i++) // перебираем все машины if (i->totalTime > result) // если время работы машины больше, чем текущее значение, то обновляем текущее значение result = i->totalTime; return result; }
void Balancer::startBalancing(int type) { switch (type) { case 0: greedyBalance(); // если тип равен 0, то вызываем greedyBalance break; case 1: sortedBalance(); // если тип равен 1, то вызываем sortedBalance break; case 2: greedyBalanceModified(); // если тип равен 2, то вызываем greedyBalanceModified; break; case 3: sortedBalanceModified(); // если тип равен 3, то вызываем sortedBalanceModified break; } } Приложение 2
[1] Источник: http://www.internetworldstats.com/top20.htm [2] Информация указана на официальном сайте: https://vk.com/about [3] Источник: https://vk.com/dev/health
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Последнее изменение этой страницы: 2021-07-18; просмотров: 109; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 216.73.216.156 (0.008 с.) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
, где P – период обработки. Данный процент показывает, насколько период обработки Greedy-Balance больше периода обработки Sorted-Balance.
за O (Log(M) · N), в то время как Sorted-Balance строит решение с периодом обработки 
за O (
+ Log(M) · N). Эти алгоритмы имеют простую реализацию и могут быть разработаны на большом количестве языков программирования и использоваться в большинстве систем. В системах, в которых используется небольшое количество серверов, использование жадных алгоритмов без очереди с приоритетом будет оптимальным. Если же используется несколько сотен или тысяч серверов, то в жадных алгоритмах балансировки необходимо использовать очередь с приоритетом, так как это снизит время работы в несколько раз. Количество поступаемых задач влияет на результат балансировки алгоритмов. С возрастанием их количества разрыв в периоде обработки между Greedy-Balance и Sorted-Balance сокращается. Кроме того, если количество задач меньше количества машин, то периоды обработки алгоритмов будут одинаковые, но Sorted-Balance будет работать дольше из-за выполнения сортировки. Таким образом, применение в балансировке Greedy-Balance алгоритма будет эффективным при количестве задач меньше количества машин, либо количество задач в несколько раз больше количества машин. Вдобавок, этот алгоритм будет эффективен при условии, когда время выполнения задач близко друг к другу. В остальных случаях алгоритм Sorted-Balance выдаст лучший результат.
