Каждой операции, определенной в уточненной объектной модели,
должен быть сопоставлен алгоритм, реализующий эту операцию. При выборе алгоритма
можно руководствоваться следующими соображениями:
- вычислительная сложность алгоритма:
для алгоритмов, применяемых к
достаточно большим массивам данных, важно, чтобы оценка их вычислительной
сложности была разумной; например, вряд ли имеет смысл избегать косвенности в
ссылках, особенно когда введение косвенности существенно упрощает понимание
программы; в то же время замена пузырьковой сортировки с оценкой сложности
n2 на алгоритм сортировки с оценкой n?log n всегда
резко ускоряет вычисления;
- понятность алгоритма и легкость его реализации
: для достижения этого
можно даже пойти на небольшое снижение эффективности; например, введение
рекурсии всегда снижает скорость выполнения программы, но упрощает ее понимание
(рисунок 3.8);
- гибкость
: большая часть программ рано или поздно должна быть
модифицирована; как правило, высокоэффективный алгоритм труден для понимания и
модификации; одним из выходов является разработка двух алгоритмов выполнения
операции: простого, но не очень эффективного, и эффективного, но сложного; при
модификации в этом случае изменяется более простой алгоритм, что обеспечивает
работоспособность системы на период разработки более эффективного
модифицированного алгоритма.
Рис. 3.8. Сравнение рекурсивного и нерекурсивного алгоритмов
вычисления n!
Выбор алгоритмов связан с выбором структур данных,
обрабатываемых этими алгоритмами. Удачный выбор структур данных позволяет
существенно оптимизировать алгоритм.
Еще одним способом упрощения и оптимизации алгоритмов является
введение внутренних (вспомогательных) классов. Эти классы не имеют соответствий
в реальном мире; они связаны с реализацией, но могут существенно упростить ее
(примеры: класс стек, класс двусвязный список и т.п.).
Наконец, во многих случаях бывает полезным внести некоторые
изменения в структуру объектной модели. Эти изменения сводятся к введению
дополнительных классов и к перераспределению операций между классами.
При распределении операций по классам руководствуются
следующими соображениями:
- если операция выполняется только над одним объектом, то она определяется в
классе, экземпляром которого является этот объект;
- если аргументами операции являются объекты разных классов, то ее следует
поместить в класс, к которому принадлежит результат операции;
- если аргументами операции являются объекты разных классов, причем изменяется
значение только одного объекта, а значения других объектов только читаются, то
ее следует поместить в класс, к которому принадлежит изменяемый объект;
- если классы вместе с их зависимостями образуют звезду с центром в одном из
классов, то операцию, аргументами которой являются объекты этих классов, следует
поместить в центральный класс.
|