Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Implemente dois programas para checar a unicidade de elementos em um vetor, usando força bruta e usando pré-sorting.

+1 voto
31 visitas
perguntada Mai 16 em Ciência da Computação por Pedro Henrique T (16 pontos)  
Compartilhe

1 Resposta

0 votos
respondida Mai 16 por Pedro Henrique T (16 pontos)  

Para a resolução desta questão os algoritmos foram implementados na linguagem R.

A implementação do método força bruta é simples e baseia-se na comparação de todos com todos. Para cada elemento do vetor, realiza-se a comparação deste com todos os outros a fim de se verificar sua unicidade. O método força bruta é eficaz, mas ineficiente visto que realiza comparações desnecessárias.

Considere o vetor de elementos
\begin{equation}
\boldsymbol{X}'=(8,7,21,15,5,32,23,21,20,37,9,32,24,7,21,37,12,27,13,33)\text{.}
\end{equation}
Perceba que o 3º elemento do vetor não é único, pois é igual ao 8º e 15º. Assim, uma vez verificado que a terceira componente do vetor não é única, as n comparações realizadas tanto para o 8º como para o 15º elemento serão desnecessárias.

A seguir tem-se a implementação do método força bruta:

#Método força bruta
uniqueELEMENTO=function(X){
  eh_unico=0
    for(i in 1:length(X)){
      guarda=0
        for(j in 1:length(X)){
          guarda[j]=(X[i]==X[j])
        }
      eh_unico[i]=(sum(guarda)==1)
    }
  return(eh_unico)
}

X=c(8,7,21,15,5,32,23,21,20,37,9,32,24,7,21,37,12,27,13,33)
resultado=uniqueELEMENTO(X)
resultado
[1] 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 1 1 1

A função retorna um vetor de zeros e uns, que indica se a componente do vetor X é única ou não (quando 1 na i-ésima posição do vetor resultado, significa que o i-ésimo elemento do vetor X é único).

Ao transformar o vetor X através da ordenação a priori dos seus elementos, pode-se implementar um algoritmo alternativo baseado na comparação de cada elemento do vetor com seus vizinhos. Dessa forma, ao invés de realizar todas as comparações possíveis entre os elementos do vetor, para cada componente realiza-se no máximo duas comparações (para o primeiro e para o último basta uma comparação) .

Para a implementação do método transforma e conquista, utilizou-se o algoritmo de ordenação conhecido como Quicksort.

A seguir tem-se a implementação do Quicksort seguida da implementação do método de transformação e conquista:

 ordena=function(x,esq=1,dir=length(x)){
   i=esq
   j=dir

   pivo=x[round((esq+dir)/2)]

   while(i <= j){
     while(x[i]< pivo){
       i=i+1
     }
     while(x[j]> pivo){
       j=j-1
     }
     if(i<=j){
       w=x[i]
       x[i]=x[j]
       x[j]=w
       i=i+1
       j=j-1
     }

   }

    if(esq<j){x=ordena(x,esq,j)}
    if(i<dir){x=ordena(x,i,dir)}

  return(x)

}


#Método transforma e conquista
transforma_uniqueELEMENTO=function(X){
  X=ordena(X)
  eh_unico=0
  for(i in 1:length(X)){

    if(i==1)  eh_unico[i]=(X[i]!=X[i+1])

    else if(i==length(X))   eh_unico[i]=(X[i]!=X[i-1])

    else   eh_unico[i]=(X[i]!=X[i-1]&X[i]!=X[i+1])

  }
  resultado=data.frame(vetor_ordenado=X,eh_unico=eh_unico)

  return(resultado)
}

y=transforma_uniqueELEMENTO(X)
y
   #          vetor_ordenado         eh_unico
# 1               5                   1
# 2               7                   0
# 3               7                   0
# 4               8                   1
# 5               9                   1
# 6              12                   1
# 7              13                   1
# 8              15                   1
# 9              20                   1
# 10             21                   0
# 11             21                   0
# 12             21                   0
# 13             23                   1
# 14             24                   1
# 15             27                   1
# 16             32                   0
# 17             32                   0
# 18             33                   1
# 19             37                   0
# 20             37                   0

Para o método de transformação e conquista, como o vetor X foi ordenado no início, o vetor de zeros e uns resultante informa a unicidade baseando se nos índices do vetor ordenado. Assim, para ter de forma explícita a correspondência entre os indicadores de unicidade e o valor ao qual este indicador se refere, criou-se um data frame.

Um vetor que estabelece uma relação direta do índice gerado pelo método de transformação e conquista com o vetor X sem estar ordenado pode ser calculado da seguinte forma.

reconstroi=double(length(X))
reconstroi[match(y$vetor_ordenado[y$eh_unico==1],X)]=1
reconstroi
#[1] 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 1 1 1

Apesar do problema da computação em valores que sabidamente não são únicos persistir no algoritmo alternativo, tem-se que o número de comparações desnecessárias vai ser bem menor do que o método força bruta. Algumas condições poderiam ser implementadas para evitar estes problemas, mas como a ideia aqui é verificar a vantagem de transformar primeiro para depois verificar unicidade, optei por não colocar essas condições para verificar o ganho "puro" do método alternativo.

Ambos os métodos foram utilizados para verificar a unicidade de 10000 elementos de um determinado vetor. O tempo (em segundos) de processamento do método transforma e conquista foi significativamente menor do que o tempo de processamento do método força bruta.

##TESTE
VEC1=sample(1:10000,10000,replace = T)
 system.time(uniqueELEMENTO(VEC1))
 # usuário   sistema decorrido 
 #  29.59      0.00     29.70 
 system.time(transforma_uniqueELEMENTO(VEC1))
 #usuário   sistema decorrido 
 #    0.12      0.00      0.13 
...