patrones de diseño - integrated systems laboratorycarreras/isse/patrones_diseno.x2.pdf · page 2 3...
TRANSCRIPT
Page 1
1
Patrones de Diseño
Departamento de Ingeniería ElectrónicaUniversidad Politécnica de Madrid
Ingeniería Software para Sistemas Empotrados
Carlos Carreras
2
Contenidos
Definición de patrones y frameworksCategorías de patrones de diseñoPrincipios de diseño. El principio Abierto/CerradoUso de patrones de diseño y de frameworksCaso de estudio 1: sort del sistemaCaso de estudio 2: verificador de sort
Agradecimientos: Douglas C. Schmidt (Vanderbilt University)
Page 2
3
Contenidos
Definición de patrones y frameworksCategorías de patrones de diseñoPrincipios de diseño. El principio Abierto/CerradoUso de patrones de diseño y de frameworksCaso de estudio 1: sort del sistemaCaso de estudio 2: verificador de sort
4
Patrones y frameworks
Patrones y frameworks mejoran la calidad del software y reducen el tiempo de diseño (reutilización, ampliación, modularidad, prestaciones)
Patrones: reutilización de la arquitectura y diseño softwareCapturan las estructuras y los modos de colaboración en soluciones a problemas en un dominio particular
Frameworks: reutilización del diseño detallado y el códigoConjunto integrado de componentes que colaboran dentro de una arquitectura reutilizable en una familia de aplicaciones
Page 3
5
Patrones de diseño
Representan soluciones a problemas que surgen al desarrollar software en un cierto contexto
“Patrón = par (problema, solución) en un contexto”
Capturan la estructura estática y dinámica y la colaboración entre los participantes clave en diseñossoftware
Facilitan la reutilización de arquitecturas software y diseños satisfactorios
6
Notación gráfica
Page 4
7
Ejemplo: servicio de cotización de acciones en bolsa (1/3)
Aspectos clave:1. Puede haber muchos observadores2. Cada observador puede reaccionar
de un modo distinto a la mismanotificación
3. El sujeto de observación deberíaestar desacoplado todo lo posiblede los observadores (p.e.: que éstospuedan cambiar de sujetoindependientemente)
8
Ejemplo: servicio de cotización de acciones en bolsa (2/3)
El patrón Observer:“Define una dependenciade muchos respecto a uno, de manera que cuando un objeto cambie de estado, todos lo que dependen de él sean notificados y actualizadosautomáticamente”
Page 5
9
Ejemplo: servicio de cotización de acciones en bolsa (3/3)
Subject mantiene unarelación de todos losObservers dados de altaColaboraciones:
Observer1 provoca un cambioen Subject con set_state()Subject llama a notify() queactualiza los Observers con update() (incluido Observer1)Los Observers obtienen másdatos con get_state()
10
Descripción de patrones de diseño
Nombre e intento (breve descripción)Problema y contexto (motivación)Fuerzas o aspectos abordados (aplicabilidad)Estructura y colaboraciones (incluye participantes)Consecuencias del uso (positivas y negativas)Implementación (directrices y código ejemplo)Usos conocidos (ejemplos en aplicaciones y SOs)Patrones relacionados (colaboración con otros patrones)
Page 6
11
Frameworks
Son aplicaciones semi-completasLa aplicaciones completas instancian o heredan de componentesparametrizados del framework
Proporcionan funcionalidad específica a un dominioP.e. negocios, telecomunicaciones, sistemas de ventanas, bases de datos, aplicaciones distribuidas, kernels de SO
Exhiben inversión del control en tiempo de ejecuciónP.e. el framework determina qué objetos y métodos hay queinvocar en respuesta a ciertos eventos
12
Librerías de clases, frameworks y patrones de diseño
Librerías de clases: autocontenidas, ADTs “conectables”Frameworks: reutilizables, aplicaciones semi-completasPatrones de diseño: par(problema, solución) en un contexto
Page 7
13
Integración de componentes en frameworks
Acoplamiento débil mediante callbacksPermiten conectar componentes SW desarrollados independientementeLa aplicación registra servicios en el framework (p.e. función foo() para atendereventos en el puerto N), y es el frameworkel que llama a la aplicación (callback)El framework proporciona la parte comúnparametrizable y la aplicación los“enganches” para las variantes específicas
14
Patrones de diseño y frameworks
Comparación:Ambos participan en la funcionalidad sin estarsubordinado el uno al otroLos patrones son másabstractosLos frameworks estánimplementados en un lenguaje concreto
Page 8
15
Contenidos
Definición de patrones y frameworksCategorías de patrones de diseñoPrincipios de diseño. El principio Abierto/CerradoUso de patrones de diseño y de frameworksCaso de estudio 1: sort del sistemaCaso de estudio 2: verificador de sort
16
Categorías de patrones de diseño
Patrones de creaciónTienen que ver con la creación, inicialización y configuración de clases y objetos
Patrones estructuralesTienen que ver con el desacoplo entre la interfaz y la implementación de clases y objetos
Patrones de comportamientoTienen que ver con las interacciones dinámicas entre sociedadesde clases y objetos
Page 9
17
Patrones de creación
Factory MethodPermite que sean las clases derivadas las que creen objetos
Abstract FactoryInterfaz para crear familias de objetos sin especificar sus clases
BuilderPermite crear objetos complejos incrementalmente
PrototypePermite clonar instancias a partir de un prototipo
SingletonAsegura que una clase sólo tiene una única instancia
18
Patrones estructurales
AdapterTraductor que adapta la interfaz de un servidor a un cliente
BridgeAbstracción que vincula a una entre muchas implementaciones
CompositeEstructura para construir jerarquías basadas en composición
DecoratorExtender la funcionalidad dinámicamente de modo transparente
FacadeDefinir una interfaz unificada para varios subsistemas
FlyweightCompartición eficiente de muchos objetos de grano fino
ProxyProporciona un sustituto de otro objeto para controlar su acceso
Page 10
19
Patrones de comportamiento (1/2)
Chain of ResponsabilitySolicitud delegada al responsable de proporcionar un servicio
CommandEncapsular una solicitud como un objeto
InterpreterIntérprete y representación de la gramática de un lenguaje
IteratorModo de acceso secuencial a elementos agregados a un objeto
MediatorEncapsular la interacción entre objetos (que no sea explícita)
MementoCapturar el estado interno de un objeto para restaurarlo luego
20
Patrones de comportamiento (2/2)
ObserverLos objetos dependientes se actualizan cuando cambia un sujeto
StateObjeto cuyo comportamiento depende de su estado
StrategyAbstracción para seleccionar un algoritmo entre varios
Template MethodDefinir un algoritmo base diferiendo ciertos pasos a subclases
VisitorAplicar operaciones a elementos de objetos heterogéneos
Page 11
21
¿Cuándo interesan los patrones?
En soluciones a problemas recurrentes con variacionesLa reutilización no es necesaria en problemas únicos
En soluciones que requieren varios pasosNo todos los problemas requieren varios pasos y usar patronespueden ser excesivo si basta con unas pocas instrucciones
En soluciones donde lo importante es saber si hay unasolución, más que todas sus implicaciones
Usando patrones se dejan de lado aspectos que pueden ser útilespara alguien que realmente quiera entenderlo todo
22
¿Qué hace que un patrón sea un patrón de diseño?
Debe resolver un problema, es decir, ser útilDebe tener un contexto, es decir, debe describir dóndepuede usarse la solución que aportaDebe ser recurrente, es decir, debe ser relevante en múltiples situacionesDebe enseñar, es decir, debe aportar una comprensiónsuficiente para alcanzar una soluciónDebe tener un nombre, es decir, se debe poder referenciarconsistentemente
Page 12
23
Ejemplo: framework OO reutilizablepara comunicaciones (1/3)
Motivación:Es difícil desarrollar SW de comunicaciones portable, reutilizable y eficienteLos SO suelen ser incompatibles (modelo de concurrencia o E/S)No es práctico usar algoritmos, interfaces, diseños detallados o implementaciones directamente
Objetivo: framework OO para gestión de un Centro de llamadaswww.cs.wustl.edu/~schmidt/PDF/ECOOP-95.pdfwww.cs.wustl.edu/~schmidt/PDF/DESJ-94.pdf
24
Ejemplo: framework OO reutilizablepara comunicaciones (2/3)
Problema: reutilización en múltiples plataformas
El framework se desarrolló en UNIX y se portó a Windows NT 3.5UNIX y Windows NT tienenmodelos de E/S diferentes(síncrono vs asíncrono)La reutilización directa del framework original no era factibleEl problema se resolvión despuéscon ACE y Windows NT 4.0
Page 13
25
Ejemplo: framework OO reutilizablepara comunicaciones (3/3)
Solución: reutilizar patronesde diseño
Los patrones reutilizan la arquitectura softwareCorresponden a soluciones a problemas en cierto contextoReducen el riesgo del proyectoal aportar una experiencia de probada eficacia
26
El patrón Reactor
Intento:Desacopla demultiplexacióny emisión de eventos del manejo de eventos
Aspectos abordados:Demultiplexación síncronaeficiente de eventos en unahebraAmpliación de aplicacionessin cambiar el demux
http://www.cs.wustl.edu/~schmidt/POSA/
Page 14
27
Colaboraciones en el patrón Reactor
Callbacks:Producen una inversióndel controlSi las callbacks del manejador de eventos(Event_Handler) tienenlarga duración puedendegradar la calidad del servicio
28
Implementación del patrón Reactor
Especialización de la clase ACE_Event_Handler
Page 15
29
Contenidos
Definición de patrones y frameworksCategorías de patrones de diseñoPrincipios de diseño. El principio Abierto/CerradoUso de patrones de diseño y de frameworksCaso de estudio 1: sort del sistemaCaso de estudio 2: verificador de sort
30
Principios clave en el diseño de patrones y frameworks
Separar la interfaz de la implementaciónSegún los objetivos, determinar lo que es común (estable) y lo que varía con la interfaz y con la implementación
Si hay poca variabilidad, es difícil adaptar los componentes del framework a los casos concretosSi hay poco común, es difícil que los usuarios comprendan y confíen en el comportamiento del framework
Permitir la sustitución de implementaciones variables utilizando una interfaz común
En frameworks la distinción entre lo común y lo variable se sueleimplementar mediante template methods y callbacks
Page 16
31
El principio abierto/cerrado(open/closed)
Las dependencias entre componentes deben ir en la dirección de mayor estabilidad
Un componente no debe depender de otro menos estable
El principio abierto/cerrado permite que el componentemás estable sea ampliable
Abierto para ampliación / cerrado para modificación (utilización)Tienen impacto positivo: abstracción, herencia y polimorfismoTienen impacto negativo: datos públicos y globales, identificación de tipos en tiempo de ejecución (RTTI)
32
Violación del principioabierto/cerrado
Page 17
33
Aplicación del principioabierto/cerrado
34
Contenidos
Definición de patrones y frameworksCategorías de patrones de diseñoPrincipios de diseño. El principio Abierto/CerradoUso de patrones de diseño y de frameworksCaso de estudio 1: sort del sistemaCaso de estudio 2: verificador de sort
Page 18
35
Uso de patrones de diseño
Ventajas:Reutilizan (y documentan) arquitecturas softwareCapturan y hacen accesible el conocimiento experimentado y lospros y los contras (tradeoffs) que aparecen en el diseñoAyudan a mejorar la comunicación entre desarrolladoresFacilitan la transición hacia la tecnología orientada a objetos
Inconvenientes:No llevan a la reutilización directa del códigoLos equipos pueden padecer una sobrecarga de patronesSe validan con la experiencia y no con tests automáticosSu integración en el proceso de desarrollo no es automatizable
36
Uso de frameworks
Ventajas:Facilitan la reutilización directa de códigoLa cantidad de reutilización posible es muy superior a la que se consigue con la definición de funciones globales autónomas(stand-alone) o clases individuales
Inconvenientes:La curva de aprendizaje presenta inicialmente una granpendiente, pues hay muchas clases y niveles de abstracciónEl flujo de control en la emisión reactiva no es intuitivoLa verificación y la validación de componentes genéricos escomplicada
Page 19
37
Diseño de patrones de diseño
No reconvertir todo en patrones, sino que es mejordesarrollar patrones para el dominio y reutilizar patronestácticosInstitucionalizar recompensas por el desarrollo de patronesInvolucrar a los desarrolladores de patrones con losdesarrolladores de aplicaciones y los expertos en dominiosDocumentar claramente la aplicabilidad de los patronesTener mucho cuidado con las espectativas
38
Libros y conferencias sobrepatrones de diseño
Libros:Gamma et al., Design Patterns, Addison-Wesley 1994Pattern Languages of Program Design, Addison-Wesley 1995-99Siemens and Schmidt, Pattern-Oriented Software Architecture, Wiley and Sons, volúmenes 1996 y 2000.http://www.cs.wustl.edu/~schmidt/ACE/book1/ y …/book2/
Conferencias:http://hillside.net/conferences/plop.htm (USA)http://hillside.net/conferences/europlop.htm (Europa)Conferencias Middleware
Page 20
39
Contenidos
Definición de patrones y frameworksCategorías de patrones de diseñoPrincipios de diseño. El principio Abierto/CerradoUso de patrones de diseño y de frameworksCaso de estudio 1: sort del sistemaCaso de estudio 2: verificador de sort
40
Caso de estudio 1: sort del sistema
Objetivo: comando sort que ordene líneas de texto de entrada estándar y escriba el resultado en salida estándar
Comporamiento de sort:Línea = secuencia de caracteres finalizada por “nueva línea”El orden por defecto entre caracteres es el lexicográfico de ASCIIEl orden queda afectado por las siguientes opciones:
No distinguir mayúsculas y minúsculas (-i)Ordenar numéricamente (-n)Usar orden inverso (-r)Empezar a ordenar por un campo específico (-f)Empezar a ordenar por una columna específica (-c)
No hay que considerar ficheros mayores que la memoria
Page 21
41
Aspectos de alto nivel
La solución debe ser eficiente tanto en espacio como en tiempo
Mediante algoritmos y estructuras de datos apropiadasMediante manejo eficiente de E/S y memoriaEvitando en lo posible dynamic binding (reducir coste)
La solución deberá basarse en componentes reutilizablesP.e. iostreams, clase Array, clase Stack
La solución deberá generar componentes reutilizablesP.e. clases de entrada eficientes, rutinas genéricas de ordenación
42
Vista algorítmica de alto nivel y solución general orientada a objetos
¡Evitar el error de usar esta vista para estructurar el diseño!
Solución general orientada a objetos:1. Identificar clases en los espacios de problema y de solución2. Reconocer y aplicar patrones de diseño comunes3. Implementar un framework que coordine los componentes
Page 22
43
Modelo de clases C++
Componentes tácticosStack: para sort rápido no recursivoArray: para almacenar/ordenar punterosa líneas y camposAccess_Table: para almacenar entradaInput: lee entradas de cualquier tamañoeficientemente con sólo una asignacióndinámica de memoria y una copia
Componentes estratégicosSystem_Sort: lo integra todoSort_AT_Adapter: integra Array y Access_TableOptions: maneja las opciones visiblesSort: tanto sort rápido como de inserción
44
Formato detallado de la solución
Page 23
45
La clase Input (1/2)
Problema: leer la entradaeficientemente ya quepuede ser muy grande(hasta la mitad de la memoria)
Solución: crear una claseInput que minimice
La copia y la manipulaciónde datosLa asignación dinámica de memoria
46
La clase Input (2/2)
Page 24
47
Patrones de diseño en sort (1/3)
FacadeDefine una interfaz unificada de alto nivel para varios subsistemasde modo que facilita su usoP.e. la función sort() proporciona una “fachada” para los detallesinternos que implica el ordenar eficientemente
AdapterConvierte la interfaz de una clase en otra que esperan los clientespermitiendo que que ambos tipos de clases trabajen juntasP.e. hacer que Access_Table se adapte a las interfaces queesperan sort e iostreams
48
Patrones de diseño en sort (2/3)
FactoryCentraliza el ensamblado de recursos para crear un objetoP.e. desacoplar la inicialización de los Line_Ptrs utilizados porAccess_Table de su uso posterior
BridgeDesacopla una abstracción de su implementación de modo queambos puedan cambiar independientementeP.e. comparar dos líneas para determinar su orden
StrategyDefine, encapsula y hace intercambiables un grupo de algoritmosP.e. permitir una selección flexible del pivote
Page 25
49
Patrones de diseño en sort (3/3)
SingletonGarantiza que una clase sólo tiene una instancia, proporcionandoun punto de acceso global a ellaP.e. proporciona un único punto de acceso a la fachada del sortdel sistema y a las opciones de programa
Double-Checked Locking OptimizationAsegura accesos atómicos a objetos y evita bloqueos innecesariosP.e. permite que varias hebras ejecuten sort
IteratorAccede secuencialmente a los elementos de un objeto agregadosin describir su representación subyacenteP.e. imprimir las líneas en orden sin exponer su representación
50
El algoritmo sort
Por eficiencia se usan dos algoritmos de ordenación:
1. Sort rápido (quicksort):Muy eficiente en tiempo y espacioComplejidad temporal O(n log n) en promedio y O(n2) en caso peorComplejidad espacial O(log n)Se usan optimizaciones para evitar el caso peor
2. Sort de inserción:Muy eficiente en espacio y tiempo con datos “casi-ordenados”Complejidad temporal O(n2) Complejidad espacial O(1)
Page 26
51
Sort rápido (quicksort)
Algoritmo: selecciona un valor pivote, crea dos particiones(> pivote, < pivote), y repite para ordenar cada partición
Optimizaciones1. No recursivo: usa una pila explícita para reducir el coste de llamar
a funciones2. Selección de pivote mediana de 3: reduce la probabilidad de la
complejidad de caso peor3. Complejidad espacial (log n) garantizada: siempre carga en pila
(push) la partición mayor4. Sort de inserción en particiones pequeñas: es más rápido con
datos “casi-ordenados”
52
Selección del valor pivote
Problema:Hay varios algoritmos que se pueden usar para seleccionar un valor pivote. P.e. selección aleatoria, mediana de 3, etc.
Aspectos a considerar:Según cada entrada la ordenación puede ser más eficienteusando uno u otro algoritmo de selección
Solución:Usar el patrón Strategy para elegir el algoritmo de selección del valor pivote.
Page 27
53
El patrón StrategyIntento:
Definir, encapsular y hacerintercambiables varios algoritmosEl algoritmo puede variar sin afectar a los clientes que lo usan
Aspectos que resuelve:1. Cómo ampliar las políticas de
selección de valor pivote sin modificar el algoritmo quicksort
2. Proporcionar una única interfazpara todos sin forzar una únicaimplementación para todos
54
Uso del patrón Strategy
Page 28
55
Implementación del patrón Strategy
56
Interfaz sencilla de sort
Problema:Aunque la implementación de sort es compleja, la interfaz debeser fácil de usar
Aspectos a considerar:Las interfaces complejas son difíciles de usar, provocan errores y desaniman a la hora de ampliar o reutilizarConceptualmente, al ordenar se hacen ciertas suposiciones sobreel array que se ordena (operador [ ], método size, elemento TYPE)No se quiere limitar los tipos de arrays que se pueden ordenar
Solución:Usar los patrones Facade y Adapter para simplificar la interfaz
Page 29
57
El patrón Facade
Intento:Define una interfaz unificada de alto nivel para varios subsistemas de modo que facilita su uso
Aspectos que resuelve:1. Simplifica la interfaz de sort: sólo hay
que tener operador [ ], size() y TYPE2. Permite una implementación eficiente
y arbitrariamente compleja sin afectara los clientes
58
Uso del patrón Facade
Page 30
59
El patrón AdapterIntento:
Convierte la interfaz de una clase en otra que esperan los clientespermitiendo que que ambos tipos de clases trabajen juntas
Aspectos que resuelve:1. Integra Access_Table con la rutina sort de modo transparente2. Integra Access_Table con operadores iostream transparentemente
60
Uso del patrón Adapter
Page 31
61
La clase Array
La clase Array define un array de tamaño variable para ser usado por Access_Table
62
La clase Access_TableAsigna índices a elementos del búfer de datos
Page 32
63
La clase Sort_AT_AdapterAdapta Access_Table a la interfaz ARRAY que espera sort
64
Centralización del procesamiento de opciones
Problema:Las opciones de la línea de comandos deben ser globales paramuchas partes del programa sort
Aspectos a considerar:El uso ilimitado de variables globales incrementa el acoplamientoen el sistema y puede violar el encapsulamientoInicializar objetos estáticos en C++ puede ser problemático
Solución:Usar el patrón Singleton para centralizar el procesamiento de opciones
Page 33
65
El patrón SingletonIntento:
Garantiza que una clase sólo tieneuna instancia, proporcionando un punto de acceso global a ella
Aspectos que resuelve:1. Localiza la creación y uso de variables
“globales” en objetos bien definidos2. Preserva el encapsulado3. Asegura que se inicializa cuando el
programa ha empezado y sólo una vez4. Permite subclases transparentes de la
implementación de Singleton
66
Uso del patrón Singleton
Page 34
67
La clase Options para el manejoglobal de opciones
68
Uso de la clase Options
Operador de comparación usado por sort
Page 35
69
Evitar carreras al inicializarSingletons
Problema:Un programa multi-hebra puede ejecutar varias copias de sort en hebras diferentes
Aspectos a considerar:En ciertas condiciones sutiles las carreras en la inicializaciónpueden crear varias copias de SingletonBloquear cada acceso a un Singleton puede ser muy costoso
Solución:Usar el patrón Double-Checked Locking Optimization para evitarcarreras al inicializar Singletons
70
El patrón Double-Checked Locking Optimization
Intento:Asegura accesos atómicos a objetosy evita bloqueos innecesarios
Aspectos que resuelve:1. Asegura accesos e inicializaciones
atómicas, sin importar el orden de planificación de las hebras
2. Mantiene el número de bloqueos al mínimo (sólo bloquea en el primer acceso, y no durante todo el métodoinstance() de Singleton)
Page 36
71
Uso del patrón Double-Checked Locking Optimization
Usa el patrón Adapter para convertir clases normales en Singletons que optimiza automáticamente
72
Simplificación de comparaciones
Problema:El operador de comparación que se ha presentado es bastantecomplejo
Aspectos a considerar:Es mejor determinar el tipo de operación de comparación durantela fase de inicialización (no cada vez que se compara)Pero la interfaz no debería cambiar
Solución:Usar el patrón Bridge para separar la interfaz de la implementación
Page 37
73
El patrón BridgeIntento:
Desacopla una abstracción de suimplementación de modo queambos puedan cambiarindependientemente
Aspectos que resuelve:1. Proporciona una interfaz estable y
uniforme, cerrada al no permitircambios directos del código, peroabierta al permitir la ampliación
2. Simplifica la implementación de Line_Ptrs::operator<
74
Uso del patrón Bridge (1/2)
Page 38
75
Uso del patrón Bridge (2/2)
Operador de comparación usado por sort:
Es una solución mucho más concisaSin embargo, se ha añadido un nivel más de indirecciónque es equivalente a una llamada a función virtual
76
Inicialización del patrón de comparación
Problema:Cómo asignar el puntero a función compare:
Aspectos a considerar:Hay muchas posibilidades para compare dependiendo de lasopciones que se hayan habilitadoAhora sólo interesa la inicialización, cuyos detalles puedencambiar en el tiempoInteresa adelantar la mayor cantidad de trabajo posible
Solución:Usar el patrón Factory para inicializar el operador de comparación
Page 39
77
El patrón FactoryIntento:
Centraliza el ensamblado de recursos para crear un objeto
Aspectos que resuelve:1. Desacopla la inicialización del
operador compare de su posterior utilización
2. Facilita el cambio posterior de política de comparación (p.e. añadiendo nuevas opciones a la línea de comandos)
78
Uso del patrón Factory paracomparaciones (1/2)
Page 40
79
Uso del patrón Factory paracomparaciones (2/2)
Esta inicialización se hace después de leer las opciones
80
Inicialización de Access_Table
Problema:Cómo inicializar Access_Table
Aspectos a considerar:Los detalles de la inicialización no deben afectar el procesamientoposteriorInteresa facilitar el cambio posterior de políticas de inicialización(p.e. al usar Access_Table en otras aplicaciones)
Solución:Usar el patrón Factory Method para inicializar Access_Table
Page 41
81
El patrón Factory MethodIntento:
Define una interfaz para crearun objeto pero las subclasesdeciden qué clase instanciar
Aspectos que resuelve:1. Desacopla la inicialización
de Access_Table de su uso2. Mejores prestaciones: carga
el principio de campo y línea3. Facilita el cambio posterior
de política de inicialización(p.e. nuevas opciones)
82
Uso del patrón Factory Method parainicialización de Access_Table (1/2)
El siguiente Adapter de iostreaminicializa Sort_AT_Adapter
Page 42
83
Uso del patrón Factory Method parainicialización de Access_Table (2/2)
La clase Access_Table_Factory tiene un Factory Methodque inicializa Sort_TA_Adapter
84
Inicializar de Access_Table con búfer de entrada
Problema:Inicializar Access_Table sin necesidad de saber cómo se representa el búfer de entrada
Aspectos a considerar:Los detalles de la representación se suelen poder desacoplar del acceso a cada elemento en un contenedor o una colección
Solución:Usar el patrón Iterator para recorrer el búfer
Page 43
85
El patrón Iterator
Intento:Accede secuencialmente a los elementos de un objeto agregadosin describir su representación subyacente
Aspectos que resuelve:Inicialización de Access_Table sin saber cómo se representa el búfer de entrada
Notar que la STL (Standard Template Library) se basaampliamente en el uso deIterators
86
Uso del patrón Iterator
Iterator permite imprimir las líneas sin exponer su representación
Page 44
87
Resumen del caso de estudio del sort del sistema
Este caso ilustra el uso de técnicas OO para estructurar un sistema modular, reutilizable y altamente eficiente
Los patrones de diseño ayudan a resolver muchos de losaspectos a considerar
Las prestaciones del sort del sistema diseñado son comparables a las del comando UNIX existente
El uso de facilidades de C++, como los tipos parametrizados e inlining, minimiza la penalización por una mayor modularidad, abstracción y ampliación
88
Contenidos
Definición de patrones y frameworksCategorías de patrones de diseñoPrincipios de diseño. El principio Abierto/CerradoUso de patrones de diseño y de frameworksCaso de estudio 1: sort del sistemaCaso de estudio 2: verificador de sort
Page 45
89
Caso de estudio 2: verificador de sort
Objetivo: verificar si el funcionamiento de una rutina sortes correcto
P.e. la salida de sort debe ser una permutación ordenada de la entrada original
Útil para verificar el sort del sistema del caso de estudio 1La solución es más compleja de lo que parece a primera vista…
Método: al igual que en el caso de estudio 1, se analizanlos aspectos clave y se discuten los patrones de diseñoque los resuelven
90
Forma general de la solución
Page 46
91
Problemas habituales
La rutina sort puede no devolver datos (… que pareceríanestar ordenados…)La rutina sort puede fallar al ordenarLa rutina sort puede añadir nuevos valores erróneamente
92
Aspectos clave (1/2)
La solución debe ser eficiente en espacio y en tiempoP.e. ¡no debe tardarse más en verificar que en ordenar!La rutina puede ejecutarse muchas veces consecutivamente, lo que puede facilitar ciertas optimizaciones en cuanto a espacio
No se puede suponer la existencia de un algoritmo de ordenación “correcto”…
Por tanto, mejorar las posibilidades de que la solución propuestasea correcta debe ser más sencillo que escribir una rutina de ordenación correctaQuis costodiet ipsos custodes? (¿quién vigila a los guardianes?)
Page 47
93
Aspectos clave (2/2)
Serán necesarias múltiples implementaciones, según laspropiedades de los datos que se estén examinando. P.e.:
Si los datos son enteros y pequeños es relación con su cantidadSi los datos no están duplicadosSi los datos están duplicados
Este problema ilustra un caso sencillo de “familias de programas”
P.e. interesa reutilizar todo el código que sea posible y/o diseñarcon mútiples soluciones si es posible
94
Estrategias de búsqueda
Las implementaciones de la estructura de búsquedavarían según los datos. P.e.:
1. Vector de rango (range vector)Complejidad temporal O(n) y eficiente en espacio para ordenar“pequeños” rangos de valores enteros
2. Búsqueda binaria (versión 1)Complejidad temporal O(n log n) y eficiente en espacio, pero no manejaduplicados
3. Búsqueda binaria (versión 2)Complejidad temporal O(n log n) y maneja duplicados
4. HashingComplejidad O(n) en casos promedio y mejor, pero O(n2) en el caso peor, maneja duplicados pero no es tan eficiente en espacio
Page 48
95
Método OO de resolución general
1. Identificar clases en los espacios problema y soluciónP.e. usar una organización de ADTs para la estructura de búsquedacon funciones miembro como insert y remove
2. Reconocer y aplicar patrones de diseño habitualesPatrones Strategy y Factory Method (+ Facade, Iterator y Singleton)
3. Hacer un framework que coordine las implementacionesP.e.: usando clases, herencia, tipos parametrizados, …
El framework C++ debe permitirAmpliación/reducción (mejoras, restricciones, varios tipos de datos)Mejora de prestaciones (mejoras “transparentes”)Portabilidad (mútiples plataformas)
96
Algoritmo de alto nivel(pseudo-código)
Page 49
97
Diagrama de clases UML para la solución en C++
98
Interfaces de clases C++ (1/2)
Clase de la Strategy Factory
Clase base de la estructura de búsqueda
Page 50
99
Interfaces de clases C++ (2/2)Subclases de Strategy
100
El patrón Strategy (de nuevo)Intento:
Definir, encapsular y hacerintercambiables varios algoritmosEl algoritmo puede variar sin afectar a los clientes que lo usan
Aspecto que resuelve:1. Amplía las estrategias para
verificar si un array está ordenadosin modificar el algoritmocheck_sort
Page 51
101
Uso del patrón Strategy
102
El patrón Factory Method (de nuevo)
Intento:Define una interfaz para crearun objeto pero las subclasesdeciden qué clase instanciar
Aspecto que resuelve:1. Cómo ampliar la estrategia
de inicialización en el verificador de sorttransparentemente
Page 52
103
Uso del patrón Factory Method
104
Código para la estrategia de verificación (función check_sort)
Page 53
105
Inicialización de la estructura de búsqueda (Factory Method)
106
Especialización de la estructura de búsqueda para vectores de rango
Page 54
107
Resumen del caso de estudio del verificador de sort
De nuevo, este caso ilustra el uso de técnicas OO paraestructurar un sistema modular, reutilizable y altamenteeficiente
Se simplifica el algoritmo principal de procesamientoLa complejidad se lleva a los objetos estrategia y a la Factory de selección de estrategiaAñadir nuevas soluciones no afecta al código existenteEl ADT de la estructura de búsqueda apropiada se selecciona en tiempo de ejecución a partir del patrón Strategy