Estrutura de dados

Você conhece o GraphQL e como ele pode te ajudar?

Olá, Web Developers!

Muitos aqui já devem ter ouvido falar desse tal GraphQL há algum tempo, mas sem saber ainda o que ele é e por que deveríamos cogitá-lo na nossa stack de desenvolvimento. Talvez ele seja uma boa pedida para o seu projeto.

Vamos entendê-lo um pouco mais?

AngularJS - Criação de interfaces web
Curso de AngularJS - Criação de interfaces web
CONHEÇA O CURSO

Como tudo começou

O GraphQL começou no Facebook. Imagine que para exibir uma lista de posts era necessário o acesso a uma API, e dentro de cada post tinha que vir uma lista dos usuários que curtiram. Dentro de cada objeto de usuário tem que vir o nome, foto do perfil, link para o perfil, se o usuário já é seu amigo, etc.

Pelo menos é isso que nós podemos ver quando acessamos o Facebook pelo navegador. Mas quando estamos no aplicativo mobile, não temos todas essas informações do usuário. O que temos é uma lista de usuários que curtiram e o link para seu perfil.

Poderíamos então evitar que o servidor nos envie dados que não vamos precisar, deixando o nosso app mobile mais rápido e economizando dados (bom para quem está no 3G ou 4G).

Mas, sério, não é legal criar uma nova API apenas para enviar uma estrutura levemente diferente, como “mobile/posts”.

É muito comum também que, em sistemas maiores, os dados fiquem em diferentes bases de dados. Podemos, por exemplo, ter dados relacionais no MySQL, guardar certas informações em forma de documentos no MongoDB e ter pequenos dados para consultas rápidas no Redis.

É aqui que começamos a ver que teremos um bom trabalho: juntar dados de bancos diferentes e enviar uma estrutura diferente para cada tipo de aplicação.

O GraphQL entra em cena

GraphQL

Ao invés de ter que ficar criando uma API para cada estrutura diferente de dados e/ou ficar manualmente fazendo consultas para cada banco e depois juntar os dados, que tal simplesmente dizer a “alguém” o que você precisa?

Para fazermos uma consulta no GraphQL, teríamos algo parecido com isso:

query {
   posts
}

Declaramos uma consulta com query e indicamos que queremos um campo com o nome posts.

Também podemos criar consultas que tenham mais níveis, como:

query {
   posts {
      likes
      comments
      shares
   }
}

É possível, ainda, passar parâmetros, como:

query {
   posts (userId: 157321){
      likes
      comments
      shares
   }
}

Dúvidas comuns

Não gosto de ferramentas do Facebook

O GraphQL é mais uma especificação. Então você pode usar outras ferramentas que fazem o mesmo e que não sejam do Facebook.

Uma ferramenta parecida, que visa resolver o mesmo problema, é o Falcor, desenvolvida pela Netflix.

Se eu for trabalhar com GraphQL, terei que usar React?

Não. O GraphQL pode ser usado com qualquer framework, biblioteca ou linguagem de programação.

A ideia do cliente dizer o que quer não me parece segura…

Fique tranquilo. O GraphQL tem uma coisa chamada resolvers. Com eles você pode cuidar da segurança de seus dados, permitindo ou não que determinado usuário acesse-os.

Ainda acho que não preciso disso. Minha aplicação já está muito boa com as APIs existentes.

Se você acredita que não tem problema e que a sua solução hoje já funciona perfeitamente, ótimo.

A ideia do GraphQL é ajudar a solucionar determinado problema. Se você não tem esse problema em sua aplicação, realmente você não precisa gastar tempo implementando uma ferramenta a mais.

Concluindo

O GraphQL é uma linguagem de consulta que facilita o nosso trabalho na hora de fazer requisições, basta que indiquemos os campos que queremos sem que nos preocupemos de onde os dados estão vindo.

Caso queira fazer alguns testes, acesse o GitHub GraphQL.

Tente executar, por exemplo, a seguinte query:

query {
  repository(owner: "graphql", name: "graphql-js"){
    name
    description
  }
}

O que achou do GraphQL? Já teve algum problema que poderia ter sido resolvido com ele? Acha que precisará dele em um novo projeto? Compartilhe com a gente aí nos comentários!

EmberJS - Criação de interfaces web
Curso de EmberJS - Criação de interfaces web
CONHEÇA O CURSO

Conheça os principais algoritmos de ordenação

Imagine como seria buscar um número em um catálogo telefônico se os nomes das pessoas não estivessem listados em ordem alfabética? Seria muito complicado. A ordenação ou classificação de registros consiste em organizá-los em ordem crescente ou decrescente e assim facilitar a recuperação desses dados. A ordenação tem como objetivo facilitar as buscas e pesquisas de ocorrências de determinado elemento em um conjunto ordenado.

Como preza a estratégia algorítmica: “Primeiro coloque os números em ordem. Depois decidimos o que fazer.”

Na computação existe uma série de algoritmos que utilizam diferentes técnicas de ordenação para organizar um conjunto de dados, eles são conhecidos como Métodos de Ordenação ou Algoritmos de Ordenação. Vamos conhecer um pouco mais sobre eles.

Os métodos de ordenação se classificam em:

  • Ordenação Interna: onde todos os elementos a serem ordenados cabem na memória principal e qualquer registro pode ser imediatamente acessado.

  • Ordenação Externa: onde os elementos a serem ordenados não cabem na memória principal e os registros são acessados sequencialmente ou em grandes blocos.

Hoje veremos apenas os métodos de ordenação interna.

Dentro da ordenação interna temos os Métodos Simples e os Métodos Eficientes:

C Básico
Curso de C Básico
CONHEÇA O CURSO

Métodos Simples

Os métodos simples são adequados para pequenos vetores, são programas pequenos e fáceis de entender. Possuem complexidade C(n) = O(n²), ou seja, requerem O(n²) comparações. Exemplos: Insertion Sort, Selection Sort, Bubble Sort, Comb Sort.

Dica: Veja uma breve introdução à análise de algoritmos

Nos algoritmos de ordenação as medidas de complexidade relevantes são:

  • Número de comparações C(n) entre chaves.
  • Número de movimentações M(n) dos registros dos vetores.

Onde n é o número de registros.

Insertion Sort

Insertion Sort ou ordenação por inserção é o método que percorre um vetor de elementos da esquerda para a direita e à medida que avança vai ordenando os elementos à esquerda. Possui complexidade C(n) = O(n) no melhor caso e C(n) = O(n²) no caso médio e pior caso. É considerado um método de ordenação estável.

Um método de ordenação é estável se a ordem relativa dos itens iguais não se altera durante a ordenação.

O funcionamento do algoritmo é bem simples: consiste em cada passo a partir do segundo elemento selecionar o próximo item da sequência e colocá-lo no local apropriado de acordo com o critério de ordenação.


(Imagens: Wikipedia.org)

Vejamos a implementação:

void insercao (int vet, int tam){
int i, j, x;
for (i=2; i<=tam; i++){
    x = vet[i];
    j=i-1;
    vet[0] = x; 
    while (x < vet[j]){
        vet[j+1] = vet[j];
        j--;
    }
    vet[j+1] = x;
}

Para compreender melhor o funcionamento do algoritmo veja este vídeo:

Selection Sort

A ordenação por seleção ou selection sort consiste em selecionar o menor item e colocar na primeira posição, selecionar o segundo menor item e colocar na segunda posição, segue estes passos até que reste um único elemento. Para todos os casos (melhor, médio e pior caso) possui complexidade C(n) = O(n²) e não é um algoritmo estável.


(Imagens: Wikipedia.org)

Veja este vídeo para conhecer o passo a passo de execução do algoritmo:

void selecao (int vet, int tam){
    int i, j, min, x;
    for (i=1; i<=n-1; i++){
        min = i;
    for (j=i+1; j<=n; j++){
            if (vet[j] < vet[min])
            min = j;
    }
    x = vet[min];
    vet[min] = vet[i];
    vet[i] = x;
    }
}

Métodos Eficientes

Os métodos eficientes são mais complexos nos detalhes, requerem um número menor de comparações. São projetados para trabalhar com uma quantidade maior de dados e possuem complexidade C(n) = O(n log n). Exemplos: Quick sort, Merge sort, Shell sort, Heap sort, Radix sort, Gnome sort, Count sort, Bucket sort, Cocktail sort, Timsort.

Quick Sort

O Algoritmo Quicksort, criado por C. A. R. Hoare em 1960, é o método de ordenação interna mais rápido que se conhece para uma ampla variedade de situações.

Provavelmente é o mais utilizado. Possui complexidade C(n) = O(n²) no pior caso e C(n) = O(n log n) no melhor e médio caso e não é um algoritmo estável.

É um algoritmo de comparação que emprega a estratégia de “divisão e conquista”. A ideia básica é dividir o problema de ordenar um conjunto com n itens em dois problemas menores. Os problemas menores são ordenados independentemente e os resultados são combinados para produzir a solução final.

Basicamente a operação do algoritmo pode ser resumida na seguinte estratégia: divide sua lista de entrada em duas sub-listas a partir de um pivô, para em seguida realizar o mesmo procedimento nas duas listas menores até uma lista unitária.

Funcionamento do algoritmo:

  • Escolhe um elemento da lista chamado pivô.
  • Reorganiza a lista de forma que os elementos menores que o pivô fiquem de um lado, e os maiores fiquem de outro. Esta operação é chamada de “particionamento”.
  • Recursivamente ordena a sub-lista abaixo e acima do pivô.

Dica: Conheça um pouco sobre algoritmos recursivos

(Imagem: Wikipedia.org)

Veja este vídeo para conhecer o passo a passo de execução do algoritmo:

void quick(int vet[], int esq, int dir){
    int pivo = esq, i,ch,j;         
    for(i=esq+1;i<=dir;i++){        
        j = i;                      
        if(vet[j] < vet[pivo]){     
            ch = vet[j];               
            while(j > pivo){           
                vet[j] = vet[j-1];      
                j--;                    
            }
            vet[j] = ch;               
            pivo++;                    
        }
    }
    if(pivo-1 >= esq){              
        quick(vet,esq,pivo-1);      
    }
    if(pivo+1 <= dir){              
        quick(vet,pivo+1,dir);      
    }
 }

A principal desvantagem deste método é que ele possui uma implementação difícil e delicada, um pequeno engano pode gerar efeitos inesperados para determinadas entradas de dados.

Mergesort

Criado em 1945 pelo matemático americano John Von Neumann o Mergesort é um exemplo de algoritmo de ordenação que faz uso da estratégia “dividir para conquistar” para resolver problemas. É um método estável e possui complexidade C(n) = O(n log n) para todos os casos.

Esse algoritmo divide o problema em pedaços menores, resolve cada pedaço e depois junta (merge) os resultados. O vetor será dividido em duas partes iguais, que serão cada uma divididas em duas partes, e assim até ficar um ou dois elementos cuja ordenação é trivial.

Para juntar as partes ordenadas os dois elementos de cada parte são separados e o menor deles é selecionado e retirado de sua parte. Em seguida os menores entre os restantes são comparados e assim se prossegue até juntar as partes.


(Imagens: Wikipedia.org)

Veja o vídeo para conhecer o passo a passo da execução do algoritmo:

void mergeSort(int *vetor, int posicaoInicio, int posicaoFim) {
    int i, j, k, metadeTamanho, *vetorTemp;
    if(posicaoInicio == posicaoFim) return;
    metadeTamanho = (posicaoInicio + posicaoFim ) / 2;

    mergeSort(vetor, posicaoInicio, metadeTamanho);
    mergeSort(vetor, metadeTamanho + 1, posicaoFim);

    i = posicaoInicio;
    j = metadeTamanho + 1;
    k = 0;
    vetorTemp = (int *) malloc(sizeof(int) * (posicaoFim - posicaoInicio + 1));

    while(i < metadeTamanho + 1 || j  < posicaoFim + 1) {
        if (i == metadeTamanho + 1 ) { 
            vetorTemp[k] = vetor[j];
            j++;
            k++;
        }
        else {
            if (j == posicaoFim + 1) {
                vetorTemp[k] = vetor[i];
                i++;
                k++;
            }
            else {
                if (vetor[i] < vetor[j]) {
                    vetorTemp[k] = vetor[i];
                    i++;
                    k++;
                }
                else {
                    vetorTemp[k] = vetor[j];
                    j++;
                    k++;
                }
            }
        }

    }
    for(i = posicaoInicio; i <= posicaoFim; i++) {
        vetor[i] = vetorTemp[i - posicaoInicio];
    }
    free(vetorTemp);
}

Shell Sort

Criado por Donald Shell em 1959, o método Shell Sort é uma extensão do algoritmo de ordenação por inserção. Ele permite a troca de registros distantes um do outro, diferente do algoritmo de ordenação por inserção que possui a troca de itens adjacentes para determinar o ponto de inserção. A complexidade do algoritmo é desconhecida, ninguém ainda foi capaz de encontrar uma fórmula fechada para sua função de complexidade e o método não é estável.

Os itens separados de h posições (itens distantes) são ordenados: o elemento na posição x é comparado e trocado (caso satisfaça a condição de ordenação) com o elemento na posição x-h. Este processo repete até h=1, quando esta condição é satisfeita o algoritmo é equivalente ao método de inserção.

A escolha do salto h pode ser qualquer sequência terminando com h=1. Um exemplo é a sequencia abaixo:

h(s) = 1, para s = 1
h(s) = 3h(s - 1) + 1, para s > 1

A sequência corresponde a 1, 4, 13, 40, 121, …

Knuth (1973) mostrou experimentalmente que esta sequencia é difícil de ser batida por mais de 20% em eficiência.

Veja o vídeo que demonstra o passo a passo da execução do algoritmo:

void shellSort(int *vet, int size) {
    int i , j , value;
    int gap = 1;
    while(gap < size) {
        gap = 3*gap+1;
    }
    while ( gap > 1) {
        gap /= 3;
        for(i = gap; i < size; i++) {
            value = vet[i];
            j = i - gap;
            while (j >= 0 && value < vet[j]) {
                vet [j + gap] = vet[j];
                j -= gap;
            }
            vet [j + gap] = value;
        }
    }
}

Conclusão

Neste artigo foi apresentado os principais métodos de ordenação com foco no conceito e funcionamento de cada um deles.

Você pode ver na tabela abaixo a comparação entre eles:

(Imagem: DECOM – UFOP)

Um abraço e até a próxima!

Twig - PHP Template Engine
Curso de Twig - PHP Template Engine
CONHEÇA O CURSO

Desmistificando os algoritmos recursivos

Os algoritmos recursivos são fundamentais na solução de muitos problemas envolvendo a computação, ainda assim, muitos programadores os veem como algo complexo e de difícil implementação.

Como disse o prof. Siang Wun Song:

Para fazer um procedimento recursivo é preciso ter fé.

Calma! Apesar da fala do prof. Siang, implementar um algoritmo recursivo não é um bicho de sete cabeças. Veremos alguns passos para compreendê-los de vez. o/

C Básico
Curso de C Básico
CONHEÇA O CURSO

Primeiro devemos entender o que é a recursividade. Uma função recursiva chama a si mesma dentro do próprio escopo. Pode ser uma recursão direta onde uma função A chama a própria função A ou uma recursão indireta onde uma função A chama uma função B que por sua vez chama a função A. Além de chamar a si mesma, a função recursiva deve possuir uma condição de parada que a impedirá de entrar em loop infinito.

Antes de criar uma função recursiva para determinado problema, é preciso saber se ele possui uma estrutura recursiva. Neste caso, devemos verificar se parte do problema possui o mesmo tipo do original, assim podemos dizer que a solução para ele é a recursividade. Para compreender melhor, vamos analisar o caso do somatório onde temos um número natural n >= 0 e queremos descobrir a soma de todos os números de n até 0.

Antes de criar o algoritmo devemos extrair dois elementos do problema: O caso base que se tornará a condição de parada e o passo recursivo. Vejamos algumas possíveis iterações do problema:

No caso do somatório, é possível identificar que para cada valor de n o último elemento sempre é 0, assim podemos confirmar que este é o caso base.

Analisando um pouco mais as iterações temos que para cada valor de n vamos diminuindo em 1 até que chegue ao valor 0.

Assim, nós temos que o somatório de um número natural n é o próprio n adicionado ao somatório do número antecessor (Somatório de n = n + (n-1) + (n-2) + ... + 0). Logo, o nosso passo recursivo é n + soma(n-1).

Sabemos que o caso base é 0 e o somatório de 0 é ele mesmo, estão essa será a nossa condição de parada. O nosso passo recurso é n + soma(n-1), assim já temos os elementos da nossa função recursiva e podemos criá-la:

int soma(int n){
    if(n == 0)
        return 0;
    return n + soma(n-1);
}

Esta é a implementação em C para resolver o problema de forma recursiva. Para um número natural n informado, a função irá executar até que seja encontrado o caso base e assim retornar o valor do somatório.

Vamos analisar outro problema clássico que pode ser resolvido com recursividade: o fatorial de um número natural n >= 1. O fatorial é bem semelhante ao somatório, porém é feito com multiplicação sucessiva.

Vamos analisar as possíveis iterações:

No exemplo do fatorial, o nosso caso base é 1, portanto, a nossa condição de parada será verificar se o número é 1 e, caso seja, a função deverá retorná-lo. Também é possível definir o nosso passo recursivo: fatorial de n = n x (n - 1) x (n - 2) x ... x 1 logo n! = n x fatorial(n - 1). Por fim, chegamos à seguinte implementação em C:

int fatorial(int n){
    if(n == 1)
        return 1;
    return n * fatorial(n-1);
}

Uma grande vantagem da recursividade é o fato de gerar uma redução no tamanho do algoritmo, permitindo descrevê-lo de forma mais clara e concisa. Porém, todo cuidado é pouco ao se fazer módulos recursivos. Basta seguir estes passos e você não terá grandes problemas. Como disse L. Peter Deutsch:

Iterar é humano, fazer recursão é divino.

Um abraço e até a próxima!

Slim - Microframework PHP
Curso de Slim - Microframework PHP
CONHEÇA O CURSO

Introdução à análise de algoritmos

Os algoritmos fazem parte do dia a dia das pessoas. Seja uma receita culinária ou instruções para uso de medicamentos. Ou seja, é uma sequência de ações executáveis para chegar à solução de um determinado tipo de problema. Segundo Edsger Dijkstra, um algoritmo corresponde a uma descrição de um padrão de comportamento, expresso em termos de um conjunto finito de ações.

Desta forma, a análise de algoritmos (descrita e difundida por D.E. Knuth) tem como função determinar os recursos necessários para executar um dado algoritmo. Ela estuda a correção e o desempenho através da análise de correção e da análise de complexidade. Dados dois algoritmos para um mesmo problema, a análise permite decidir qual dos dois é mais eficiente.

C Básico
Curso de C Básico
CONHEÇA O CURSO

Análise da correção

A análise da correção procura entender porque um dado algoritmo funciona. É preciso ter certeza de que o algoritmo está correto. Como algoritmos prometem resolver problemas, é esperado que ele cumpra essa premissa.

Análise da complexidade

A Análise da complexidade procura estimar a velocidade do algoritmo. Prever o tempo que o algoritmo vai consumir. Verificar qual é o custo de usar um dado algoritmo para resolver um problema específico. Porém, neste aspecto, encontram-se duas dificuldades:

  1. O tempo gasto depende dos dados de entrada.
  2. O tempo também depende da capacidade de hardware do computador utilizado.

Mas, mesmo assim, é possível definir a complexidade de determinado algoritmo.

Para medir o custo de execução de um algoritmo é comum definir uma função de custo ou função de complexidade, f; f(n) é a medida do tempo necessário para executar um algoritmo para um problema de tamanho n;

Para entendermos melhor, vejamos o trecho de código abaixo:

int soma = 0;
for (i=0; i<n; i++)
    soma = soma + vet[i];

O custo para execução deste algoritmo é f(n) = n. Pois o laço executa de acordo com o tamanho de n. Se n=10, logo o laço executará 10 vezes, se for igual a 100 executará 100 vezes.

Podemos tornar este algoritmo mais eficiente fazendo a seguinte modificação:

int soma = vet[0]; 
for (i=1; i<n; i++)
    soma = soma + vet[i];

Assim, temos uma nova função de complexidade, f(n) = n - 1.

Os dois trechos de códigos resolvem o mesmo problema, somar os elementos de um vetor. Porém, cada um tem um custo de execução diferente do outro, a partir da análise, podemos definir qual é o algoritmo mais eficiente para resolver este problema específico.

Melhor caso, Pior caso, Caso Médio.

Na análise da complexidade, definimos para um algoritmo, o melhor, o pior e o caso médio, como forma de mensurar o custo do algoritmo de resolver determinado problema diante de diferentes entradas.

  • Melhor caso: é quando o algoritmo representa o menor tempo de execução sobre todas as entradas de tamanho n;

  • Pior caso: maior tempo de execução sobre todas as entradas de tamanho n;

  • Caso médio (ou caso esperado): é a média dos tempos de execução de todas as entradas de tamanho n.

Desta forma, considere o problema de acessar um determinado registro de um vetor de inteiro; cada registro contém um índice único que é utilizado para acessar o elemento do vetor. O problema: dada uma chave qualquer, localize o registro que contenha esta chave; O algoritmo de pesquisa mais simples é o que faz a pesquisa sequencial.

Seja f uma função de complexidade tal que f(n) é o número de registros consultados no arquivo, temos:

  • Melhor caso: f(n) = 1 (registro procurado é o primeiro consultado);

  • Pior caso: f(n) = n (registro procurado é o último consultado ou não está presente no arquivo);

  • Caso médio: f(n) = (n+1)/2 (a média aritmética entre o melhor e o pior caso);

Além disso, a análise de algoritmos estuda certos paradigmas como divisão e conquista, programação dinâmica, gula, busca local, aproximação, entre outros que se mostraram úteis na criação de algoritmos para vários problemas computacionais.

Conclusão

Neste artigo, vimos uma breve introdução do que se trata a análise de algoritmos. Como ela é útil para definir o algoritmo mais eficiente em determinados problemas. Assim, o objetivo final não é apenas fazer códigos que funcionem, mas que sejam também eficientes.

“Um bom algoritmo, mesmo rodando em uma máquina lenta, sempre acaba derrotando (para instâncias grandes do problema) um algoritmo pior rodando em uma máquina rápida. Sempre.” – S. S. Skiena, The Algorithm Design Manual

Um abraço e até a próxima!

Java - Banco de dados e JDBC
Curso de Java - Banco de dados e JDBC
CONHEÇA O CURSO