Выпускная квалификационная работа бакалавра
Download 1.08 Mb.
|
ВКР.pdf (1)
Из таблицы видно, что для некоторых контейнеров имеются разные оценки сложности для одинаковых функций, в зависимости от положения элементов, с которыми происходит работа. Выбор какой-либо из этих функций может сильно влиять на работу алгоритмов для суперпозиции контейнеров в целом. Поэтому необходимо выбрать те, которые имеют минимальные временные затраты на выполнение. Проведём тестирование функций, в результате которого выявим самые быстрые из них. Будем варьировать количество элементов в контейнерах от 1000 до 100000. Возьмём шаг в 1000 элементов, и каждый раз будем производить 100 измерений в очередной точке. Будем запоминать минимальное, среднее и максимальное время работы функции в каждой точке. Далее по полученной выборке будем проводить интерполяцию, и сравнивать время выполнения двух тестируемых функций. Проведём тестирования для вектора. В общем случае вставка в вектор осуществляется функцией: iterator insert(const_iterator position, const T& x); Её сложность линейно зависит от количества перемещаемых элементов при вставке. Если нужно производить вставку элементов в конец вектора, то можно использовать функцию: void push_back(const T& x); Эта функция имеет амортизированную константную сложность. Сравним время вставки при помощи push_back(x) и insert(end, x). Рисунок 3 - Сравнение push_back(x) и insert(end, x) в среднем по времени. Рисунок 4 - Сравнение push_back(x) и insert(end, x) по максимальному времени. Из результатов измерений видно, что push_back(x) работает быстрее в среднем и максимальном времени. Поиск по значению в векторе осуществляется с помощью функции: template Inputiterator find(inputiterator first, Inputiterator last, const T& value); Данная функция имеет линейную сложность от количества перебираемых элементов. Удаление элементов из вектора в общем случае осуществляется с помощью функции: iterator erase(const_iterator position); Её сложность линейно зависит от количества перемещаемых элементов при удалении. Если нужно удалять элементы из конца вектора, то можно воспользоваться функцией: void pop_back(); Эта функция имеет амортизированную константную сложность. Сравним время удаления с помощью pop_back() и erase(end). Рисунок 5 - Сравнение pop_back() и erase(end) в среднем по времени. Рисунок 6 - Сравнение pop_back() и erase(end) по максимальному времени. Из результатов измерений видно, что pop_back() работает быстрее по максимальному времени и немного медленнее в среднем по времени. Доступ к элементам в векторе в общем случае осуществляется с помощью оператора: reference operator[](size_type n); Этот оператор имеет константную сложность. Если необходим доступ к первому элементу, то можно использовать функцию: reference front(); Эта функция имеет константную сложность. Сравним время доступа с помощью front() и operator[0]. Рисунок 7 - Сравнение front() и operator[0] в среднем по времени. Max time 0.05 0.045 0.04 0.035 0.03 0.025 0.02 0.015 0.01 0.005 0 0123456789 10 x104 Рисунок 8 - Сравнение front() и operator[0] по максимальному времени. Из результатов измерений видно, что front() работает быстрее в среднем по времени и немного медленнее по максимальному времени. Если необходим доступ к последнему элементу, то можно использовать функцию: reference back(); Эта функция имеет константную сложность. Сравним время доступа с помощью back() и operator[size - 1]. Рисунок 9 - Сравнение back() и operator[size - 1] в среднем по времени. Рисунок 10 - Сравнение back() и operator[size - 1] по максимальному времени. Из результатов измерений видно, что back() работает быстрее в среднем по времени и немного медленнее по максимальному времени. Проведём тестирования для двусторонней очереди. В общем случае вставка в двустороннюю очередь осуществляется функцией: iterator insert(const_iterator position, const T& x); Её сложность линейно зависит от количества перемещаемых элементов при вставке. Если производить вставку элементов в начало очереди, то можно использовать функцию: void push_front(const T& x); Эта функция имеет амортизированную константную сложность. Сравним время вставки при помощи push_front(x) и insert(begin, x). Рисунок 11 - Сравнение push_front(x) и insert(begin, x) в среднем по времени. Рисунок 12 - Сравнение push_front(x) и insert(begin, x) по максимальному времени. Из результатов измерений видно, что push_front() работает быстрее в среднем и по максимальному времени. Если нужно производить вставку элементов в конец очереди, то можно использовать функцию: void push_back(const T& x); Эта функция имеет амортизированную константную сложность. Сравним время вставки при помощи push_back(x) и insert(end, x). Рисунок 13 - Сравнение push_back(x) и insert(end, x) в среднем по времени. Рисунок 14 - Сравнение push_back(x) и insert(end, x) по максимальному времени. Из результатов измерений видно, что push_back() работает быстрее в среднем и по максимальному времени. Поиск по значению в очереди осуществляется с помощью функции: template Inputiterator find(InputIterator first, Inputiterator last, const T& value); Данная функция имеет линейную сложность от количества перебираемых элементов. В общем случае удаление элементов из очереди осуществляется с помощью функции: iterator erase(const_iterator position); Её сложность линейно зависит от количества перемещаемых элементов при удалении. Если нужно удалять элементы из начала очереди, то можно воспользоваться функцией: void pop_front(); Эта функция имеет амортизированную константную сложность. Сравним время удаления с помощью pop_front() и erase(begin). Рисунок 15 - Сравнение pop_front() и erase(begin) в среднем по времени. Рисунок 16 - Сравнение pop_front() и erase(begin) по максимальному времени. Из результатов измерений видно, что pop_front() работает быстрее в среднем и по максимальному времени. Если нужно удалять элементы из конца очереди, то можно воспользоваться функцией: void pop_back(); Эта функция имеет амортизированную константную сложность. Сравним время удаления с помощью pop_back() и erase(end). Рисунок 17 - Сравнение pop_back() и erase(end) в среднем по времени. Рисунок 18 - Сравнение pop_back() и erase(end) по максимальному времени. Из результатов измерений видно, что pop_back() работает быстрее в среднем и по максимальному времени. Доступ к элементам в очереди в общем случае осуществляется с помощью оператора: reference operator[](size_type n); Этот оператор имеет константную сложность. Если необходим доступ к первому элементу, то можно использовать функцию: reference front(); Эта функция имеет константную сложность. Сравним время доступа с помощью front() и operator[0]. Рисунок 19 - Сравнение front() и operator[0] в среднем по времени. Рисунок 20 - Сравнение front() и operator[0] по максимальному времени. Из результатов измерений видно, что front() работает быстрее в среднем и по максимальному времени. Если необходим доступ к последнему элементу, то необходимо использовать функцию: reference back(); Эта функция имеет константную сложность. Сравним время доступа с помощью back() и operator[size - 1]. Рисунок 21 - Сравнение back() и operator[size - 1] в среднем по времени. Рисунок 22 - Сравнение back() и operator[size - 1] по максимальному времени. Из результатов измерений видно, что back() работает медленнее в среднем и по максимальному времени. Проведём тестирования для списка. В общем случае вставка в список осуществляется функцией: iterator insert(const_iterator position, const T& x); Для списка сложность этой функции константная. Если производить ставку элементов в начало списка, то можно использовать функцию: void push_front(const T& x); Эта функция имеет амортизированную константную сложность. Сравним время вставки при помощи push_front(x) и insert(begin, x). Рисунок 23 - Сравнение push_front(x) и insert(begin, x) в среднем по времени. Рисунок 24 - Сравнение push_front(x) и insert(begin, x) по максимальному времени. Из результатов измерений видно, что push_front(x) работает быстрее в среднем и по максимальному времени. Если производить вставку элементов в конец списка, то можно использовать функцию: void push_back(const T& x); Эта функция имеет амортизированную константную сложность. Сравним время вставки при помощи push_back(x) и insert(end, x). Рисунок 25 - Сравнение push_back(x) и insert(end, x) в среднем по времени. Рисунок 26 - Сравнение push_back(x) и insert(end, x) по максимальному времени. Из результатов измерений видно, что push_back(x) работает быстрее по максимальному времени и медленнее в среднем времени. Поиск по значению в списке осуществляется с помощью функции: template Inputiterator find(InputIterator first, Inputiterator last, const T& value); Данная функция имеет линейную сложность от количества перебираемых элементов. В общем случае удаление элементов из списка осуществляется с помощью функции: iterator erase(const_iterator position); Для списка сложность этой функции константная. Если нужно удалять элементы из начала списка, то можно воспользоваться функцией: void pop_front(); Эта функция имеет амортизированную константную сложность. Сравним время удаления с помощью pop_front() и erase(begin). Рисунок 27 - Сравнение pop_front() и erase(begin) в среднем по времени. Рисунок 28 - Сравнение pop_front() и erase(begin) по максимальному времени. Из результатов измерений видно, что pop_front(x) работает быстрее по максимальному времени и немного медленнее в среднем времени. Если нужно удалять элементы из конца списка, то можно воспользоваться функцией: void pop_back(); Эта функция имеет амортизированную константную сложность. Сравним время удаления с помощью pop_back() и erase(end). Рисунок 29 - Сравнение pop_back() и erase(end) в среднем по времени. Рисунок 30 - Сравнение pop_back() и erase(end) по максимальному времени. Из результатов измерений видно, что pop_back(x) работает медленнее в среднем и по максимальному времени. Для доступа к элементам списка в общем случае необходимо использовать перебор итератора на п позиций (индекс проверяется заранее): for (iterator it = list.begin(); it != list.end() && n > 0; ++it, --n); Данный подход имеет линейную сложность от количества перебираемых элементов. Если необходим доступ к первому элементу, то можно использовать функцию: reference front(); Эта функция имеет константную сложность. Если необходим доступ к последнему элементу, то можно использовать функцию: reference back(); Эта функция имеет константную сложность. Проведём тестирования для ассоциативных контейнеров. Вставка в ассоциативные контейнеры в общем случае осуществляется с помощью функции: pair Эта функция имеет логарифмическую сложность от количества элементов в контейнере. Также есть следующая функция вставки: iterator insert(const_iterator position, const val- ue_type& x); В общем случае эта функция имеет логарифмическую сложность от количества элементов в контейнере. При каждой вставке будем запоминать, на какую позицию она производилась. И если следующая вставка будет после этого элемента, то данная функция будет иметь амортизированную константную сложность. Сравним время работы этих функций для всех рассматриваемых ассоциативных контейнеров. Для множества: Рисунок 31 - Сравнение insert(x) и insert(iterator, x) в среднем по времени. Рисунок 32 - Сравнение insert(x) и insert(iterator, x) по максимальному времени. Для множества с дубликатами: Рисунок 33 - Сравнение insert(x) и insert(iterator, x) в среднем по времени. Рисунок 34 - Сравнение insert(x) и insert(iterator, x) по максимальному времени. Для словаря: Рисунок 35 - Сравнение insert(x) и insert(iterator, x) в среднем по времени. Рисунок 36 - Сравнение insert(x) и insert(iterator, x) по максимальному времени. Для словаря с дубликатами: Рисунок 37 - Сравнение insert(x) и insert(iterator, x) в среднем по времени. Рисунок 38 - Сравнение insert(x) и insert(iterator, x) по максимальному времени. Из результатов измерений видно, что эти функции в общем случае имеют одинаковые показатели по времени. Теперь будем добавлять элементы последовательностями. Это существенно повлияет на работу контейнеров с дубликатами. Для множества с дубликатами: Рисунок 39 - Сравнение insert(x) и insert(iterator, x) в среднем по времени. Рисунок 40 - Сравнение insert(x) и insert(iterator, x) по максимальному времени. Для словаря с дубликатами: Рисунок 41- Сравнение insert(x) и insert(iterator, x) в среднем по времени. Рисунок 42 - Сравнение insert(x) и insert(iterator, x) по максимальному времени. Из результатов измерений видно, что insert(iterator, x) работает быстрее в среднем и максимальном времени. Поиск по значению для всех контейнеров проводится с помощью функции: template Inputiterator find(inputiterator first, Inputiterator last, const T& value); Данная функция имеет линейную сложность от количества перебираемых элементов. Удаление из ассоциативных контейнеров осуществляется с помощью функции: size_type erase(const key_type& x); Эта функция имеет логарифмическую сложность от количества элементов в контейнере. Для контейнеров с дубликатами к этой сложности добавляется количество элементов с таким ключом. Если необходим доступ к элементу ассоциативного контейнера, то необходимо использовать функцию: iterator find(const key_type& x); Эта функция определена для каждого контейнера и имеют логарифмическую сложность от количества элементов в контейнере. Для словаря также определён оператор: T& operator[](const Key& x); С помощью которого можно изменять и добавлять элементы. Обобщенные алгоритмы для работы с суперпозицией контейнеров Для работы с суперпозицией контейнеров необходимо реализовать набор базовых функций. К этому набору относятся такие функции как доступ к элементам, добавление новых элементов, поиск и удаление уже имеющихся элементов. Все контейнеры в отдельности поддерживают эти функции, поэтому их можно реализовать и для суперпозиции. Но при этом необходимо учитывать выше полученные результаты по работе различных функций. Если на каком-то уровне структуры требуется получить доступ к его элементу, то это нужно реализовать следующим образом: сначала проанализировать, какой элемент нужен, а после использовать подходящую функцию. Если на уровне последовательный контейнер, то могут быть следующие варианты: индекс первого элемента, индекс последнего элемента и индекс средних элементов. Сначала обрабатывается общий случай - индекс средних элементов, а после частные - индекс первого элемента и индекс последнего элемента. Если нужно получить доступ, то для вектора и очереди нужно использовать operator[], а для списка перебор итераторов с того конца, к которому ближе нужный элемент. В частных случаях нужно использовать front() и back(), но для очереди - operator[end] для доступа к последнему элементу. Если нужно вставить элемент, то в общем случае нужно пользоваться функцией insert(iterator, x), а в частных push_back(x) и push_front(x). Если нужно удалить элемент, то в общем случае нужно пользоваться функцией erase(iterator), а в частных pop_front() и pop_back(). Но для списка нужно использовать erase(end) для удаления последнего элемента. Также не стоит забывать, что для вектора и очереди есть функция shrink_to_fit(), которая освобождает неиспользуемую память у контейнера. Если на уровне ассоциативный контейнер, то нужно использовать следующие функции: для вставки: insert(iterator, x) и сохранять итератор, который возвращает эта функция. Это позволит ускорить её работу в тех случаях, когда будут вставляться несколько элементов последовательно; для удаления элементов: erase(x); для получения доступа: T::find(x), где T - это тип используемого контейнера. Поиск во всех контейнерах осуществляется полным перебором с применением функции std::find(first, last, value). Тестирование структуры Целью тестирования структуры является сравнение скорости выполнения обобщенных алгоритмов с алгоритмами контейнеров из STL на стандартных типах данных. При этом количество элементов в структурах будет варьироваться в диапазоне от 1000 до 100000. Рассмотрим на примере работу обобщенных алгоритмов в спроектированной структуре. Учитывая выше полученные особенности контейнеров, измерим их время работы на разном количестве элементов. Сгенерируем структуру следующего вида: vector Рассмотрим функцию вставки void Insert(int, int, int). Рисунок 43 - Оценка функции вставки по максимальному времени. Рисунок 44 - Оценка работы функции вставки в среднем по времени. Рассмотрим функцию удаления элементов void Erase(int, int, int). Рисунок 45 - Оценка работы функции удаления по максимальному времени Рисунок 46 - Оценка работы функции удаления в среднем по времени. Рассмотри функцию поиска элементов bool Find(int). Рисунок 47 - Оценка работы функции поиска по максимальному времени. Рисунок 48 - Оценка работы функции поиска в среднем по времени. Рассмотрим функцию доступа к элементам int operator()(int, int, int). Рисунок 49 - Оценка работы функции доступа к элементам по максимальному времени. Рисунок 50 - Оценка работы функции доступа к элементам в среднем по времени. По результатам тестирования и оценки базовых функций для составной структуры видно, что эти функции в среднем работают так же, как и стандартные аналогичные функции у каждого контейнера в отдельности. Таким образом, использование полученных алгоритмов почти не отличается от стандартных методов работы с контейнерами из STL. Предложенные решения подходят для адекватной работы с проектируемой структурой в плане скорости выполнения. Структура программы Визуально узел представляет собой пользовательский элемент управления. Рисунок 51 - Пользовательский элемент управления. Он состоит из элементов ComboBox и TextBox. ComboBox предоставляет выбор типа для текущего узла: вектор, список, дэк или конечный тип. TextBox содержит информацию о количестве потомков, если типом узла является контейнер. Если типом узла является конечный тип, то в этом поле содержится значение для инициализации. В программе узел представляется с помощью класса Node. Node -node: MyControl -link: Line -next: List -prev: int -level: int +Node() +Node(newNode: MyCon trol) +Next: int {set} +NextSize: int {get} +GetNext(index: int): int +Prev: int{get, set} +Level: int {get, set} +IsChild: bool {get} +IsParent: bool {get} +X: double {get} +Y: double {get} +Width: double {get} +Height: double {get} +CentreX: double {get} +CentreY: double {get} +isFreeNode: bool {get} +isInGraph: bool {get} +SetColor(): void Среди полей класса имеется визуальный элемент, который соответствует данному узлу, линия для отображения связи от узла, список индексов потомков, индекс родительского элемента и уровень узла. Метод Next добавляет индекс потомка в список для данного узла, а метод GetNext возвращает номер потомка, который содержится в списке под номером index. Все созданные узлы добавляются в список узлов Nodes. После загрузки окна программы, в этот список автоматически добавляется узел, который соответствует корню проектируемой структуры. Создание узлов производится функцией CreateNode(), которая сразу же помещает узлы в список. Для создания узла необходимо нажать на кнопку AddNode или выбрать соответствующий пункт в контекстном меню. Пример нескольких созданных узлов: Рисунок 52 - Пример нескольких созданных узлов. Для создания связи между узлами необходимо нажать на кнопку AddLink или выбрать соответствующий пункт в контекстном меню. После нажатия на кнопку нужно указать два узла, между которыми будет устанавливаться связь. После вызывается функция CreateLink(), которая проверяет ограничения для установления связи, которые были рассмотрены ранее, используя методы isInGraph и isFreeNode. Если узлы удовлетворяют всем условиям, то у родительского узла добавляется в список потомков индекс дочернего узла, а у дочернего узла изменяется уровень, появляется родительский элемент и изменяется цвет на тот, который соответствует его уровню. Пример нескольких соединённых узлов: Рисунок 53 - Пример нескольких соединённых узлов. Перед созданием библиотеки необходимо заполнить все поля в проектируемой структуре. У каждого узла должен быть выбран его тип. У терминальных узлов последнего уровня с конечным типом должны быть записаны значения. Также должны быть заполнены имя структуры и конечный тип, который будет в ней использоваться. Пример заполненной структуры: Рисунок 54 - Пример заполненной структуры. Для создания библиотеки необходимо нажать на кнопку Create library. Сначала будет произведена проверка корректности заполнения всех полей в структуре при помощи функции CheckInputData(). В ней будет произведена проверка введённого названия структуры и конечного типа. Проверится, что каждый узел имеет какой-либо тип и имеет вписанное значение, если оно нужно, а также что нет свободных узлов и все они соединены в граф. Следующим шагом будет заполнение шаблона необходимой информацией о структуре. Пустой шаблон выглядит следующим образом: versiоп="1.0" encoding="utf-8"?> «struct» «include text="Winclude " start="<" end=">"» include» «using text="using " end=";"> «/using» «class text="class " start="{" end="};"» «private text="private:"» «name text=" " start="<" middle=">" end="_;"> «public text="public:"> «constructor text=" " start="(" end=");" /> «operator text=" " return="&" start="operator()(" middle="int" end=");" «insert text=" " return="void " start="Insert(" middle="int" end=");" /> «find text=" " return="bool " start="Find(" end=");" /> «erase text=" " return="void " start="Erase(" middle="int" end=");" /> «/publio lass» Рисунок 55 - Пустой шаблон. Совершаем обход дерева в ширину при помощи очереди. Для посещения узлов воспользуемся следующей функцией: Download 1.08 Mb. Do'stlaringiz bilan baham: 
|