Дж. Рамбо, М. Блаха - UML 2.0 - Объектно-ориентированное моделирование и разработка (1158633), страница 78
Текст из файла (страница 78)
1. Выбор алгоритмов, минимизирующих стоимость реализации операций. 2. Выбор структур данных, соответствующих алгоритмам. 3. Определение новых внутренних классов и операций. 4. Назначение операций подходящим классам. 15.4.1. Выбор алгоритмов Многие операции реализуются очевидным образом, так как они сводятся к прослеживанию модели классов и получению или изменению значений атрибутов или связей. Для записи таких операций удобно использовать систему обозначений языка ОС1.
(См. главу 3). Некоторые операции не могут быть полностью выражены в виде цепочек прослеживания связей модели классов. Для описания таких ситуаций мы обычно используем псевдокод. Псевдокод помогает обдумывать алгоритм, не углубляясь в тонкости программирования. Например, многие приложения связаны с графами и с транзитивным замыканием (транзитивным замыканием называется набор вершин, которые непосредственно или косвенно связаны с некоторой исходной вершиной).
На рис. 15.3 показана простая модель неориентированного графа, а в листинге 15.1 приведен псевдокод, позволяющий вычислить транзитивное замыкание. Мобе::соерпгетгапв1С1зес1овпге () гегогпв Мобезег побез:=сгеагектргузег) гегпгп ве1Т.ТС1оор (побез)) кобе::ТС1оор (побез:Мобезег) гегогпв МобеБеС абб ве11 Со побев) Тог вась ебве 1п зе1г.вбое Тог еасн побе 1п ебде.небе /* 2 побев аге азвос1агеб етСЬ ап ебде */ гв побе 1в пог 1п побез сьеп побе.ТС1оор(побез) епб гв епб Тог еасн побе епб Тог еась ебве Рис.
15.3. Модель неориентированного графа Листинг 1$.1. Псевдокод поиска транзитивного замыкания зобе::сопригетгапв1С1зес1озиге () геСпгпв Мобезег побез:= сгеасееерсузес) геСпгп ве1Г.ТС1аор (побез)( мобе::ТС1оор (побез:Мобезег) гегигпв Мобезег абб ве11 Со побоев 15Я. Проектирование алгоритмов 329 гог еасЬ ебде 1п зе11.кбзе гог еасЬ побе 1п ебэе.вобе /* каждая луга связывает две вершины */ 11 побе ьз поз ьп побез Сьев побе.тегоор(побез>; епб 11 епб Тот еась побе епб Гог вась ебзе Когда эффективность не слишком важна, нужно выбирать простые алгоритмы. На практике производительность приложения определяется небольшим количеством операций (так называемыми узкими местами — Ьотт/елесяз).
В среднем на 20 /з операций приходится 80;/з времени выполнения. Остальные операции лучше всего сделать простыми, понятными и удобными для программирования. Творческую активность лучше направить на алгоритмы тех операций, которые могут стать узкими местами приложения. Например, поиск значения в множестве из п элементов методом перебора требует в среднем п/2 операций, тогда как бинарный поиск выполняется за 1оя л операций, а поиск по хэш-таблице вообще в среднем требует менее двух операций. Ниже мы приводим некоторые рекомендации по выбору между альтернативными алгоритмами. ° Вычислительная сложность. Как зависит длительность вычислений от размера структур данных? Не обращайте внимания на незначительные факторы, влияющие на эффективность.
Дополнительный уровень косвенной адресации может значительно повысить ясность алгоритма, а на скорость вычислений он почти не повлияет. Однако сложность алгоритма нужно учитывать обязательно. Время выполнения (или объем занимаемой памяти) может по-разному зависеть от количества входных данных: быть константой, линейно, квадратично или зкспоненциально. Например, печально известный алгоритм сортировки еметодом пузырька» выполняется за время, пропорциональное л', тогда как большинство альтернативных алгоритмов сортировки выполняются за время, пропорциональное и!ой п. ° Простота реализации и понятность. Для некритических операций можно пожертвовать производительностью в тех случаях, когла имеется более простой алгоритм. По этой причине нужно стараться следовать аналитической модели на этапе проектирования и вносить в нее лишь самые необходимые изменения. Если у вас нет проблем с производительностью, не тратьте время на оптимизацию, потому что это затруднит понимание модели и усложнит программирование.
° Гибкость. Раньше или позже большинство программ требуют расширения. Сильно оптимизированные алгоритмы часто затрудняют внесение подобных изменений. В некоторых случаях полезно иметь две версии критических операций: простой и неэффективный алгоритм, который можно реализовать быстро и использовать для проверки системы, и сложный, но эффективный алгоритм, который можно будет сравнивать с простым. Пример с банкоматом. Взаимодействие между компьютером консорциума н банковскими компьютерами может быть достаточно сложным. Одна из проблем ЗЗО Глава 15 ° Проектирование классов связана с распределенностью вычислений: компьютер консорциума находится в одном месте, а банковские компьютеры — во множестве других мест.
Важно, чтобы компьютер консорциума допускал масштабирование: сеть банкоматов ие может оправдать затраты иа слишком мошиый компьютер консорциума, ио этот компьютер должен быть способен обслуживать новые банки по мере их присоединения к консорциуму. Третий вопрос связан с тем, что банковские системы представляют собой отдельные приложения, существующие независимо от системы банкоматов.
Это приводит к неизбежным преобразованиям и компромиссам, связанным с необходимостью поддерживать различные форматы данных. По этим причииам выбор алгоритмов, коордииируюших взаимодействие коисорциума и банка, является достаточно важным решением. Во многих банках имеются сложные системы предотврашеиия потерь. Поэтому решение о принятии или отклонении запроса от банкомата о снятии денег со счета может определяться ие простой формулой, а сложной внутренней логикой.
Это решение может зависеть от оценки кредитоспособности клиента, его поведеиия в прошлом, а также от соотношения баланса на счете и запрашиваемой суммы. Хорошие алгоритмы сокращают потери банков, что сопровождается возрастаиием стоимости расходов иа разработку. 15.4.2. Выбор структур данных Алгоритмы работают с определенными структурами даииых. На этапе аиализа вас интересовала логическая структура информации в системе, ио иа этапе проектирования вы должны предложить структуры данных, которые позволят реализовать эффективные алгоритмы. Структуры данных ие добавляют в аиалитическую модель новой информации, оии служат тому, чтобы организовать эту информацию в форме, удобной для применения алгоритмов.
Многие структуры данных являются экземплярами классов-контейнеров. К таким структурам отиосятся массивы, списки, очереди, стеки, множества, мультимиожества, словари, деревья и их разновидности, такие как очереди с приоритетом и бинарные деревья. Большинство объектио-ориеитироваииых языков содержат уииверсальигяе структуры данных в библиотеках предопределенных классов.
Пример с банкоматом. Тгапзасаоп (Траизакция) состоит из множества Урдаге (Обиовлеиие). Мы должны пересмотреть модель классов — иа самом деле, транзакция представляет собой последовательность обновлений, то есть класс Ттапьасгюп должен содержать упорядоченный список Гранате. Обдумывая алгоритмы и изучая логику приложения, вы будете находить недостатки и совершенствовать модель классов. 15.4.3.
Определение внутренних классов и операций В процессе декомпозиции высокоуровневых операций вам придется придумывать новые операции, относящиеся к более низким уровням. Некоторые низкоуровиевые операции могут относиться к «операциям по списку» (см. главу 13) 15.4. Проектирование алгоритмов 331 аналитической модели. Однако чаше всего добавления новых операций избежать не удается. Раскрытие алгоритмов может вызвать необходимость создания новых классов лля хранения промежуточных результатов.
Обычно эти классы отсутствуют в постановке задачи, так как они относятся к артефактам приложения. Пример с банкоматом. Среди действий, относящихся к сфере ответственности варианта использования ргосехз ггапзасйоп (обработка транзакции), мы выделили печать клиентского чека. Банкомат должен печатать на чеке все действия клиентов, чтобы они не забывали о них. В аналитической модели класс Яесе~рг (Чек) отсутствовал, поэтому нам придется добавить его. 15.4.4. Назначение операций классам Когда класс имеет отношение к реальному миру, его операции обычно достаточно очевидны.
В процессе проектирования добавляются внутренние классы, соответствующие не объектам реального мира, а лишь некоторым их аспектам. Поскольку этн классы придумываются вами, они являются в достаточной степени произвольными, н границы между ними определяются не логической необходимостью, а удобством.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
