22 de janeiro de 2017


Assunto abordado por Meyer (1997), um objeto pode assumir diferentes estados ao longo da execução de um código. Esses estados podem ser alterados em vários momentos de acordo com as funções que tratam esse objeto. A implementação de objetos como máquinas de estado, auxilia na redução dos custos de vários tipos de operações que equivale a economia de tempo de execução e melhora o desempenho de aplicativos.

Veja essa implementação de uma lista e suas operações alterar, pesquisar, inserir e apagar itens da lista onde a noção de efeito colateral restrito ao estado concreto não é usado:

// Lista
class IntList {
private static class Node {...}
private Node firstElement;
private int nElements;
public IntList( ) { }

//Operações de IntList...
}

// Método para alterar valor de um item da lista com custo O(n)
public void changeValue(int i,int v)throws E1{
Node e; int j;
if (i<1 i="">nElements)
throw new IndexError();
e = getAddress(i);
e.info = v;
}

// Método para pesquisar item na lista com custo O(n)
public int search(int v) {
Node e; int j;
if (empty( )) then return 0;
for (j = 1 , e = firstElement ; j&lt;=nElements; j++,e = e.right) {
if (v == e.value) return j;
}
return 0;
}

// Método para inserir item na lista com custo O(n)
public void insert(int i, int v) throws E1 {
Node previous, node; int j;
if (i<0 i="">nElements)
throw new IndexError();
node = new Node(v);
if (i == 0) {
node.right= firstElement;
firstElement = node;
} else {
previous = getAddress(i);
node.right =previous.right;
previous.right =node;
}
nElements++;
}

// Método para deletar um item da lista com custo O(n)
public void delete(int i) throws IndexError {
Node previous, toBeDeleted;
if (i<1 i="">nElements)
throw new IndexError();
if (i == 1) {
firstElement = firstElement.right;
}
else {
previous = getAddresss(i-1);
toBeDeleted = previous.right;
previous.right = toBeDeleted.right;
}
nb_elements--;
}

// Uso de IntList
class User {
public static void main(String[ ] a) {
LinkedList q;
int k, v1 = 1, v2 = 2, v3 = 3, v4 = 4, int n = 5; ...;
k = q.search(v1);
v4 = q.value(k);
q.insert(n, v2);
q.changeValue(n,v3);
q.delete(n);
................
}
}

A lista apresentada possui as operações básicas para o funcionamento de uma lista, porém, suas operações possuem o custo O(n), pois, em todas as operações a lista é percorrida desde o início. Esse tipo de implementação não poupa tempo de execução. Essa lista poderia ser reimplementada de modo que suas operações tivessem um menor custo. A saída seria implementar essa lista como uma máquina de estados.

Na implementação dessa lista como uma máquina de estados, será utilizada a noção de nodo corrente para que as operações sejam mais eficientes. Essa noção será obtida pela construção do nodo ativo que armazena informações de acordo com as últimas operações realizadas. E todas as operações são definidas em função do nodo corrente.

Nas Figuras 1 e 2, podemos verificar o funcionamento da nova lista de acordo com o estado abstrato, ou seja, o estado percebido pelo usuário e de acordo com o estado concreto, ou seja, o estado definido pela implementação do objeto. Na percepção do usuário, o tempo de execução será melhorado e ele notará um retorno mais rápido durante as execuções. Na demonstração do estado concreto, podemos verificar como funcionarão as operações de acordo coma existência do nodo active.


FIG. 1 Vista do Estado Abstrato do ADT. Fonte: Bigonha.


FIG. 2 Vista do Estado Concreto do ADT. Fonte: Bigonha.


Vejamos a nova implementação da lista:

class IntList {
private static class Node {
int value; Node right;
Node(int value){this.value = value;}
}
private int nElements, position;
private Node firstElement;
private Node previous, active, next;

//Operações de IntList ...
}

// É criado o nodo Ativo para definir o nodo corrente da lista
public void start( ) throws ActiveError {
if (empty( )) throw ActiveError( );
previous = null;
active = firstElement;
next = active.right ;
position = 1;
}

/* Método para alterar valor do nodo corrente da lista com custo O(1) */
public void changeValue( int v)
throws ActiveError {
if (offLeft( ) || offRight( ))
throw new ActiveError( );
active.value = v;
}

// Método para pesquisar item na lista com custo O(n)
public boolean search(int v) {
try {
for (start();!offRight() ; forth())
if (active.value = v) return true;
}
catch(ActiveError e) { }
return false;
}

/* Método para inserir item à direita do nodo corrente da lista com custo O(1) */
public void insertRight(int v)
throws InsertionError {
Node node = new Node(v);
if (empty() ) {
firstElement = node; active = node;
previous = null; next = null; position = 1;
} else {
if (offLeft( ) || offRight( ))
throw new InsertionError( );
node.right = next; active.right = node;
previous = active; active = node;
}
nElements++;
}

// Método para deletar nodo corrente da lista com custo O(1)
public void delete() throws DeletionError {
if (offLeft() || offRight() || empty( ))
throw new DeletionError( );
active = next;
if (active != null) next = ative.right;
if (position == 1) {
firstElement = active;
if (firstElement == null) position = 0;
} else previous.right = active;
nElements--;
}

Note que a função pesquisar produz efeito colateral no objeto no sentido que ela pode alterar o indicador de elemento ativo da lista. Esse efeito está definido na interface do tipo IntList.

// Uso da nova classe
class User {
public static void main(String[ ] a) {
IntList q; boolean b; int v1=1;
int v2=2, v3=3, v4=4, n=5;
b = q.search(v1);
v4 = q.value();
q.go(n);
q.insertRight(v2);
q.changeValue(v3);
q.delete();
}
}

Na nova implementação acima, após ser criado o nodo ativo, as operações passaram a ser realizadas com base nos estados armazenados pelo nodo. Nesse caso, as novas operações, exceto search passaram a ter custo O(1).

É interessante implementar objetos como máquinas de estado uma vez que armazenando os estados, é possível obter melhorias como o acesso mais rápido dos dados em futuras execuções. O uso dessa prática proporciona economia no tempo de execução, ou seja, mais rapidez e eficiência.

Referências:

MEYER, B. Object-Oriented Software Construction. 2. ed. New Jersey: Prentice Hall, 1997.

BIGONHA, R.S.; BIGONHA, M. Programação Modular. Notas de Aula – DCC UFMG. Belo Horizonte: 2015.

0 comentários:

Postar um comentário

Comentários:

Perfil

Formada em Sistemas de Informação e pós-graduada em Engenharia de Software.

Facebook

Views