sábado, 5 de fevereiro de 2022

Selenium com Python

Índice



Introdução

Selenium automates browsers. That's it! What you do with that power is entirely up to you. Primarily it is for automating web applications for testing purposes, but is certainly not limited to just that. Boring web-based administration tasks can (and should) also be automated as well.

Essa frase foi retirada diretamente do site oficial do Selenium. Traduzindo, o Selenium começou como um framework para testes funcionais de aplicações web, porém com o passar do tempo foi amplamente utilizado para automatizar tarefas como acessar e coletar informações de páginas web.

Neste artigo, vamos abordar esse aspecto de automação e webscraping em um exemplo prático, onde vamos buscar informações sobre ações no site Fundamentus e montar um arquivo CSV que possa ser importado em qualquer lugar (banco de dados, Google Sheets, etc.)



Arquitetura

Para começar precisamos entender como funciona a arquitetura do selenium que está dividida em três partes.

  • Cliente: é uma biblioteca específica para uma determinada linguagem feita para interagir com o selenium
  • Driver: é o agente que irá permitir a interação entre o cliente e o browser de fato
  • Browser: é o ambiente onde a página será renderizada e executada.







Instalações

Neste exemplo, vamos utilizar a linguagem python, então precisamos baixar duas coisas, a biblioteca oficial do selenium para python e o driver correspondente ao browser que estamos utilizando.

A instalação da biblioteca é bem simples:

pip install selenium

(ou você pode usar o poetry)

A instalação do driver pode ser um pouco complicada pois a versão dele deve ser idêntica a versão do browser instalado na máquina, então para facilitar, é possível utilizar a imagem docker do selenium.

version: '3.8'

services:
    selenium-chrome:
        image: selenium/standalone-chrome:latest
        hostname: selenium-chrome
        networks:
            - selenium-network
        privileged: true
        shm_size: 2g
        ports:
            - "4444:4444"
            - "7900:7900"
        healthcheck:
            test: ["CMD", "curl", "-f", "http://localhost:7900"]
            interval: 10s
            timeout: 10s
            retries: 5
    app:
        build: ./
        volumes:
            - /Users/geraldoferraz/repositorios/blog/selenium-with-python:/tmp/
        networks:
            - selenium-network
        depends_on:
            selenium-chrome:
                condition: service_healthy

networks:
    selenium-network:
      driver:  bridge



Site Fundamentus

Agora que temos tudo que precisamos, vamos analisar a página do Fundamentus e entender onde estão as informações que queremos coletar. Vamos acessar a página de análise da ação da Magazine Luiza (MGLU3). Para isso, acesse este link e você verá uma página semelhante a essa:




Inspect do Chrome

A forma mais fácil de localizar um elemento é utilizando o XPATH. Vamos utilizar a ferramenta de inspeção do browser para recuperar o xpath das informações de “Cotação”, “Min 52 sem”, “Max 52 sem”, “Div. Yield” e a Oscilação “Dia”.

  • Encontre a informação desejada, clique com o botão direito do mouse e selecione a opção “inspect”


  • Na ferramenta de inspeção que se abriu, no item selecionado, clique com o botão direito do mouse e selecione a opção “Copy”→ “Copy full xpath”



Hands-on

Agora que sabemos como chegar no nosso elemento, vamos ver o código necessário para realizar a coleta.

Primeiro, a partir do driver, precisamos construir o objeto que irá representar o browser.

from selenium import webdriver
from selenium.webdriver.chrome.service import Service

def main():
    option = webdriver.ChromeOptions()

    s = Service('/Users/geraldoferraz/Downloads/chromedriver')
    navegador = webdriver.Chrome(service=s, options=option)

    #para trabalhar dentro do docker
    #navegador = webdriver.Remote('http://selenium-chrome:4444/wd/hub', options=option)

if __name__ == '__main__':
    main()

Segundo, precisamos carregar a página desejada e utilizar o XPATH que obtivemos no passo anterior para encontrar as informações que queremos.

navegador.get("<https://fundamentus.com.br/detalhes.php?papel=MGLU3>")

try:
    xpath_valor_atual = '/html/body/div[1]/div[2]/table[1]/tbody/tr[1]/td[4]/span'        
    valor_atual = navegador.find_element(By.XPATH, xpath_valor_atual).text
    print(f'valor atual={valor_atual}')
finally:
    navegador.close()

A lib do selenium possui diversas formas de encontrar elementos na página sendo o XPATH o mais preciso:

  • By.ID
  • By.XPATH
  • By.NAME
  • By.TAG_NAME
  • By.CLASS_NAME
  • By.CSS_SELECTOR

Você deve escolher a melhor forma de acordo com a sua lógica. Para o nosso exemplo, o XPATH será suficiente.

No exemplo a seguir, vamos ver como pegar todas as informações que precisamos de um conjunto de ações:

from selenium import webdriver
from selenium.webdriver.chrome.service import Service
from selenium.webdriver.common.by import By

def main():
    option = webdriver.ChromeOptions()
    s = Service('/Users/geraldoferraz/Downloads/chromedriver')
    navegador = webdriver.Chrome(service=s, options=option)

    #para trabalhar dentro do docker
    #navegador = webdriver.Remote('http://selenium-chrome:4444/wd/hub', options=option)

    acoes = ['MGLU3', 'LREN3', 'BBAS3', 'ITSA4']

    try:
        for acao in acoes:
            navegador.get(f"https://fundamentus.com.br/detalhes.php?papel={acao}")
            xpath_valor_atual = '/html/body/div[1]/div[2]/table[1]/tbody/tr[1]/td[4]/span'
            xpath_min = '/html/body/div[1]/div[2]/table[1]/tbody/tr[3]/td[4]/span'
            xpath_max = '/html/body/div[1]/div[2]/table[1]/tbody/tr[4]/td[4]/span'
            xpath_yield = '/html/body/div[1]/div[2]/table[3]/tbody/tr[9]/td[4]/span'
            xpath_valorizacao = '/html/body/div[1]/div[2]/table[3]/tbody/tr[2]/td[2]/span/font'

            valor_atual = navegador.find_element(By.XPATH, xpath_valor_atual).text
            min = navegador.find_element(By.XPATH, xpath_min).text
            max = navegador.find_element(By.XPATH, xpath_max).text
            _yield = navegador.find_element(By.XPATH, xpath_yield).text
            valorizacao = navegador.find_element(By.XPATH, xpath_valorizacao).text

            print(f'valor atual={valor_atual}, min={min}, max={max}, min={_yield}, min={valorizacao} ')
    finally:
        navegador.close()

if __name__ == '__main__':
    main()

A parte mais simples é gerar o CSV

from selenium import webdriver
from selenium.webdriver.chrome.service import Service
from selenium.webdriver.common.by import By
import csv

def main():
    option = webdriver.ChromeOptions()
    utilize esse formato para trabalhar localmente
    s = Service('/Users/geraldoferraz/Downloads/chromedriver')
    navegador = webdriver.Chrome(service=s, options=option)

    #para trabalhar dentro do docker
    #navegador = webdriver.Remote('http://selenium-chrome:4444/wd/hub', options=option)

    acoes = ['MGLU3', 'LREN3', 'BBAS3', 'ITSA4']

    try:
        with open('acoes.csv', 'w', newline='') as csvfile:
            cabecalho = ['valor_atual', 'min', 'max', 'yield', 'valorizacao']
            writer = csv.DictWriter(csvfile, delimiter=',', fieldnames=cabecalho)
            writer.writeheader()

            for acao in acoes:
                navegador.get(f"https://fundamentus.com.br/detalhes.php?papel={acao}")
                xpath_valor_atual = '/html/body/div[1]/div[2]/table[1]/tbody/tr[1]/td[4]/span'
                xpath_min = '/html/body/div[1]/div[2]/table[1]/tbody/tr[3]/td[4]/span'
                xpath_max = '/html/body/div[1]/div[2]/table[1]/tbody/tr[4]/td[4]/span'
                xpath_yield = '/html/body/div[1]/div[2]/table[3]/tbody/tr[9]/td[4]/span'
                xpath_valorizacao = '/html/body/div[1]/div[2]/table[3]/tbody/tr[2]/td[2]/span/font'

                valor_atual = navegador.find_element(By.XPATH, xpath_valor_atual).text
                min = navegador.find_element(By.XPATH, xpath_min).text
                max = navegador.find_element(By.XPATH, xpath_max).text
                _yield = navegador.find_element(By.XPATH, xpath_yield).text
                valorizacao = navegador.find_element(By.XPATH, xpath_valorizacao).text

                writer.writerow({'valor_atual': valor_atual, 'min': min, 'max': max, 
                'yield': _yield, 'valorizacao': valorizacao})
    finally:
        navegador.close()

if __name__ == '__main__':
    main()



Atenção!

  • Ao executar o programa, você deve ter notado que um browser se abriu. Para o desenvolvimento, pode ser interessante acompanhar visualmente tudo o que está acontecendo, assim podemos pegar alguma falha na nossa lógica, porém em um ambiente de produção, provavelmente não teremos um ambiente visual para que um browser seja aberto, então é interessante adicionar a configuração abaixo na construção do browser.
option.add_argument('headless')
  • Algumas vezes, o site pode ter algum tipo de proteção contra robôs, que podem prejudicar a performance do site, então, precisamos ficar atentos a isso, caso contrário pode ser que o nosso robô não funcione. Não é o escopo desse artigo mostrar como contornar esse cenário, mas saiba que é possível, basta realizar uma pesquisa rápida no google.
  • Para trabalhar dentro do docker, basta descomentar a linha abaixo e executar o docker-compose.yml
navegador = webdriver.Remote('http://selenium-chrome:4444/wd/hub', options=option)



Conclusão

O selenium é uma ferramenta extremamente versátil que permite automatizar diversas tarefas. A criatividade é o limite.

Github do projeto



Referências

segunda-feira, 8 de julho de 2019

Estrutura de Dados - Ordenação Parte 1 - Bubble sort e Quick sort

Ordenação
Hoje em dia temos que lidar com um grande volume de informações e será mais fácil lidar com elas se estiverem ordenadas com base em algum critério.

Imagina uma agenda de contatos onde os nomes são colocados de maneira sequencial, sem nenhum critério de ordenação. Ao buscar um nome específico, será necessário percorrer essa lista inteira até encontrar. No melhor caso o será  o primeiro e o pior caso será o último. Esse processo pode ser demorado caso a quantidade de informações seja muito grande.

A escolha do algoritmo de ordenação ideal é deve levar em consideração uma  série de variáveis como volume de informação, estrutura de dados de armazenamento, etc.

Hoje vamos falar sobre ordenação por troca, isto é, os elementos serão comparados uns aos outros e trocados de acordo com o critério desejado.

Os dois algoritmos mais básicos desse tipo de ordenação são o Bubble Sort e o Quick Sort

Bubble Sort
O algoritmo mais simples e conhecido, de fácil compreensão e implementação. Neste algoritmo, cada elemento será comparado com seu sucessor e trocado caso esteja fora de ordem. Com isso podemos perceber que será necessário várias iterações até que os elementos estejam completamente ordenados.


Apesar de ser simples de implementar, esse algoritmo possui uma ordem de N AO QUADRADO. Isso significa que seu desempenho terá uma curva crescente em função da quantidade de elementos.


Esse algoritmo então, pode não ser a escolha ideal caso tenhamos muitos elementos para ordenar e sim em um conjunto finito e controlado.

public class BubbleSort {

 public static void ordenar(int[] arr) {
  int n = arr.length;
  int temp = 0;
  for (int i = 0; i < n; i++) {
   for (int j = 1; j < (n - i); j++) {
    if (arr[j - 1] > arr[j]) {
     temp = arr[j - 1];
     arr[j - 1] = arr[j];
     arr[j] = temp;
    }

   }
  }
 }

 public static void main(String[] args) {
  int arr[] = { 3, 60, 35, 2, 45, 320, 5 };

  System.out.println("Antes de ordenar");
  imprimir(arr);
  System.out.println();

  ordenar(arr);

  System.out.println("Depois de ordenar");
  imprimir(arr);
 }

 private static void imprimir(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }

}


Quick Sort
Este algoritmos usa a estratégia "Dividir para conquistar". O primeiro passo é escolher um pivô, em seguida, todos os elementos a direita que forem "menores" serão passados para esquerda do pivô e os elementos da esquerda que forme "maiores" serão passados para direita do pivô. No final dessa iteração, o pivô estará exatamente na posição que deveria.
O próximo passo é repetir esse passo para as sublistas a direita e à esquerda do pivô.



public class QuickSort {
 
 public static void ordenar(int arr[], int inicio, int fim) {
  if (inicio < fim) {
         int particao = particionar(arr, inicio, fim);
  
         ordenar(arr, inicio, particao-1);
         ordenar(arr, particao+1, fim);
     }
 }
 
 private static int particionar(int arr[], int inicio, int fim) {
     int pivo = arr[fim];
     int i = (inicio-1);
  
     for (int j = inicio; j < fim; j++) {
         if (arr[j] <= pivo) {
             i++;
  
             int temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
         }
     }
  
     int temp = arr[i+1];
     arr[i+1] = arr[fim];
     arr[fim] = temp;
  
     return i+1;
 }

 
 public static void main(String[] args) {
  int arr[] = { 3, 60, 35, 2, 45, 320, 5 };

  System.out.println("Antes de ordenar");
  imprimir(arr);
  System.out.println();

  ordenar(arr,0,arr.length-1);

  System.out.println("Depois de ordenar");
  imprimir(arr);
 }

 private static void imprimir(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }

}

domingo, 16 de junho de 2019

Estrutura de Dados Parte 5 - Tabela de Espalhamento

Tabela de espalhamento

A tabela de espalhamento ou tabela de hash é uma estrutura que consiste em indexar os elementos armazenados de maneira que seja fácil e rápido encontrar qualquer elemento a partir de sua chave.
Essa estrutura não tem a premissa de armazenar os elementos de maneira sequencial e sim de identificar uma categoria para o elemento e armazená-lo de acordo.

É uma estrutura muito usada tanto na computação quanto no dia a dia.

  1. Agenda telefônica
  2. Corredores de supermercado
  3. Organizar livros em uma biblioteca

O primeiro passo é identificar a qual categoria pertence o elemento que queremos armazenar, para isso temos a "função hash". Esta função é responsável por gerar o índice do elemento. Portanto, essa função deve ser escolhida com cuidado pois caso a função seja mal implementada a tabela terá uma performance ruim.

Vamos pegar um exemplo de uma agenda telefônica.

Para armazenar o nome "Geraldo", executamos a função hash que irá produzir o índice "G".
Já o nome "Nayara" irá produzir o índice "N" e o nome "Fábio" irá produzir o índice "F".

Desta maneira sabemos que os elementos serão armazenados da seguinte maneira:

    

Para recuperar o nome "Fábio" usamos novamente o índice "F" e acessamos o elemento diretamente.

Mesmo que a nossa "função hash" seja muito boa, ainda assim estamos sujeitos a colisões, que é quando dois elementos distintos produzem o mesmo índice. O nome "Francisco" também produz o índice "F" e no exemplo acima ocorreria uma colisão com o nome "Fábio".

Nesse caso precisamos combinar mais de uma estrutura para permitir que os dois elementos possam coexistir.



Podemos combinar as estruturas "tabela de espalhamento" e alguma outra estrutura que melhor encaixe no nosso contexto como Pilhas, Filas e Listas, etc.

public class TabelaEspalhamentoApp {
 
 public static void main(String[] args) {
  TabelaEspalhamento tabela = new TabelaEspalhamento();

  tabela.adiciona("Nayara");
  tabela.adiciona("Geraldo");
  tabela.adiciona("Gorge");
  tabela.adiciona("Fabio");

  System.out.println(tabela.contem("Geraldo"));

  tabela.remove("Gorge");
  System.out.println(tabela.contem("Geraldo"));
  System.out.println(tabela.contem("Gorge"));

 }

}

public class TabelaEspalhamento {

 VetorGenerico vetor = new VetorGenerico();

 public void remove(String elemento) {
  int indice = recuperarIndice(elemento);
  Vetor v = (Vetor) vetor.get(indice);
  if (v != null) {
   int posicao = v.indice(elemento);
   if (posicao >= 0) {
    v.remove(posicao);
   }

  }
 }

 public boolean contem(String elemento) {
  int indice = recuperarIndice(elemento);
  Vetor v = (Vetor) vetor.get(indice);
  if (v != null) {
   return v.has(elemento);
  }
  return false;
 }

 public void adiciona(String elemento) {
  int indice = recuperarIndice(elemento);
  Vetor v = (Vetor) vetor.get(indice);
  if (v == null) {
   v = new Vetor();
  }
  v.add(elemento);
  vetor.add(indice, v);
 }

 private int recuperarIndice(String elemento) {
  return elemento.charAt(0) % 75;
 }

}

public class VetorGenerico{

 Object[] elementos = new Object[1000];
 int indice;

 public void add(Object elemento) {
  elementos[indice] = elemento;
  indice++;
 }

 public Object get(int i) {
  return elementos[i];
 }

 public void add(int posicao, Object elemento) {
  for (int i = indice - 1; i >= posicao; i--) {
   elementos[i + 1] = elementos[i];
  }

  elementos[posicao] = elemento;
  indice++;
 }
 
 public void remove(int posicao) {
  elementos[posicao] = null;

  for (int i = posicao; i + 1 < elementos.length; i++) {
   elementos[i] = elementos[i + 1];
  }

  indice--;
 }
}

Estrutura de Dados - Pesquisa - Sequencial ou Linear, Binária e Interpolação

PESQUISA

Nos dias de hoje, o acesso rápido a informação pode ser determinante para o sucesso do aplicativo. Por isso o algoritmo de pesquisa é tão importante quanto a estrutura de armazenamento e o algoritmo de ordenação.


PESQUISA SEQUENCIAL

Vamos falar do mecanismo de pesquisa mais trivial que existe, a Pesquisa Linear ou Sequencial.

Esse algoritmo consiste em percorrer cada um dos elementos da nossa estrutura até encontrar o elemento desejado. Sua eficiência é inversamente proporcional a quantidade de elementos que tivermos que percorrer. Na melhor hipótese o elemento desejado será o primeiro e na pior hipótese o elemento desejado será o último.

Podemos melhorar significativamente o desempenho se os elementos estiverem ordenados. Por isso é tão importante escolher a estrutura certa assim como aplicar algoritmos de ordenação.

Por exemplo, se queremos encontrar um nome específico na nossa agenda telefônica, será muito mais rápido se a agenda estiver organizada por ordem alfabética. Assim podemos pular alguns nome que temos certeza que não irão atender ao critério de pesquisa.

public class PesquisaLinear {

 public static int pesquisar(String arr[], String argumento) {
  
  for (int i = 0; i < arr.length; i++) {
   if (arr[i] == argumento) {
    return i;
   }
  }

  return -1;
 }

 public static void main(String args[]) {
  String arr[] = { "A", "B", "C", "D" };
  System.out.println(pesquisar(arr, "C"));
 }

}


PESQUISA BINÁRIA

A pesquisa binária utiliza da técnica "dividir para conquisar". Consiste em dividir os elementos ao meio, em seguida é verificado se o elemento desejado é maior ou menor que o elemento central. Caso seja maior, então o elemento desejado obrigatoriamente deve estar do lado direito da divisão e caso seja menor então obrigatoriamente deve estar do lado esquerdo. Esse processo de divisão e verificação é repetido até encontrar o elemento.
Repare para que esse algoritmo funcione, os elementos devem estar obrigatoriamente ordenados, caso contrário pode não funcionar.


public class PesquisaBinaria {

 public static int pesquisar(int arr[], int l, int r, int x) {
  if (r >= l) {
   int mid = l + (r - l) / 2;

   if (arr[mid] == x)
    return mid;

   if (arr[mid] > x)
    return pesquisar(arr, l, mid - 1, x);

   return pesquisar(arr, mid + 1, r, x);
  }

  return -1;
 }

 public static void main(String args[]) {
  int arr[] = { 2, 3, 4, 10, 40 };
  int n = arr.length;
  int x = 10;
  int posicao = pesquisar(arr, 0, n - 1, x);
  if (posicao == -1)
   System.out.println("Elemento não encontrado");
  else
   System.out.println("Elemento encontrado na posição " + posicao);
 }
}


PESQUISA POR INTERPOLAÇÃO

Este algoritmo de pesquisa, assim como a busca binária, tem como premissa que os elementos esteja previamente ordenados, além disso o algoritmo é semelhante a busca binária, eles diferem na forma como os elementos são divididos. Enquanto a busca binária está sempre dividindo ao meio, a busca por interpolação divide os elementos com base na fórmula abaixo:

pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

public class PesquisaInterpolacao {

 public static int pesquisar(int[] arr, int x) {
  int lo = 0, hi = (arr.length - 1);

  while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {

   if (lo == hi) {
    if (arr[lo] == x)
     return lo;
    return -1;
   }

   int pos = lo + (((hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));

   if (arr[pos] == x)
    return pos;

   if (arr[pos] < x)
    lo = pos + 1;

   else
    hi = pos - 1;
  }
  return -1;
 }

 public static void main(String[] args) {
  int x = 18;
  int arr[] = new int[] { 10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47 };
  int posicao = pesquisar(arr, x);

  if (posicao != -1)
   System.out.println("Elemento encontrado na posição " + posicao);
  else
   System.out.println("Elemento não encontrado.");
 }

}

Estrutura de Dados - Ordenação Parte 2 - Selection, Insertion e Shell sort

Selection sort.

O algoritmo consiste em selecionar o menor (ou maior) elemento fora de ordem colocá-lo em sua posição correta. Para fazer isso, primeiro os elementos devem ser divididos em duas partes: os elementos já ordenados e os elementos que ainda não foram ordenados.

Inicialmente a parte ordenada estará vazia, enquanto a parte não ordenada possuirá todos os elementos.

Após a divisão, o algoritmo irá encontrar o menor elemento do lado não ordenado e colocá-lo no lado ordenado. Esse passo irá se repetir até que o lado não ordenado fique vazio.

Este algoritmo possui duas grandes vantagens, primeiro, é um algoritmo simples de ser implementado e segundo, não há consumo de memória além daquele já alocado para os elementos originais, uma vez que a divisão de lado ordenado e lado não ordenado é feita no próprio vetor que queremos ordenar.

A maior desvantagem é que é um algoritmo que não tem um bom desempenho quando temos uma quantidade de elementos muito grande.



public class SelectionSort {

 public static void ordenar(int arr[]) {
  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
   int min = i;
   for (int j = i + 1; j < n; j++)
    if (arr[j] < arr[min])
     min = j;

   int temp = arr[min];
   arr[min] = arr[i];
   arr[i] = temp;
  }
 }

 public static void main(String args[]) {
  int arr[] = { 64, 25, 12, 22, 11 };

  System.out.println("Antes de ordenar");
  imprimir(arr);

  ordenar(arr);

  System.out.println("Depois de ordenar");
  imprimir(arr);
 }

 public static void imprimir(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");
  System.out.println();
 }

}


Insertion sort

O algoritmos consiste inicialmente em selecionar um pivô e comparar os elementos seguintes, um a um. Se o elemento seguinte for maior que o pivô, esse elemento agora passará a ser o novo pivô. Se o elemento for menor que o pivô, os elementos anteriores ao pivô serão percorridos até ser encontrado o elemento maior que o elemento encontrado anteriormente colocando-o logo antes do elemento maior.

Este algoritmo possui uma vantagem: não há consumo de memória além daquele já alocado para os elementos originais, uma que toda a ordenação ocorre dentro dos próprios elementos.

A maior desvantagem é que é um algoritmo que não tem um bom desempenho quando temos uma quantidade de elementos muito grande, assim como o selection sort.



public class InsertionSort {

 public static void sort(int arr[]) {
  int n = arr.length;
  for (int i = 1; i < n; ++i) {
   int k = arr[i];
   int j = i - 1;

   while (j >= 0 && arr[j] > k) {
    arr[j + 1] = arr[j];
    j = j - 1;
   }
   arr[j + 1] = k;
  }
 }

 public static void main(String args[]) {
  int arr[] = { 12, 11, 13, 5, 6 };
  
  System.out.println("Antes de ordenar");
  imprimir(arr);

  sort(arr);

  System.out.println("Depois de ordenar");
  imprimir(arr);
 }

 public static void imprimir(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");

  System.out.println();
 }

}


Shell sort

Este algoritmo consiste em realizar trocas entre os elementos que estão posicionados a uma distância determinada. A distância inicial pode ser definida por d = n /  2 e a cada iteração diminuímos a essa distância, por exemplo, se você tem 10 elementos

iteração 1) d = 10 / 2 = 5;
iteração 2) d =  5 / 2 = 3;
iteração 3) d =  3 / 2 = 2
iteração 4) d =  2 / 2 = 1

Os elementos estarão ordenados quando a distância for menor ou igual a zero.





public class ShellSort {

 public static int ordenar(int arr[]) {
  int n = arr.length;

  for (int gap = n / 2; gap > 0; gap /= 2) {
   for (int i = gap; i < n; i += 1) {
    int temp = arr[i];

    int j;
    for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
     arr[j] = arr[j - gap];

    arr[j] = temp;
   }
  }
  return 0;
 }

 public static void main(String args[]) {
  int arr[] = { 12, 34, 54, 2, 3 };
  
  System.out.println("Antes de ordenar");
  imprimir(arr);

  ordenar(arr);

  System.out.println("Depois de ordenar");
  imprimir(arr);
 }

 public static void imprimir(int arr[]) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");
  System.out.println();
 }
}

sábado, 25 de maio de 2019

Estrutura de Dados Parte 4 - Árvore

Árvores


Árvores são estruturas hierárquicas que permitem fazer associações entre elementos chamados de nós. Esses elementos podem ser pais ou/ou filhos, isso significa que, diferente das listas, os nós não estão dispostos de maneira linear e sim acima ou abaixo uns dos outros. Sempre que um nó possuir filhos teremos uma sub-árvore.

Para entender melhor essa estrutura precisamos primeiro conhecer algumas partes de uma árvore:

Nó raiz: é o primeiro nó da estrutura, é a partir dele que os outros nós irão existir.
Nós filhos: são nós que pertencem ao nó raiz ou a qualquer outro nó.
Grau: o grau de um nó é determinado pela quantidade de filhos que ele possui.
Nível: o nó raiz é considerado o nível zero, a partir dele, cada geração é considerada mais um nível.
Nós folhas: são nós que não possuem filhos.
Profundidade: é o maior nível de uma árvore.

Para serem consideradas árvores essas estruturas podem ter apenas um nó raiz e
os nós podem ter apenas um nó pai.

As árvores podem ser usadas para representar diversas situações:

  1. Estrutura de pastas
  2. Árvore genealógica
  3. Organograma de uma empresa
 



Os tipos de árvores são:

  1. Árvores binárias
  2. Árvores B
  3. Árvores 2-3
Existem outros tipos de árvores mais complexas que não iremos tratar aqui.

Árvores Binárias

São árvores onde os nós obrigatoriamente possuem 0, 1 ou 2 filhos. Os filhos são posicionados sempre na esquerda ou na direita de acordo com o critério de grandeza adotado.


Árvore B

São árvores que possuem uma ordem de grandeza M que define a quantidade de elementos chave que um nó irá possuir.
O nó raiz deverá possuir no mínimo 2 elementos chaves.
Cada nó deverá possuir no máximo M-1 e no mínimo M/2 elementos chave.

Por exemplo, uma árvore B com ordem de grandeza M=5, teria em seu nó raiz no mínimo dois elementos.Cada um desses elementos teria em seu nó filho no máximo 4 e no mínimo 2 elementos, cada elemento possuiria por sua vez um nó filho que seguiria o mesmo raciocínio.



Árvores 2-3

São árvores que permitem mais de um elemento (chave) em um único nó. Nessa estrutura,
se o nó possuir uma única chave, poderá possuir de 0 a 2 nós filhos. Agora se o nó possuir duas chaves, poderá ter de 0 a 3 nós filhos.
Podemos dizer que árvores 2-3 são árvores B com ordem de grandeza M=4




public class Arvore{
 
 public static void main(String[] args) {
  No raiz = new No("Raiz");
  
  No no1 = new No("No 1");
  No no11 = new No("No 1.1");
  No no12 = new No("No 1.2");
  
  no1.add(no11, 1);
  no1.add(no12, 2);
  
  No no2 = new No("No 2");
  No no21 = new No("No 2.1");
  no2.add(no21, 1);
  
  
  No no3 = new No("No 3");
  No no31 = new No("No 3.1");
  No no32 = new No("No 3.2");
  No no33 = new No("No 3.3");
  
  No no331 = new No("No 3.3.1");
  
  no33.add(no331, 1);
  
  no3.add(no31, 1);
  no3.add(no32, 2);
  no3.add(no33, 3);
  
  raiz.add(no1, 1);
  raiz.add(no2, 2);
  raiz.add(no3, 3);
  
  raiz.imprimir();
  
  
  System.out.println("--------");
  
  raiz.remover(2);
  raiz.imprimir();
  
  System.out.println("--------");
  
  no3.imprimir();
 }

}
public class No {

 private No[] filhos = new No[10];
 private String descricao;

 public No(String descricao) {
  this.descricao = descricao;
 }

 public void add(No no, int posicao) {
  filhos[posicao] = no;
 }

 public No[] getFilhos() {
  return filhos;
 }

 public String getDescricao() {
  return descricao;
 }

 public void imprimir() {
  imprimir(0);
 }

 public void remover(int i) {
  filhos[i] = null;
 }


 private void imprimir(int i) {
  System.out.println(tab(i)+descricao);
  i++;
  for (No no : filhos) {
   if (no != null) {
    no.imprimir(i);
   }
  }
  
 }

 private String tab(int i) {
  String retorno = "";
  for (int j = 0; j < i; j++) {
   retorno +="  ";
  }
  return retorno;
 }

}

terça-feira, 7 de maio de 2019

Estrutura de Dados Parte 3 - Lista

Quem diria, não levou 8 anos mas sim 8 dias para continuar a série =D.

A definição de Lista é muito simples: elas mantêm a ordem de inserção e permitem a repetição dos elementos. As operações básicas são:

ADD(x): operação para adicionar um elemento no final da lista.
ADD(i,x): operação para adicionar um elemento em uma posição específica.
GET(i): operação para recuperar um elemento em uma posição específica.
REMOVE(i): operação para remover um elemento em uma posição específica.

O tipo de lista mais simples é o Vetor. Sua implementação é baseada em uma estrutura sequencial, onde por padrão os elementos são adicionados no final, após o último elemento. Seu acesso é através da posição (índice) em que foram inseridos.



Essa implementação é excelente para acessar rapidamente um elemento, por exemplo, para acessar o elemento 63, basta informar o índice 2 e o acesso será direto (GET(2))

Porém não é tão interessante quando queremos inserir um elemento em uma posição no meio, por exemplo, na posição 3 (ADD(2, 18)) pois teríamos que deslocar todos os demais elementos para direita.



Apesar esse deslocamento ser uma operação simples, em um vetor com muitos elementos essa operação pode ser custosa e demorada.


public class Vetor implements Lista {

 String[] elementos = new String[10];
 int indice;

 @Override
 public void add(String elemento) {
  elementos[indice] = elemento;
  indice++;
 }
 
 @Override
 public String get(int i) {
  return elementos[i];
 }

 @Override
 public void add(int posicao, String elemento) {
  for (int i = indice - 1; i >= posicao; i--) {
   elementos[i + 1] = elementos[i];
  }

  elementos[posicao] = elemento;
  indice++;
 }
 
 @Override
 public void remove(int posicao) {
  elementos[posicao] = null;
  
  for (int i = posicao; i+1 < elementos.length; i++) {
   elementos[i] = elementos[i+1];
  }

  indice--;
 }
 
 public static void main(String[] args) {
  Vetor vetor = new Vetor();
  vetor.add("A");
  vetor.add("C");
  vetor.add("D");
  vetor.add("E");
  
  System.out.println(Arrays.asList(vetor.elementos));

  vetor.add(1, "B");

  String c = vetor.get(2);
  System.out.println(c);
  
  System.out.println(Arrays.asList(vetor.elementos));

  vetor.remove(2);
  
  System.out.println(Arrays.asList(vetor.elementos));
 }

}

Eis que surgem as Listas ligadas para o resgate =D.
Essas listas possuem uma implementação mais elaborada. Para percorrer os elementos é necessário que cada elemento saiba onde está seu sucessor.



A grande vantagem desta implementação é que se precisarmos inserir um elemento no meio (ADD(2,'E')), basta fazer com que o elemento anterior aponte para o novo e o novo para o sucessor tornando a inserção uma operação rápida.



Em contrapartida, como nem tudo são flores, o acesso a um determinado elemento pelo índice já não é mais tão fácil. Na verdade, precisamos navegar do primeiro elemento perguntando onde está o próximo até chegarmos na posição desejada.
Além disso a navegação ocorre apenas em uma direção, do primeiro elemento até o último e há casos em que gostaríamos de ir e voltar nessa navegação.
public class ListaLigada implements Lista {

 No primeiro;
 No ultimo;

 @Override
 public void add(String elemento) {

  if (primeiro == null) {
   primeiro = new No(elemento);
   ultimo = primeiro;
  } else {
   ultimo.proximo = new No(elemento);
   ultimo = ultimo.proximo;
  }

 }

 @Override
 public String get(int posicao) {
  No no = buscarNo(posicao);
  return no.elemento;
 }

  @Override
 public void add(int posicao, String elemento) {
  No retorno = buscarNo(posicao-1);
  No novo = new No(elemento);
  novo.proximo=retorno.proximo;
  retorno.proximo = novo;
 }

 @Override
 public void remove(int posicao) {
  No retorno = buscarNo(posicao-1);
  No temp = retorno.proximo;
  retorno.proximo = temp.proximo;
 }
 
 private No buscarNo(int posicao) {
  No retorno = primeiro;
  int contador = 0;
  while (contador < posicao) {
   retorno = retorno.proximo;
   contador++;
  }
  return retorno;
 }
 
 public void imprimir() {
  String conteudo = primeiro.elemento;
  No proximoNo = primeiro.proximo;
  while(proximoNo != null) {
   conteudo+=", "+proximoNo.elemento;
   proximoNo = proximoNo.proximo;
  }
  System.out.println(conteudo);
 }

 public static void main(String[] args) {
  ListaLigada listaLigada = new ListaLigada();
  listaLigada.add("A");
  listaLigada.add("C");
  listaLigada.add("D");
  listaLigada.add("E");
  
  listaLigada.imprimir();

  listaLigada.add(1, "B");
  
  listaLigada.imprimir();

  String c = listaLigada.get(2);
  System.out.println(c);

  listaLigada.remove(2);
  
  listaLigada.imprimir();


 }

}

Para ter uma navegação bidirecional, a listas podem ser duplamente ligadas. Isso significa que o elemento sabe não só a posição do próximo mas também do anterior a ele, seu antecessor.


public class ListaDuplamenteLigada implements Lista {

 No primeiro;
 No ultimo;

 @Override
 public void add(String elemento) {
  addFim(elemento);
 }

 public void addFim(String elemento) {

  if (primeiro == null) {
   primeiro = new No(elemento);
   ultimo = primeiro;
  } else {
   No novo = new No(elemento);
   ultimo.proximo = novo;
   novo.anterior = ultimo;
   ultimo = novo;
  }
 }

 public void addInicio(String elemento) {
  if (primeiro == null) {
   primeiro = new No(elemento);
   ultimo = primeiro;
  } else {
   No novo = new No(elemento);
   
   primeiro.anterior = novo;
   novo.proximo = primeiro;
   primeiro = novo;
  }
 }

 @Override
 public String get(int posicao) {
  No no = buscarNo(posicao);
  return no.elemento;
 }

 @Override
 public void add(int posicao, String elemento) {
  No novo = new No(elemento);
  
  No esquerda = buscarNo(posicao - 1);  
  No direita = esquerda.proximo;
  
  novo.proximo = direita;
  novo.anterior = esquerda;
  
  direita.anterior = novo;
  esquerda.proximo = novo;
  
 }

 @Override
 public void remove(int posicao) {
  No retorno = buscarNo(posicao);
  
  No esquerda = retorno.anterior;
  No direita = retorno.proximo;
  
  esquerda.proximo = direita;
  direita.anterior = esquerda;
 }

 private No buscarNo(int posicao) {
  No retorno = primeiro;
  int contador = 0;
  while (contador < posicao) {
   retorno = retorno.proximo;
   contador++;
  }
  return retorno;
 }

 public void imprimirParaFrente() {
  String conteudo = primeiro.elemento;
  No proximoNo = primeiro.proximo;
  while (proximoNo != null) {
   conteudo += ", " + proximoNo.elemento;
   proximoNo = proximoNo.proximo;
  }
  System.out.println(conteudo);
 }
 
 public void imprimirParaTras() {
  String conteudo = ultimo.elemento;
  No noAnterior = ultimo.anterior;
  while (noAnterior != null) {
   conteudo += ", " + noAnterior.elemento;
   noAnterior = noAnterior.anterior;
  }
  System.out.println(conteudo);
 }

 public static void main(String[] args) {
  ListaDuplamenteLigada listaLigada = new ListaDuplamenteLigada();
  listaLigada.add("C");
  listaLigada.add("D");
  listaLigada.add("E");
  
  listaLigada.imprimirParaTras();
  listaLigada.imprimirParaFrente();
  System.out.println();
  listaLigada.addInicio("A");

  listaLigada.imprimirParaTras();
  listaLigada.imprimirParaFrente();
  System.out.println();

  listaLigada.add(1, "B");

  listaLigada.imprimirParaTras();
  listaLigada.imprimirParaFrente();
  System.out.println();

  String c = listaLigada.get(2);
  System.out.println(c);

  listaLigada.remove(2);

  listaLigada.imprimirParaTras();
  listaLigada.imprimirParaFrente();
  System.out.println();

 }

}

Resumindo:
- Listas são estruturas que permitem armazenar elementos garantindo sua ordem de inserção e permitindo repetir elementos.
- Vetor tem acesso rápido e fácil aos elementos porém pode demorar mais para inserir em determinadas posições.
- Listas ligadas e duplamente ligadas são excelentes para inserção em posições desejadas porém não são boas para acessar elementos específicos.

A sua escolha em relação à qual usar vai depender da sua necessidade. Acesso ou Inserção.

Podemos concluir também que as Pilhas e Listas são um tipo de lista que possuem características mais específicas.