Boas Práticas, Fundamentos, Técnicas

Design Patterns – Singleton

Olá Pessoal,

No mundo da O.O. uma das  práticas que podemos aplicar em diversos cenários são os Design patterns (ou Padrões de Projeto), que por sinal são modos de resolver problemas recorrentes e que garantem boa reutilização e também expressam de uma forma elegante a resolução de um determinado problema.

Os Design Patterns são classificados em:

  • Padrões de Criação;
  • Padrões  de Estruturas e
  • Padrões de Comportamento.

Cada uma dessas classificações acima englobam diversos tipos de padrões. Nesse post abordaremos o Design Patterns chamado Singleton. Esse Pattern é caracterizado por permitir apenas uma instância de um objeto no sistema e fornecer um ponto de acesso a essa instância, sendo caracterizado como um padrão de criação.

Existem contextos em que poderá haver a necessidade de ter esse tipo de implementação. Por exemplo com classes que possuem dados sobre o sistema, sobre um determinado dispositivo. Imagine que você esta trabalhando em uma aplicação mobile e precisa capturar algum dado do aparelho, ou atualizar determinada informação. Outro exemplo seria configurações de um aplicativo que poderiam ser solicitadas em determinados momentos da execução. Diversos são os cenários que podemos aplicar essa técnica.

O padrão Singleton também é alvo de várias discussões, alguns acham que não há necessidade de utilizar dessa forma, outros preferem combinar padrão Factory, pois poderá limitar a herança e/ou polimorfismo. Enfim, essa é uma discussão para outro momento.

Para transformar uma classe em Singleton existem 3 modificações a serem feitas na classe.

1 – Criar uma instância privada e estática dessa classe;

2 – Criar um método que seja o ponto de acesso ao único objeto criado e

3 – Tornar o construtor padrão privado.

Abaixo temos uma classe chamada Dispositivo bem simples, vamos transformá-la num Singleton. A classe possui dois atributos (Marca e Modelo) e dois métodos chamados Ligar e Desligar além da sobrecarga do método ToString Conforme figura 1.

Singleton1Figura 1 – Classe Comum de Um Dispositivo

Com a nossa classe comum, vamos fazer as três alterações citadas acima para transformá-la num Singleton. As alterações podem ser acompanhadas na figura 2.

Singleton2

Figura 2 – Classe com as alterações necessárias para atender o padrão Singleton.

A partir desse momento, a forma de utilização dessa classe deixa de ser como já conhecemos, não podemos mais instanciar um objeto dessa classe usando o operador new, isso é feito internamente pelo método getInstance que passa a ser o nosso ponto de acesso ao objeto da classe Dispositivo. Na figura 3 podemos ver como deverá ser utilizada.

Singleton3Figura 3 – Exemplo de uso

Essa é a forma que deverá ser utilizada. O método getInstance, verifica se há alguma instância já criada, caso não haja, será criada uma nova instância senão, ele retornará a instância já existente. A Figura 4 mostra o exemplo em funcionamento.

Singleton4

Figura 4 – Exemplo em execução

Bom, essa é uma forma de tratar um tipo de situação num determinado contexto, porém isso exige cuidado na aplicação ou seja, quando aprendemos sobre Design Patterns, costumamos contrair uma doença chamada “Patternite” onde queremos aplicar sempre, seja qual for o pattern. Porém o ideal é deixar que a plicação “peça” o padrão mais adequado, o desenvolvedor perceberá que aquela situação será bem tratada se for aplicado o pattern X.

Quanto ao Singleton, existe um detalhe que será comentado num próximo post, ele não é thread safe, ou seja se mais de uma thread solicitar esse objeto, teremos problemas, e existem formas de contornar essa situação que serão vistas em breve!

Abraço!

Padrão
Fundamentos, Uncategorized

Algoritmos de Ordenação

Irei mostrar alguns dos principais algoritmos de ordenação, veremos como funciona o Bubble Sort, Selection Sort, Quick Sort, Merge Sort e Heap Sort.

Não colocarei códigos aqui, até porque é muito fácil de encontrar, apenas o funcionamento com explicações e demonstrações em vídeos.

P.S.: Alguns vídeos têm sons!

BUBBLE SORT

O bubble sort, ou ordenação por flutuação (literalmente “por bolha”), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

Características :
Algoritmo muito simples;
Lento para ordenar grande número de elementos, mas eficiente com poucos elementos;
O(n2) comparações e trocas;
Adaptativo: O(n) comparações e trocas se o algoritmo estiver parcialmente ordenado.
Pior Caso: O(n2), Caso Médio O(n2) melhor caso O(n).

Animação:

SELECTION SORT

O selection sort (ordenação por seleção) é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.

Pior Caso: O(n2), Caso Médio O(n2) Melhor caso O(n2).

Animação:

QUICK SORT

O Quick Sort é um algoritmo baseado em Divisão e Conquista. Isso significa que ele divide sucessivamente um problema e partes menores . O próximo passo é solucionar recursivamente os sub-problemas, ou seja ordenar os elementos, e só então combinar as soluções menores de forma a obter a solução final.

Complexidade:

Pior Caso:  O(n2), Caso Médio: O(nlogn) e  Melhor caso:O(nlogn).

Animação:

MERGE SORT

Sua idéia básica é muito fácil: criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.

Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:

Dividir: Dividir os dados em subsequências pequenas;

Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;

Combinar: Juntar as duas metades em um único conjunto já classificado.

Complexidade:

Pior Caso:      O(nlogn), Caso Médio: O(nlogn), Melhor caso:O(nlogn).

Animação:

HEAP SORT

• HeapSort também é um método de seleção – ordena através de sucessivas seleções doelemento correto a ser posicionado em um segmento ordenado

• O HeapSort utiliza um heap binário paramanter o próximo elemento a serselecionado – heap binário: árvore binária mantida na forma de vetor – o heap é gerado e mantido no próprio vetor a ser ordenado (no segmento não-ordenado)

Complexidade:

Pior Caso:      O(nlogn), Caso Médio: O(nlogn), Melhor caso:O(nlogn).

Você sabe o que é um Heap? Primeiro vamos entender o que é um Heap.

Heap Binário – Exemplo

• raiz da árvore: primeira posição do vetor

• filhos de um nodo na posição i: posições 2i e 2i + 1

• pai de um nodo na posição i: posição ëi / 2û

Heap Binário Máximo

• Heap Binário tal que um nodo pai tem valor maior ou igual ao valor dos nodos filhos

Funcionamento

1. Transformação do vetor em um heap binário máximo (Construção do Heap)

2. Ordenação – a cada iteração seleciona-se o maior elemento (na raiz do heap) e o adiciona no início de um segmento ordenado – após cada seleção de elemento, o heap deve ser reorganizado para continuar sendo um heap binário máximo.

• Método auxiliar responsável pelo ajuste de um elemento no heap – método ajustaElemento(posição, vetor.lenght)

– realiza trocas no heap para posicionar

corretamente um elemento

• Exemplo: ajustaElemento(1, 7)

Ajuste de Elementos

• Executa até que o elemento seja transferido para uma posição i > ën/2û – após a posição ën/2û , o elemento já é um nodo folha

Etapa de Ordenação

• A cada iteração seleciona o maior elemento do heap (sempre está na primeira posição) e o troca com o elemento no final do segmento não- ordenado

• Após a troca, o novo elemento raiz do heap deve ser ajustado (deve-se chamar ajustaElemento para o nodo raiz)

• O processo termina quando o heap tiver somente 1 elemento (vetor ordenado) Nesse caso, um Heap Máximo.

Referências:

Wikipédia

Vimeo.com

Ordenação de Dados(III)

UFSC-CTC-INE

INE5384 – Estruturas de Dados

Prof. Ronaldo S. Mello

UNICAMP

Abraços!

Padrão