Разработка алгоритмов, реализующих полученные операции

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

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

- понятность алгоритма и лёгкость его реализации: для достижения этого можно даже пойти на небольшое снижение эффективности; например, введение рекурсии всегда снижает скорость выполнения программы, но упрощает её понимание (рис. 3.7);

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

Определение функции n!

0! = 1

n!= nx(n-1)

Нерекурсивный алгоритм Рекурсивный алгоритм

factorial (int n) fact (int n)

{ {

Int 1, f=1 Int f=1

for (1=n, 1 > 0: 1--) If (n > 0)

f = f^1: f = f^ fact (n – 1):

return (f): return (f):

} }

Рис. 3.7. Сравнение рекурсивного и нерекурсивного

алгоритмов вычисления n!

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

Ещё одним способом упрощения и оптимизации алгоритмов является введение внутренних (вспомогательных) классов. Эти классы не имеют соответствий в реальном мире; они связаны с реализацией, но могут существенно упростить её (примеры: класс стек, класс двусвязный список и т.п.).

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

При распределении операций по классам руководствуются следующими соображениями:

- если операция выполняется только над одним объектом, то она определяется в классе, экземпляром которого является этот объект;

- если аргументами операции являются объекты разных классов, то её следует поместить в класс, к которому принадлежит результат операции;

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

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

Оптимизация разработки

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

- добавляются избыточные зависимости, чтобы минимизировать потери, связанные с доступом к данным, и максимизировать удобство работы с ними;

- изменяется порядок вычислений для достижения большей эффективности;

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

На этапе анализа требований к программной системе избыточные зависимости нежелательны, так как они не вносят в модель новой информации. Однако на этапе разработки мы должны приспособить структуру объектной модели к требованиям эффективной реализации системы. Пример использования избыточной (производной) зависимости для повышения эффективности поиска представлен на рисунке 3.9: на рисунке 3.8(а) показаны зависимости из исходной объектной модели; добавление производной (и, следовательно, избыточной) зависимости (рис. 3.9(б)) позволяет резко ускорить поиск сотрудников, говорящих по-китайски.

б)

а)

Рис. 3.8. Ускорение поиска с помощью производной зависимости

Рис. 3.9. Использование производных атрибутов

для исключения повторных вычислений

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

Рис. 3.10. Использование производной зависимости

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

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

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

- периодическое перевычисление всех производных атрибутов (в мо-мент изменения базового значения производные атрибуты перевычисляются);

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

Реализация управления

Реализация управления связана с реализацией динамической модели объектов системы. Известны три подхода к реализации динамической модели:

- процедурное управление: состоянию соответствует определённый фрагмент программы;

- управление через события: явная реализация конечного автомата;

- использование параллельных независимых задач.

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

Пример практического использования процедурного управления представлен на рисунке 3.11.

Рис. 3.11. Псевдокод, соответствующий динамической модели ATM