Содержание к диссертации
Введение
1. Анализ существующих методов синтеза структур данных и постановка задачи 10
1.1. Анализ существующих методов оптимизации структур данных 10
1.1.1. Языки сверхвысокого уровня и абстрактные типы данных 10
1.1.2. Специализация структур данных 12
1.1.3. Оптимизация структур данных, использующих указатели 15
1.1.4. Оптимизация структур данных с большим количеством элементов 18
1.2. Анализ методов автоматического выбора оптимальных структур данных 20
1.3. Анализ существующих формальных описаний структур данных 27
1.4. Постановка задачи синтеза оптимальных структур данных 28
2. Разработка моделей структур данных 33
2.1. Анализ операций над структурами данных 33
2.2. Модели базовых одноуровневых структур данных 38
2.3. Модели комбинированных одноуровневых структур данных 53
2.4. Формальная постановка задачи синтеза одноуровневой структуры данных 68
2.5. Модели базовых двухуровневых структур данных 71
2.6. Формальная постановка задачи синтеза двухуровневой структуры данных 88
3. Разработка методики синтеза оптимальных структур данных и генерации их описаний 93
3.1. Синтез комбинированных одноуровневых структур данных 93
3.1.1. Разработка алгоритма решения задачи синтеза оптимальной одноуровневой структуры данных 93
3.1.2. Входные данные и способы их представления 97
3.1.3. Способ задания функций одного переменного 101
3.1.4. Реализация операции объединения структур данных 106
3.1.5. Генерация описания одноуровневой структуры данных 108
3.2. Синтез многоуровневых структур данных 111
3.2.1. Разработка алгоритма синтеза двухуровневой структуры 111
3.2.2. Генерация описания многоуровневой структуры данных 115
4. Экспериментальные исследования полученных результатов 118
4.1. Программное обеспечение системы синтеза оптимальных структур данных 118
4.2. Исследование зависимости вычислительной сложности реализации алгоритма уравновешенной двоичной свертки от структур данных 120
4.3. Исследование зависимости вычислительной сложности алгоритма неуравновешенной двоичной свертки от свойств входных данных 135
4.4. Исследование зависимости вычислительной сложности алгоритма лингвистического анализа текста от структур данных 146
Выводы 152
Список литературы 154
Приложения 159
- Анализ методов автоматического выбора оптимальных структур данных
- Модели комбинированных одноуровневых структур данных
- Синтез многоуровневых структур данных
- Исследование зависимости вычислительной сложности реализации алгоритма уравновешенной двоичной свертки от структур данных
Введение к работе
Актуальность. К задачам структурного анализа и синтеза относят задачи исследования или определения некоторого варианта структуры объекта, под которой понимают совокупность составляющих его элементов и связей между ними [19]. В качестве моделей объекта и результата в этих задачах обычно используются графы различных типов, позволяющие отображать существенные с точки зрения решаемой задачи отношения между компонентами рассматриваемой структуры.
Большинство задач анализа структур относится к классу комбинаторных, а синтеза - комбинаторно-оптимизационных и применительно к вычислительной технике имеют большую размерность входа. В настоящее время речь идет о десятках и сотнях тысяч компонентов при исследовании и разработке структур аппаратных средств и о тысячах компонентов для задач, связанных с созданием программного обеспечения.
В целом решение задачи структурного анализа и синтеза - трудоемкий процесс, предполагающий исследование свойств исходного объекта и результата проектирования и построение адекватной математической модели. По результатам исследования определяют последовательность операций преобразования модели исходного объекта в модель результата проектирования. После этого необходимо выбрать структуры данных для представления используемых моделей и реализовать эти операции на выбранном универсальном языке программирования, что с учетом сложности реализации графовых моделей, также является процессом, требующим больших трудозатрат, как на написание программы, так и на тестирование и отладку последней.
Вычислительная сложность вариантов реализации алгоритма при использовании различных структур данных может отличаться на несколько порядков. Данная задача, т.е. задача синтеза оптимальных структур данных, является самостоятельной научной проблемой, актуальной для многих научно-технических направлений. На данный момент существуют системы, которые
решают лишь задачу выбора оптимальной структуры данных [32, 49, 51], в то время как формальной постановки задачи синтеза до сих пор не было получено.
В данной работе выполнена формальная постановки задачи синтеза оптимальных структур данных, а также предложен метод её решения, который успешно реализован в виде системы синтеза оптимальных структур данных. Создание подобных средств позволяет существенно упростить разработку и анализ алгоритмов решения задач анализа и синтеза структур, предоставляя разработчику алгоритмов возможность реализации, оценки и исследования различных методов и алгоритмов с учетом затрат памяти и времени их выполнения.
Цель работы - создание комплекса математических, лингвистических и программных средств автоматической генерации структур данных, оптимальных с точки зрения вычислительной сложности операций над данными и используемых для представления объектов задач структурного синтеза.
Основные решаемые задачи. Для достижения указанной цели в работе потребовалось:
Выполнить анализ существующих структур данных с целью выявления их свойств и классификации основных операций над ними.
На основании проведённого анализа разработать модели структур данных, позволяющие оценивать влияние организации данных на ёмкостную и вычислительную сложность.
Выполнить формальную постановку задачи синтеза оптимальной структуры данных и разработать метод её решения.
Разработать способ генерации синтаксически корректных конструкций описаний оптимальных структур данных.
Разработать программную систему синтеза оптимальных структур данных для представления взвешенных множеств и графовых моделей.
6. Выполнить экспериментальную проверку полученных теоретических результатов.
Методы исследований. Выполненная работа характеризуется комплексным подходом к решению поставленной проблемы. Результаты диссертационной работы получены на базе использования методов анализа, синтеза и оптимизации. Математическую основу составляет аппарат теории графов, теории множеств и математической логики, а также теория формальных языков и методы грамматического разбора.
Научная новизна работы. В процессе исследования получены следующие новые научные результаты, представляемые на защиту:
Выполнена систематизация существующих и предложены новые способы оптимизации структур данных, представляющих графовые модели, по критерию минимальной вычислительной сложности операций над ними.
Разработаны структурные модели базовых и комбинированных способов организации данных, применимые для автоматической оценки вычислительной и ёмкостной сложностей алгоритмов решения задач на графах, а также определены формальные правила перехода от объектов к моделям.
Формально определена операция объединения моделей структур данных, позволяющая получать модели комбинированных структур данных и их характеристики из базовых.
Получена формальная постановка задач синтеза оптимальных с точки зрения минимума вычислительной сложности алгоритма одноуровневых и двухуровневых структур данных для представления графовых моделей, разработаны и реализованы алгоритмы их решения.
Разработан алгоритм генерации синтаксически корректных конструкций описаний структур данных для синтезированных моделей.
Практическая ценность работы. По результатам проведенных исследований создана программная система синтеза оптимальных структур данных, которая включает модуль генерации оптимальных структур данных, анализа-
тор вычислительной и емкостной сложности структур данных, библиотеки шаблонов описаний классов абстракций, а также макрогенератор описаний структур данных. Система позволяет автоматизировать процесс синтеза структур данных а также позволяет получать оценки вычислительной и ёмкостной сложностей для сгенерированных структур.
Апробация работы. Основные положения работы обсуждались на научно-технической конференции, посвященной 175-летию МГТУ им. Н.Э. Баумана (Москва, 2005), на научной конференции «Информатика и системы управления», проходившей в МГТУ им. Н.Э. Баумана (Москва, 2007).
Реализация и внедрение. Все основные теоретические и практические результаты работы в виде методик и программных средств внедрены в промышленность. Они использованы при разработке очередной версии системы защиты Windows-приложений StarForce Protection Builder 5.70 в ООО «Протекшей Технолоджи» (StarForce) и при создании системы анализа и классификации текстов БКФ 2.00 в ЗАО «ИнфоВотч» (дочерняя компания ЗАО «Лаборатория Касперского»). Документы, подтверждающие внедрение, приведены в приложении.
Публикации. По результатам диссертационной работы автором опубликовано 7 статей.
Объем и структура диссертации. Диссертационная работа включает введение, четыре главы, заключение и список литературы, занимающих 159 страниц текста, в том числе 32 рисунка и 23 таблицы, список использованной литературы из 58 наименований на 6 страницах.
Содержание работы. Во введении обоснована актуальность темы диссертации, сформулированы основные задачи, научные результаты и практическая ценность, дано краткое содержание глав.
В первой главе выполнен анализ существующих способов оптимизации структур данных, а также предложены новые. Сделаны выводы относительно возможности применения рассмотренных способов в случае синтеза структур
данных. Также проведён анализ существующих алгоритмов автоматического выбора структур данных и показаны их недостатки. Содержательно определены задачи, которые необходимо решить при создании системы генерации оптимальных структур данных. К ним относятся задачи разработки моделей комбинированных и многоуровневых структур данных, формальной постановки задачи синтеза оптимальных структур данных, разработки модуля синтеза оптимальных структур данных для представления графовых моделей и макрогенератора описаний структур данных.
Во второй главе выполнен анализ наиболее часто используемых операций над структурами данными и предложена классификация операций. Исследованы отношения между компонентами базовых структур данных, построены их обобщенные математические модели, определены расчетные формулы, позволяющие определить вычислительную и ёмкостную сложность базовых структур данных по их моделям.
Проанализированы особенности построения комбинированных и многоуровневых структур данных и по результатам этого анализа предложено получать модели таких структур объединением моделей соответствующих базовых структур. Показано, что вычислительная и ёмкостная сложности комбинированных и многоуровневых структур могут быть рассчитаны по предлагаемым моделям. Выполнена формальная постановка задач синтеза оптимальной одноуровневой и двухуровневой структур данных.
Таким образом, в данной главе сформулированы основные положения, положенные в основу автоматизированной системы синтеза оптимальной структуры данных.
В третьей главе разработан способ решения задачи синтеза оптимальных структур данных. Разработаны алгоритмы синтеза одноуровневых и двухуровневых оптимальных с точки зрения вычислительной сложности структур данных. Предложен способ задания описаний базовых структур данных на
универсальном языке программирования, а также предложен вариант реализация операции объединения структур данных.
Четвёртая глава посвящена описанию практических результатов работы. В начале главы определен состав и структура программного обеспечения, которое должно быть включено в автоматизированную систему. Остальная часть главы содержит описание результатов экспериментальных исследований, выполненных для подтверждения основных теоретических положений диссертации. Сформулированы цели исследований, даны характеристики объектов. Приведены результаты исследований.
Проведенные эксперименты подтвердили результаты теоретических исследований, показали работоспособность системы и ее высокую эффективность при разработке алгоритмов решения комбинаторных задач структурного анализа и синтеза.
Анализ методов автоматического выбора оптимальных структур данных
В литературе [13, 52] встречается упоминание о двух системах генерации оптимальных структур данных. Первая из этих систем представляет собой встроенный оптимизатор языка SETL, который позволяет в полуавтоматическом режиме выбрать оптимальную структуру данных, а затем автоматически генерирует описание её реализации. Более подробно описание применяемого метода выбора структур данных представлено ниже. Вторая система подробно описана в [13]. В этой системе выбор структуры данных осуществляется пользователем, а синтез её описания выполняется автоматически при помощи специализированного макрогенератора, который подробно рассмотрен в [10].
SETL (setheoretically oriented language) представляет собой язык программирования сверхвысокого уровня, основанный на множествах [34, 46, 52]. Этот язык был специально создан для упрощения разработки алгоритмов на графах. Программу, написанную на языке SETL, можно автоматически транслировать в эквивалентную ей программу на языке C/C++ или Ada.
Язык SETL является слабо-типизированным языком, что означает, что при написании программы нет необходимости объявлять переменные перед их использованием. Транслятор языка SETL сам определяет тип используемой переменной и создаёт необходимые для её реализации структуры данных. Тип данных для конкретной переменной определяется исходя из операций, которые над ней выполняются. Выбор организации элементов данных для сложных структур данных производится также на основании выполняемых над ними операций [49, 50].
Рассмотрим простую программу на языке SETL, и получающиеся в результате работы оптимизатора структуры данных [48]. Программа реализует
Рассмотрим способ представления структур данных, используемый языком SETL. В основе данного способа лежит понятие базиса. Базис - множест во допустимых значений для данной переменной. Фактически базис является универсумом данной переменной. В примере определён только один базис -nodes, содержащий все вершины исходного графа. Физически базис представляется как хеш-таблица элементов данных, при этом значение ключа в этой таблице не имеет семантического смысла и служит только для ускорения поиска элементов. Каждый элемент базиса содержит некоторое значение и набор специальных полей для представления переменных программы, которые ссылаются на базис. Например, выражение х є nodes означает, что х на самом деле реализуется как указатель на элемент в базисе nodes, содержащий искомое значение переменной х.
Множества на основе базиса могут быть представлены тремя способами: 1) local set - в каждом элементе базиса отводится бит для хранения флага принадлежности данного элемента множеству; 2) indexed set - битовый вектор хранится отдельно от самого базиса, а каждый элемент базиса имеет уникальный индекс, идентифицирующий позицию бита для данного элемента в векторе; 3) sparse set - отдельно от базиса хранится хеш-таблица с фиктивным ключом, содержащая указатели на все элементы данного множества.
Отображения также могут представляться тремя способами: 1) local map - в каждый элемент базиса добавляется поле, содержащее либо сами данные, либо указатель на список указателей на элементы базиса; 2) indexed map - по аналогии с indexed set данные хранятся отдельно от элемента; 3) sparse map - вся хеш-таблица, содержащая ключи (в виде указателей на элементы базиса) и значения (в виде скалярных величин, либо в виде указателей на элементы базиса), хранится отдельно.
Процесс выбора структур данных выполняется за три этапа. Целью первого этапа является построение управляющего графа программы, содержаще го информацию, которая необходима в процессе выбора структур данных. На первом этапе выполняется мониторинг выполнения программы на одном типовом наборе входных данных. На основании данных мониторинга строится управляющий граф программы, в который в качестве узлов входят все управляющие конструкции программы, а также все выражения, оперирующие со структурами данных.
Второй этап начинается с процедуры обработки управляющего графа с целью получения информации о типах элементов, хранимых в структурах данных, типах операций над структурами данных и аргументов, используемых при выполнении этих операций. Этот этап необходим, так как SETL является слабо-типизированным языком. Далее производится разбиение на классы эквивалентности - определение сходных структур данных, для которых можно генерировать одно и то же представление. Завершается этап опросом пользователя, в ходе которого система задаёт пользователю вопросы о предполагаемом количестве элементов в используемых структурах данных, а также о вычислительной сложности отдельных операций. На этапе анализа все циклы считаются циклами с одной итерацией.
Модели комбинированных одноуровневых структур данных
В результате объединения двух и более структур данных получается новая комбинированная структура. Очевидно, что и результирующая и исход ные структуры должны описывать размещение одних и тех же элементов данных в памяти. То есть набор данных и для исходных структур и для структуры-результата должен быть один и тот же. Рассмотрим, каким образом можно представить рассмотренную ранее комбинированную структуру данных дерево-вектор (см. 1.4) в терминах предлагаемой модели, разработанной ранее, а также определим операцию объединения моделей двух структур данных с учётом возможных вариантов.
Для доступа к данным комбинированной структуры дерево-вектор можно использовать как дерево, так и вектор, в зависимости от типа операции доступа. Например, для доступа по номеру логично использовать вектор, так как вычислительная сложность данной операции для него меньше. Однако, в данном случае вектор содержит не элементы данных, а указатели на них, что приводит к следующим негативным последствиям: 1) происходит увеличение вычислительной сложности доступа данным на единицу, так как для получения самих данных необходимо производить разыменование указателя;2) ёмкостная сложность увеличивается на величину 1Ап; 3) может возрасти фрагментация свободной памяти за счёт большого количества операций выделения блока памяти.
С другой стороны, структуры данных, содержащие указатели на данные, проще поддаются объединению. Если же использовать структуры данных, которые требуют разыменования более одного указателя при доступе к данным, то влияние вышеописанных последствий удвоится, а операция объединения не упростится. В связи с этим, при разработке операции объединения исключим из рассмотрения все структуры данных, которые требуют разыменования более одного указателя при доступе к данным. Таким образом, при объединении двух любых структур данных возможны три варианта:1) обе структуры содержат указатели на элементы данных; 2) одна структура содержит указатели на элементы данных, другая - сами элементы данных; 3) обе структуры непосредственно содержат элементы данных.
В зависимости от типов исходных структур, некоторые варианты объединения могут быть бессмысленными. Например, битовый вектор не может непосредственно хранить данные (либо указатели в явной форме), что приводит к невозможности его использования в третьем варианте объединения. Также количество вариантов объединения может существенно сократиться, если на реализацию результирующей структуры данных наложены какие-либо ограничения. Например, если ограничен максимальный размер непрерывного участка памяти, занимаемого всей структурой данных, либо её частью.
Рассмотрим процесс объединения моделей двух структур данных, содержащих указатели на данные на примере объединения модели вектора (см. рис. 2.7) и модели древовидного списка (см. рис. 2.8).
Синтез многоуровневых структур данных
Перед выбором метода решения задачи синтеза, необходимо оценить мощность полного множества решений, которая в данном случае существенно больше, чем в случае с одноуровневой структурой. Оценку будем производить для наиболее сложной структуры данных, которая реализует отношение «многие-ко-многим» (см. 2.3). В состав этой структуры данных входит 4 типа одноуровневых структур данных. Учитывая, что существует порядка 528 возможных вариантов (см. 3.1.1) построения одноуровневой структуры данных, получаем мощность множества решений порядка 5284 « 6 1010. При таком большом количестве вариантов использовать прямой перебор будет нерационально, поэтому необходимо разработать способ сокращения количества рассматриваемых вариантов.
Вычислительная сложность операций над двухуровневой структурой данных зависит от вычислительной сложности операций над одноуровневыми структурами данных, включёнными в её состав. Например, вычислительная сложность операции добавления значения по заданному ключу для структуры, реализующей отношение «многие-ко-многим», вычисляется по форму 8). В этом случае при выполнении операции добавления значения по ключу потребуется выполнить одну операцию добавления в одноуровневую структуру под номером 2. На основании функций, определяющих вычислительную сложности всех операций, можно вывести множество функций (/) = F{P)\ описывающих зависимость количества повторений любой операции над одноуровневой структурой, в зависимости от количества повторений операций всех типов над многоуровневой структурой данных (т.е. от множества функций Р). Наличие подобных множеств (Рг) позволяет свести решение задачи синтеза многоуровневой структуры к синтезу набора оптимальных одноуровневых структур.
Используя данный способ можно сразу получить наилучшее с точки зрения вычислительной сложности решение для рассмотренного ранее примера, при этом для его получения необходимо просмотреть не более чем 4 528 = 2112 вариантов одноуровневых структур данных. Однако, получен ное решение может не соответствовать ограничению по ёмкостной сложности результирующей структуры. Для получения решения, соответствующего данному ограничению, необходимо использовать частичный перебор, который заключается в замене наименее критичных к скорости одноуровневых структур данных, их более медленными аналогами, имеющими меньшую ёмкостную сложность.
Входными данными алгоритма синтеза комбинированных многоуровневых структур данных являются: 1) множество операций, выполняемых структурой данных и количество повторений каждой операции в зависимости от размера входа задачи P = множество базовых одноуровневых структур данных 3) множество базовых многоуровневых структур данных 4) максимальная емкостная сложность результирующей структуры данных размер элемента данных структуры Ґ, размер ключа - 1к; 5) максимальное количество элементов структуры данных (максимальное количество пар ключ-значение) - Атгх ; 6) максимальное количество значений, соответствующих одному ключу 8) максимальное количество ключей, соответствующих одному ЗНаче 9) максимальный размер непрерывного блока памяти, выделяемого струк турой данных т;
Исследование зависимости вычислительной сложности реализации алгоритма уравновешенной двоичной свертки от структур данных
Целью исследования является анализ работоспособности модуля синтеза оптимальных двухуровневых структур данных.
В качестве объекта исследования был использован алгоритм уравновешенной двоичной свертки, который применяется для решения задачи деком позиции функциональных схем устройств вычислительной техники. Выбор обусловлен тем, что данный алгоритм хорошо исследован [21], и, соответственно, существует возможность сравнения результатов, полученных с применением разработанной системы, с теми, которые уже известны. Кроме этого в алгоритме использованы операции удаления элементов из множества, вычислительная сложность которых меняется с и до 1 при замене представления множества вектором представлением того же множества списком, что позволяет предположить целесообразность такой замены. В то же время в алгоритме встречаются операции обращения к элементам тех же множеств по индексу, сложность которых при указанной замене наоборот возрастает от 1 до п, что делает необходимым исследование зависимости вычислительной сложности алгоритма от используемых структур данных.
Разработка программы выполнялась по алгоритмической модели, приведенной в [21]. В табл. 10 представлено описание данных, а в табл. 11 — описание исследуемого алгоритма.
В таблице А - максимальное количество вершин, входящих в ребро гиперграфа (для рассматриваемого примера А = 3), операция получения следующего показателя связности не рассматривается, так как любая структура данных способна обеспечить вычислительную сложность 0{\). В качестве тестового набора данных был использован наиболее сложный гиперграф из работы [13], который содержит 210 вершин. Это позволило сравнить данные эксперимента с полученными ранее результатами.
С точки зрения процесса генерации оптимальной структуры данных, наиболее сложной является реализация структуры данных IX, так как над ней выполняются операции доступа, поиска, а таюке добавления и изменения. В таблице 14 приведены значения времени выполнения программы при различных способах реализации этой структуры данных. среднее время выполнения подсчитывается при условии оптимальности всех остальных структур данных, используемых реализацией алгоритма и при размере выборки равным 100 измерениям.
Последняя приведённая в таблице структура данных является результатом работы алгоритма синтеза оптимальной структуры данных. В таблице 15 приводится вычислительная сложность отдельных операций над оптимальной структурой данных. Для представления графа оптимальной структурой данных будет структура «многие-ко-многим» в которой связь между значениями и ключами реализуется посредством двусвязного списка, а все остальные множества реализуются бинарными деревьями. Вычислительная сложность отдельных операций над полученной структурой данных приводится в таблице 16.
В таблице р - максимальное количество показателей связности, которое может соответствовать одной вершине, к — максимальное количество вершин, п - максимальное количество уникальных значений показателей связности, 8 — максимальное количество вершин, имеющих одинаковый показатель связности.
В таблице p - максимальное количество ребер инцидентных одной вершине, к - максимальное количество вершин, п - максимальное количество ребер, 8 - максимальное количество вершин, инцидентных одному ребру.
Программа, использующая оптимальные структуры данных, была протестирована в соответствии с правилами функционального тестирования на автоматически генерируемых случайных наборах данных. Во всех случаях результаты ее работы совпали с результатами работы программы, использующей простые структуры данных.
Исследование влияния оптимальных структур данных на время выполнения программы основано на произведении измерений времен начала и завершения решения задачи. Поэтому, прежде всего, необходимо определить факторы, влияющие на достоверность результатов измерений. Такими факторами являются: 1) точность аппаратных средств; 2) «накладные» расходы функции Time Delphi; 3) многопрограммность используемой операционной системы Windows ХР, которая «параллельно» может выполнять служебные действия. Аппаратным средством, используемым для получения отсчетов времени, является таймер, который генерирует сигнал изменения часов реального времени. С помощью специальной функции API GetSystemTimeAdjiistmentQ было получено, что время между «тиками» таймера составляет 14625000 не = 0,0146250 с. Откуда ошибка одного измерения с использованием таймера составляет примерно 0,01 с. Время выполнения программы определяется как разность двух измерений, откуда ошибка колеблется в интервале [0; 0,02] (с).
Функция Time - это порядка 100 машинных команд, что для тактовой частоты /= 100 МГц требует примерно 0,000001 (с). Этой погрешностью на фоне ошибки измерения, получаемой за счет таймера, можно пренебречь.
В условиях эксперимента никаких дополнительных действий, кроме обработки «тиков» таймера, компьютер не выполнял (программе был выставлен класс приоритета Realtime), поэтому этой погрешностью на фоне остальных также можно пренебречь.
