Разработка структур данных и алгоритмов

На этапе разработки для коллекции выбираются программная структура хранения данных и алгоритмы её операций. Но в рамках лабораторных работ программная структура данных для хранения коллекции и набор основных операций задаётся вариантом задания. Необходимо спроектировать программный объект коллекции, реализующий заданный вариант.

Для реализации коллекции используется объектно-ориентированный подход к проектированию. Коллекция представляется в виде объекта, объединяющего в единое целое данные и операции. Основой для проектирования структуры коллекции служит формат АТД, составленный на этапе постановки задачи. Раздел данных АТД определяет набор полей объекта коллекции, а раздел операций – набор методов.

В раздел данных коллекции вводятся именованные поля для общих параметров коллекции, определенных в АТД (предельный размер коллекции, текущий размер коллекции и т.п.) и структура данных, хранящая данные, включаемые в коллекцию. Впоследствии, по мере разработки методов объекта, для них в раздел данных вводятся вспомогательные поля и структуры данных (адрес массива или адрес первого элемента связной структуры, индекс или адрес последнего элемента, адрес текущего элемента, структура для вспомогательной очереди или стека и т.п.).

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

Для представления структуры, хранящей множество данных, применяются две альтернативные формы – массив или связная структура на основе указателей. Учитывая произвольное количество данных, включаемых в коллекцию, как правило, массив или связная структура размещаются в динамической памяти.

В случае использования связной структуры возникает необходимость в представлении отдельного элемента структуры, хранящего не только значение объекта, но и указатели на соседние элементы структуры. Поэтому в коллекцию вводится вспомогательный объект для отдельных элементов структуры (элемент списка, узел дерева, вершина графа и т.п.). По мере пополнения коллекции новыми данными создаются вспомогательные объекты – элементы структуры и включаются в связную структуру. Эти элементы, как и сама структура, являются внутренними для коллекции и скрыты от клиентской программы.

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

Как и любой объект, итератор имеет данные – ссылку на объект коллекции, к которому он привязан, ссылку на текущий элемент скрытой структуры коллекции, хранящий отдельное данное, методы установки итератора на первый или последний элементы коллекции, перемещения по элементам, обнаружения конца просмотра.

Таким образом, в среде клиентской программы структуру отдельного объекта – коллекции можно изобразить с помощью типовой схемы, приведенной на рисунке 1.

Рис. 1. Структура объекта коллекции.

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

Если при разработке методов, оговоренных в АТД, возникает необходимость в дополнительных методах, необходимых для управления коллекцией, то они вводятся в интерфейс коллекции и, соответственно, в формат АТД.

Все интерфейсные методы помещаются в секцию объекта коллекции, открытую для клиентских программ.

Алгоритмы методов реализуют операции, указанные в АТД, с учётом выбранной структуры данных для коллекции. При выборе и разработке алгоритмов методов помимо назначения операций должна учитываться и эффективность алгоритма. Любая задача может быть решена несколькими методами, алгоритмы которых могут отличаться. При выборе алгоритма метода наиболее предпочтительным является алгоритм, который выполняет минимально возможное число действий, т.е. имеет минимальную трудоёмкость.

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

Для предварительной оценки трудоёмкости алгоритмов используется нотация «большое О» (Big-O) [3, 6, 8, 9]. Основная идея применения нотации Big-O заключается в том, что необходимо определить, как будет вести себя алгоритм при росте размера коллекции n. Нотация Big-O даёт аппроксимированную верхнюю границу трудоёмкости алгоритма при неограниченном росте n.

Технику получения аналитической оценки Big-O можно продемонстрировать на примере алгоритма сортировки массива методом выбора, содержащего n значений (Таблица 1).

Таблица 1

Selection_Sort (A, n)	Стоимость	Число повторений
1. A - массив
2. n- число значений в массиве
3. for i 1 to n	C1	n
4. do imin i	C2	n-1
5. for j i+1 to n	C3
6. do if A[j]<A[imin] then imin j	C4
7. temp A[imin]	C5	n-1
8. A[imin] A[i]	C6	n-1
9. A[i] temp	C7	n-1

Сложив вклады всех строк, получим:

С1 n + С2 (n– 1 ) + C3 + C4 + С5 (n– 1 ) + С6 (n– 1 ) + С7 (n– 1 ) =

= С1 n + (С2+С5+С6+С7) (n– 1 ) + (C3+C4) =

= С1 n + (С2+С5+С6+С7) (n– 1 ) + (C3+C4)/ 2 (n- 1 ) (n-2) =

= С1 n + (С2+С5+С6+С7) (n– 1 ) + (C3+C4) /2 n² - 3 (C3+C4)/ 2 n - (C3+C4) =

= (C3+C4)/ 2 n² + (С1+С2- 3/2 (C3+C4) +С5+С6+С7) n – (С2+C3+C4+С5+С6+С7)

То есть, можно утверждать, что время выполнения алгоритма прямо пропорционально функции f(n) = a₂ n ² + a₁ n + a₀, зависящей от размера задачи n.

Вообще, если f(n) есть полином вида

a_k n ^k + a_k-1 n ^k-1 + …+ a₁ n + a₀

то можно доказать, что f(n)< C n ^k при n ≥ n₀.

В частности полином a_k n ^k + a_k-1 n ^k-1 + …+ a₁ n + a₀ <C n ^k

при n₀ = 1и C = | a_k | + | a_{k- 1} | + …+ | a₁ | + | a₀ |.

Приведённая к старшей степени оценка трудоёмкости g (n)= C n ^k называется порядком роста трудоёмкости алгоритма и обозначается, как O(g (n)) или O(n^k).

Таким образом, для рассмотренного алгоритма сортировки оценка трудоёмкости имеет вид O(n²).

Анализ трудоёмкости вновь разрабатываемого алгоритма подчас становится сложной математической задачей. В результате теоретического анализа наиболее известных, фундаментальных алгоритмов получены оценки их трудоёмкости в виде нотации Big-O [3-9]. Если для реализации выбран один из известных алгоритмов, то можно воспользоваться этими оценками.

На практике можно воспользоваться более грубым приёмом для быстрого получения оценки Big-O. Если в алгоритме отсутствует зависимость между его действиями и объёмом обрабатываемых данных, то его трудоёмкость не зависит от n и имеет оценку O(1). Если в алгоритме встречается цикл, число повторений которого пропорционально n, то можно сказать, что его трудоёмкость имеет вид O(n). Если в алгоритме используются два цикла, число повторений которых пропорционально n, причем один цикл вложен в другой, то трудоёмкость алгоритма имеет вид O(n²). Тройная вложенность таких циклов свидетельствует о трудоёмкости O(n³) и так далее. Алгоритмы, выполняющие разбиение задачи на подзадачи и выбор для решения одной из подзадач (алгоритм двоичного поиска значения в упорядоченном массиве, алгоритмы операций для двоичного дерева поиска и т.п.) имеют оценку трудоёмкости O(log ₂ n). Алгоритмы, выполняющие разбиение задачи на подзадачи и комбинирующие решения подзадач в одно общее решение, имеют оценку O(n log ₂ n) (алгоритмы сортировки методом разделения, методом слияния). Алгоритмы, выполняющие разбиение задачи и перебор всех возможных комбинаций решений подзадач, имеют трудоёмкость O(2 ⁿ) и называются экспоненциальными. На практике такие алгоритмы очень редко используются.

Графики, приведенные на рисунке 2, наглядно иллюстрируют, насколько отличаются трудоёмкости алгоритмов с различным порядком роста.

Рис. 2. Сравнение различных порядков роста трудоёмкости алгоритмов.

Необходимо отметить, что трудоёмкость алгоритмов для коллекции в значительной мере определяется спецификой структуры данных, на которой базируется коллекция. Например, если в коллекции используется связный список элементов, то большинство алгоритмов будут иметь нотацию трудоёмкости O(n). Если основой коллекции является двоичное дерево поиска, то трудоёмкость алгоритмов оценивается нотацией O(log₂n). Эти оценки должны служить ориентиром при разработке алгоритмов для коллекции.

Для некоторых алгоритмов и структур данных при оценке трудоёмкости приходится рассматривать худший и средний варианты работы. Работа таких алгоритмов и структур зависит от перестановки элементов обрабатываемого множества данных. Например, алгоритмы сортировки методом вставки, обменной сортировки выполняют максимальное число сравнений и перестановок, если значения в сортируемом массиве имеют обратную упорядоченность. Двоичное дерево поиска вырождается в линейный список, если оно формируется последовательными вставками возрастающих по значению ключа данных. В таком случае проводится анализ трудоёмкости для худшего и среднего режимов работы алгоритмов. Оценка трудоёмкости для худшего случая определяет максимальное время выполнения алгоритма. Эта оценка важна, если реализованный алгоритм будет встроен в систему реального времени, для которой оговаривается допустимое время ответа на входящий запрос. Анализ трудоёмкости для среднего случая позволяет оценить среднюю производительность алгоритма. Как правило, анализ среднего варианта носит вероятностный характер и выполнить его намного сложнее, чем для худшего случая.

В рамках лабораторных работ предлагается следующая методика использования оценки трудоёмкости Big-O для алгоритмов операций. Для алгоритма или структуры даётся эталонная оценка трудоёмкости. Все решения при разработке алгоритмов операций должны быть направлены на то, чтобы трудоёмкость реализованного алгоритма соответствовала этой оценке. В дальнейшем на этапе тестирования проводится программное измерение трудоёмкости операций коллекции и сопоставление экспериментальных оценок с эталонной оценкой. Если для какого–либо метода оценки значительно отличаются, то необходимо обосновать алгоритм этой операцмм или внести в него изменения.

Кодирование

При выполнении лабораторных работ программная реализация коллекции выполняется на языке программирования С++. Для программирования намеченных объектов разрабатываются определения соответствующих классов. Классы, предназначенные для создания объекта коллекции, известны, как классы – контейнеры.

В основе контейнеров лежит понятие шаблонного класса, принятое в языке C++. Шаблон позволяет разрабатывать класс, не уточняя типы данных до момента создания объекта. При объявлении объекта-коллекции в клиентской программе указывается конкретный тип данных, хранящихся в коллекции.

Описание шаблонного класса и его реализацию (определение методов класса) следует хранить в одном заголовочном файле, в отличие от схемы для обычных классов, когда определение и реализация класса разнесены в заголовочный файл и файл реализации. Связано это с особенностями компиляции шаблонного класса. Большинство компиляторов должно знать, как клиентская программа использует шаблонный класс перед компиляцией файла, содержащего его реализацию. Фактический тип данных, заданный параметром шаблона T, должен быть известен компилятору заранее. Поэтому реализацию шаблонного класса не следует компилировать отдельно от программы, использующей класс. Определение класса и его реализация компилируются совместно с клиентской программой, в которой выбран конкретный тип T при объявлении объектов шаблонного класса.

Согласно структуре объекта коллекции, намеченной в формате АТД, определение класса включает скрытую секцию для данных и открытую секцию с интерфейсными методами. Если коллекция использует связную структуру данных, то в классе коллекции определен также внутренний класс для элемента структуры. Кроме того, в открытой секции класса определен внутренний класс для итератора коллекции. Общий вид заголовочного файла с определением и реализацией контейнерного класса для коллекции, основанной на связной структуре, задан следующий схемой:

//заголовочный файл “Collection.h”

//определение шаблонного класса для объекта коллекции

template <class T> class Collection

{// скрытая секция объекта

protected:

срытые поля и структуры Collection

…

объявление прототипов срытых методов Collection

…

//открытая секция объекта коллекции

public:

Collection (); // конструктор по умолчанию

Collection (…); //конструктор с параметрами

// конструктор копирования

Collection (const Collection<T> & anotherCollection);

~Collection (); //деструктор

объявление прототипов интерфейсных методов Collection

…

…

…

//класс для элемента коллекции

Class Node

{public:

T item; //значение объекта в элементе

Node *p1; //указатели на соседние элементы структуры

Node *p2

Node(Т item); // конструктор элемента

}; //конец класса Node

//класс итератора для объекта Collection

Дата добавления: 2015-11-04