Модели структур данных

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

Эта модель должна:

• отражать структурные особенности различных способов организации данных, существенные с точки зрения оценки вычисли-тельной сложности выполняемых операций, а также емкостной сложности структуры данных;

• позволять выполнять формальные преобразования, позволяющие получать новые структуры из имеющихся;

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

Векторная организация предполагает размещение однотипных элементов в последовательной непрерывной памяти.

Основными компонентами вектора данных, являются множество ад-ресов (базы и элементов) – A и множество значений элементов – V.

При этом из множества адресов выделяется подмножество AAB, состоя-щее из одного элемента – адрес базы. На остальных элементах это-го множества AAE = A \ AAB определено отношение порядка.

В структуре между этими компонентами существует множество отно-шений С, которое распадается на следующие подмножества:

• СA – отношения адресов A, показывающие, что из одного адреса в процессе работы получают другой, где

– СAE – несимметричные отношения адресов данных, отображающие, что адрес каждого элемента может быть получен из адреса любого другого;

– СAB – несимметричное отношение адреса базы и адресов элементов;

• CV – симметричные отношения взаимнооднозначного соответствия элементов данных V и адресов AAE, по которым они расположены.

Максимальное количество элементов данных, которые могут быть занесены в этот вектор, определяется количеством зарезервиро-ванных адресов ZAE плюс адрес базы. Поэтому элементам множества вершин ZA следует сопоставить значение lV – объем памяти (байт), необходимый для размещения одного элемента данных, т. е.

(" z Î ZA) l (z) = lV.

Объем памяти, необходимый для хранения вектора, таким образом, составит L в = lV ·| ZA | (байт).

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

lV = lz + lw 1+ lw 2+ …+ lwr, где w 1, w 2, … wr Î W – множество весов.

В полученной модели каждое ребро соответствует одной операции вычисления адреса, следовательно функциональная вычислительная сложность определения элемента по номеру Q = 1.

Поиск элемента по значению, а также поиск экстремальных значений и значений, следующих за ними, в среднем предполагает просмотр по-ловины элементов, а потому функциональная вычислительная слож-ность этих операций для вектора составляет Q = n/2, где n = | ZV | – ко-личество элементов данных, хранящихся в векторе.

Поскольку значения элементов данных в обычном векторе не упорядо-чены, добавление элементов данных в вектор выполняют, дописывая значения на свободные места в конец вектора. Откуда функциональ-ная вычислительная сложность добавления элемента к несортированной совокупности данных Q = 1.

Дуги EAB упорядочены, т. е. нераздельно связаны с вершинами адресов, к которым они подходят, следовательно, для удаления элемента с но-мером k требуется изменить соответствие следующих вершин ZV вер-шинам ZAE. Откуда функциональная вычислительная сложность этой операции в среднем Q = n/ 2.

При этом вычислительная сложность выполнения основных операций для множества элементов данных считается одинаковой, поэтому определенные выше значения вычислительной сложности могут быть сопоставлены каждому элементу данных " z Î ZV или его адресу " z Î ZAE.

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

Таким образом, ZAE ® Qo, где Qo = { Qo i, i = 1,| Op | }, а Qo i – вычислительная сложность выполнения i -ой операции op i Î Op для элемента z Î ZAE.

Моделями вектора данных и вектора адресов будут соответственно графы:

G Д({<{ ZAB, ZAE }, lV,QО>;, ZV }, { { EAB, EAE }, EV }) и

G А({<{ ZAB, ZAE }, lA, QО>;, ZAV }, {{ EAB, EAE }, EAV }).

В отличие от векторной структуры компоненты списка расположены в произвольных местах памяти. Эти компоненты для линейного односвязного списка связаны между собой отношением «следующий» за счет хранения в компоненте адреса следующего компонента. Адрес списка хранится в начальном компоненте. Элементы данных связаны с адресами их хранения. При переходе от объекта к модели:

• A «ZA, V«ZV, ZA È ZV=Z, ZA Ç ZV= Æ;

• C AB «EAB = { e 0}, где e 0 – дуга;

• C AE «EAE – множество дуг;

• C V «EV – множество звеньев, соединяющих вершины ZAE и ZV.

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

Каждому элементу множества ZA сопоставим значение lA – объем памяти,необходимый для хранения адреса, а каждому элементу множества ZV – значение lV _ объем памяти, необходимый для элемента данных, т. е.

(" z Î ZA) l (z) = lA & (" z Î ZV) l (z) = lV.

При этом объем памяти, необходимый для реализации линейного односвязного списка, определяется формулой:

LS 1 = lA * | ZA | + lV * | ZV |.

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

С этой точки зрения необходимо различать стековую и последователь-ную (очередь) дисциплины добавления/обработки. Для стека характерно, что элементы добавляются перед первым – в начало списка, следовательно, первым будет обрабатываться элемент, добавлен-ный последним. Добавление элементов в очередь выполняется в конец списка, следовательно, первым будет обрабатываться эле-мент, помещенный в очередь первым. Так вычислительная сложность выполнения операций определения первого и следующего элементов в среднем для очереди Q = 1, а для стека – Q = n /2. И, наоборот, вычислительная сложность выполнения операций определения последнего и предыдущего элементов в среднем для очереди Q = n /2, а для стека – Q = 1.Соответственно, вычислительная сложность добавления элемента в среднем для стека Q = 1, а для очереди – Q = n /2, так как предполагает поиск конца списка.

Вычислительная сложность удаления элемента не зависит от дисциплины обработки, так как при выполнении этой операции в любом случае приходится искать адрес либо предыдущего (очередь), либо следующего элемента (стек), адрес которых не хранится в удаляемом элементе, поэтому в среднем вычислительная сложность выполнения операции удаления для односвязного списка Q = n/ 2.

Однако, если в процессе поиска удаляемого элемента сохранять адрес предыдущего элемента списка, то удаление элемента может быть выполнено со сложностью Q = 1. Аналогично, операция добавления также может быть выполнена со сложностью Q = 1.

Вычислительная сложность поиска элемента по номеру или значению, а также поиска экстремумов и значений, следующих за ними, и для стека и для очереди в среднем Q = n/ 2. Аналогично модели вектора сопоставим каждому элементу множества ZAE вычислительную сложность выполнения операций с этим эле-ментом, т. е. ZAE ® Qo, где Qo = { Qoi, i =1,| Op | }, где Qoi – вычислитель-ная сложность выполнения i -ой операции opi Î Op для элемента z Î ZAE.