Лекция 5. Модели жизненного цикла. Лекция Модели жизненного цикла по, проектирование как конструирование. Аннотация
 Скачать 0.94 Mb.
|
|
Производящие шаблоны Производящие шаблоны (creational patterns) предназначены для обеспечения выполнения одной из самых распространенных задач в ООП — создания объектов в системе. В ходе работы большинства объектно-ориентированных систем, независимо от уровня их сложности, создается множество экземпляров объектов. Производящие шаблоны облегчают процесс создания объектов, предоставляя разработчику следующие возможности: Единый способ получения экземпляров объектов. В системе обеспечивается механизм создания объектов без необходимости идентификации определенных типов классов в программном коде. Простота. Некоторые из шаблонов упрощают процесс создания объектов до такой степени, что полностью избавляют разработчика от необходимости написания большого и сложного программного кода для получения экземпляра объекта. 20 Учет ограничений при создании. Некоторые шаблоны позволяют при создании объектов налагать ограничения на их тип или количество в соответствии с установленными требованиями системы. Основные производящие шаблоны проектирования. Abstract Factory. Обеспечивает создание семейств взаимосвязанных или зависящих друг от друга объектов без указания их конкретных классов. Builder. Упрощает создание сложных объектов путем определения класса, предназначенного для построения экземпляров другого класса. Шаблон Builder генерирует только одну сущность. Хотя эта сущность в свою очередь может содержать более одного класса, но один из полученных классов всегда является главным. Factory Method. Определяет стандартный метод создания объекта, не связанный с вызовом конструктора, оставляя решение о том, какой именно объект создавать, за подклассами. Prototype. Облегчает динамическое создание путем определения классов, объекты которых могут создавать собственные дубликаты. Singleton. Обеспечивает наличие в системе только одного экземпляра заданного класса, позволяя другим классам получать доступ к этому экземпляру. Два из перечисленных выше шаблона, а именно Abstract Factory и Factory Method, базируются исключительно на концепции определения создания настраиваемых объектов. Подразумевается, что разработчик, применяющий эти шаблоны, при реализации системы обеспечит механизм расширения создаваемых классов или интерфейсов. В силу этой особенности данные шаблоны часто объединяются с другими производящими шаблонами. Поведенческие шаблоны Поведенческие шаблоны (behavioral patterns) применяются для передачи управления в системе. Существуют методы организации управления, применение которых позволяет добиться значительного повышения как эффективности системы, так и удобства ее эксплуатации. Поведенческие шаблоны представляют собой проверенные на практике методы и обеспечивают понятные и простые в применении эвристические способы организации управления. В данной главе рассматриваются следующие поведенческие шаблоны. Chain of Responsibility. Предназначен для организации в системе уровней ответственности. Использование этого шаблона позволяет установить, должно ли сообщение обрабатываться на том уровне, где оно было получено, или же оно должно передаваться для обработки другому объекту. Command. Обеспечивает обработку команды в виде объекта, что позволяет сохранять ее, передавать в качестве параметра методам, а также возвращать ее в виде результата, как и любой другой объект. Interpreter. Определяет интерпретатор некоторого языка. Iterator. Предоставляет единый метод последовательного доступа к элементам коллекции, не зависящий от самой коллекции и никак с ней не связанный. 21 Mediator. Предназначен для упрощения взаимодействия объектов системы путем создания специального объекта, который управляет распределением сообщений между остальными объектами. Memento. Сохраняет "моментальный список" состояния объекта, позволяющий такому объекту вернуться к исходному состоянию, не раскрывая своего содержимого внешнему миру. Observer. Предоставляет компоненту возможность гибкой рассылки сообщений интересующим его получателям. State. Обеспечивает изменение поведения объекта во время выполнения программы. Strategy. Предназначен для определения группы классов, которые представляют собой набор возможных вариантов поведения. Это дает возможность гибко подключать те или иные наборы вариантов поведения во время работы приложения, меняя его функциональность "на ходу". Visitor. Обеспечивает простой и удобный в эксплуатации способ выполнения тех или иных операций для определенного семейства классов. Это достигается путем централизации с помощью данного шаблона возможных вариантов поведения, что позволяет модифицировать или расширять их, не затрагивая классы, на которые распространяются эти варианты поведения. Template Method. Предоставляет метод, который позволяет подклассам перекрывать части метода, не прибегая к их переписыванию. Структурные шаблоны Структурные шаблоны (structural patterns) с одинаковой эффективностью применяются как для разделения, так и для объединения элементов приложения. Способы воздействия структурных шаблонов на приложение могут быть самые разные. Например, шаблон Adapter может обеспечить возможность двум несовместимым системам обмениваться информацией, тогда как шаблон Facade позволяет отобразить упрощенный пользовательский интерфейс, не удаляя ненужных конкретному пользователю элементов управления. Структурные шаблоны, рассмотренные в данной главе, имеют следующее назначение. Adapter. Обеспечение взаимодействия двух классов путем преобразования интерфейса одного из них таким образом, чтобы им мог пользоваться другой класс. Bridge. Разделение сложного компонента на две независимые, но взаимосвязанные иерархические структуры: функциональную абстракцию и внутреннюю реализацию. Это облегчает изменение любого аспекта компонента. Composite. Предоставление гибкого механизма для создания иерархических древовидных структур произвольной сложности, элементы которых могут свободно взаимодействовать с единым интерфейсом. 22 Decorator. Предоставление механизма для добавления или удаления функциональности компонентов без изменения их внешнего представления или функций. Facade. Создание упрощенного интерфейса для группы подсистем или сложной подсистемы. Flyweight. Уменьшение количества объектов системы с многочисленными низкоуровневыми особенностями путем совместного использования подобных объектов. Half-Object Plus Protocol (HOPP). Предоставление единой сущности, которая размещается в двух или более областях адресного пространства. Proxy. Представление другого объекта, обусловленное необходимостью обеспечения доступа или повышения скорости либо соображениями безопасности 23 Источники 1. Грекул – Проектирование ИС Лекция 2. 2. Стелтинг, Маассен – Шаблоны проектирования в Java (16-19) Производящие шаблоны (стр.25-26) Прототип (стр. 48-51) Поведенческие шаблоны (стр. 61-62) Итератор (стр. 88-90) Наблюдатель (стр. 111-113) Структурные шаблоны (стр. 155) Фасад (стр. 189-191) 24 Приложение 1 Абстрактная фабрика Порождающий шаблон проектирования, позволяющий изменять поведение системы, варьируя создаваемые объекты, при этом сохраняя интерфейсы. Предоставляет интерфейс для создания семейств взаимосвязанных или взаимозависимых объектов, не специфицируя их конкретных классов. Плюсы: изолирует конкретные классы упрощает замену семейств продуктов гарантирует сочетаемость продуктов Минусы: сложно добавить поддержку нового вида продуктов. Синглтон Объект-одиночка Гарантирует, что у класса есть только один экземпляр, и предоставляет к нему глобальную точку доступа. 25 Плюсы: контролируемый доступ к единственному экземпляру уменьшение числа имѐн допускает уточнение операций и представления допускает переменное число экземпляров бо льшая гибкость, чем у операций класса Минусы: Глобальные объекты могут быть вредны для объектного программирования, в некоторых случаях приводя к созданию немасштабируемого проекта. Усложняет написание модульных тестов Наблюдатель Поведенческий шаблон. Определяет зависимость типа «один ко многим» между объектами таким образом, что при изменении состояния одного объекта все зависящие от него оповещаются об этом событии. Пример кода в отдельном файле observer.py Адаптер Структурный шаблон, предназначенный для организации использования функций объекта, недоступного для модификации, через специально созданный интерфейс. Задача: Система поддерживает требуемые данные и поведение, но имеет неподходящий 26 интерфейс. Решение:Адаптер предусматривает создание класса-оболочки с требуемым интерфейсом class Adaptee: def specific_request(self): return 'Adaptee' class Adapter: def __init__(self, adaptee): self.adaptee = adaptee def request(self): return self.adaptee.specific_request() client = Adapter(Adaptee()) print client.request() Мост Структурный шаблон, предназначенный для того, чтобы «разделять абстракцию и реализацию так, чтобы они могли изменяться независимо». 27 Пример в отдельном файле bridge.py. 28 Приложение 2 Сложность алгоритмов Понятие сложности алгоритма входит в теорию алгортмов, которая изучает общие свойства и закономерности алгоритмов, а также разнообразные модели их представления. Задачи теории алгоритмов: Асимптотический анализ сложности алгоритмов Доказательство асимптотической неразрешимости алгоритмов Классификация алгоритмов в соответствиии с классами сложности Понятие сложности также является одним из основных объектов изучения в теории сложности вычислений, изучающей стоимость работы, требуемой для решения вычислительной проблемы. Стоимость обычно измеряется такими абстрактными понятиями, как время и пространство, называемыми вычислительными ресурсами. Время – количество элементарных шагов, необходимых для решения задачи. Время является основным параметром, характеризующим быстродействие алгоритма. Оно также называется вычислительной сложностью. Обычно учитывается худшее, среднее и лучшее время алгоритма. Количество элементарных операций, затраченных алгоритмом для решения конкретного экземпляра задачи, зависит не только от размера входных данных, но и от самих данных. Например, количество операций алгоритма сортировки вставками значительно меньше в случае, если входные данные уже отсортированы. Чтобы избежать подобных трудностей, рассматривают понятие временной сложности алгоритма в худшем случае. Временная сложность алгоритма (в худшем случае) — это функция размера входных и выходных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера (верхний предел). Располагая этим значением, мы точно знаем, что для выполнения алгоритма не потребуется большее количество времени. В задачах, где размер выхода не превосходит или пропорционален размеру входа, можно рассматривать временную сложность как функцию размера только входных данных. Пример: Поиск информации по БД-> наихудший случай будет тогда, когда информация в БД отсутствует. Аналогично понятию временной сложности в худшем случае определяется понятие временная сложность алгоритма в наилучшем случае. Также рассматривают понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста). Пространство – объем памяти или места на носителе данных. По аналогии с временной сложностью, определяют пространственную сложность алгоритма, только здесь говорят не о количестве элементарных операций, а об объѐме используемой памяти. 29 При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы. Асимптотические обозначения Обозначе ние Интуитивное объяснение Определение f ограничена сверху функциейg (с точностью до постоянного множителя) асимптотически асимптотическая верхняя граница или f ограничена снизу функцией g(с точностью до постоянного множителя) асимптотически асимптотическая нижняя граница f ограничена снизу и сверху функцией g асимптоти чески асимптотические верхняя и нижняя границы g доминирует над fасимптотически f доминирует над gасимптотически f эквивалентна gас имптотически 30 Примеры «пропылесосить ковер» требует время, линейно зависящее от его площади (Θ(A)), то есть на ковер, площадь которого больше в два раза, уйдет в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз, объем работы увеличивается строго пропорционально в сто тысяч раз, и т. п. «найти имя в телефонной книге» требует всего лишь время, логарифмически зависящее от количества записей (O(log2(n))), так как открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге, толщиной в 1000 страниц, любое имя находится не больше чем за раз (открываний книги). Примеры сложностей алгоритмов Название Сложность Пример Пример алгоритмов Константное время O(1) 10 Определение четности числа Взятие элемента массива/хэш Логарифмическое время O(log n) Log n, log n^2 Бинарный поиск Линейное время O(n) N Поиск наименьшего значение в неотсортированном массиве Linearithmic time O(nlogn) Наиболее быстрый сортировки сравнением(quicksort и др) Квадратичное время O(n^2) n^2 Сортировка пузырьком, сортировка вставками Кубическое время O(n^3) n^3 Перемножение матриц nxn (без спец. алгоритмов) Экспоненциальное время 2^O(n) 1.1^n, 10^n Решение задачи о коммивояжере, динамическое программирование 31 Сортировка пузырьком. Временная сложность O(n^2): def swap(arr, i, j): arr[i], arr[j] = arr[j], arr[i] def bubble_sort(arr): i = len(arr) while i > 1: for j in xrange(i - 1): if arr[j] > arr[j + 1]: swap(arr, j, j + 1) i -= 1 Сортировка слияниями Временная сложность O(n log n): def mergesort(w): """Sort list w and return it.""" if len(w)<2: return w else: mid=len(w)//2 # sort the two halves of list w recursively with mergesort and merge them return merge(mergesort(w[:mid]), mergesort(w[mid:])) def merge(u, v): """Merge two sorted lists u and v together. Return the merged list r.""" r=[] while u and v: # pop the smaller element from the front of u or v and append it to list r r.append( u.pop(0) if u[0] < v[0] else v.pop(0) ) # extend result with the remaining end r.extend(u or v) return r 32 Выше приведено сравнение времени работы алгоритмов при сортировки 50, 500 и 5000 элементов (целочисленных) соответственно. Код программы в отдельном файле bubble.py. |