DEV Community: André Ulle

Entendendo Algoritmos - Cap.5 Quicksort em Clojure

André Ulle — Mon, 16 Oct 2023 02:08:36 +0000

Este mês estou participando do clube de leitura #devslendo (Mais informações aqui) em que o livro escolhido é o Entendendo Algoritmos. No capítulo 5, é apresentado o Quicksort. Assim como no outro artigo, não irei explicar o conceito, pois o livro já o faz muito bem. A ideia aqui não é ser mais um resumo, mas sim mostrar como implementar na prática usando Clojure.

Quicksort

O quicksort é um algoritmo de ordenação. Este algoritmo é muito mais rápido do que a ordenação por seleção e é muito utilizado na prática. por exemplo, a biblioteca-padrão da linguagem C tem uma função chamada qsort, que é uma implementação do quicksort. O algoritmo quicksort também utiliza a estratégia DC (Dividir e Conquistar).
Aditya Y. Bhargava

Além do livro, sugiro também esse vídeo para quem gostaria de entender mais sobre o quicksort.

Implementando Quicksort com clojure

Vou dar uma breve introdução sobre o que é o quicksort. Basicamente, temos um vetor, e para ordená-lo, escolheremos um pivô. O pivô servirá de base para nossa comparação. Após a primeira iteração com esse vetor, teremos todos os valores menores que o pivô ao lado esquerdo e todos os maiores ou iguais ao lado direito. Para isso, dado o seguinte vetor:

[3 4 5 2 1 6 7 3]

Vamos escolher o primeiro elemento como nosso pivô. Seguindo a regra acima, teríamos o seguinte resultado:

esquerda [2 1]
pivô 3
direita [4 5 6 7 3]

"E repetiremos a execução para cada subgrupo, selecionando um novo pivô nesse subgrupo (esquerda e direita). Sei que essa explicação é bem breve e sucinta, por isso recomendo esse vídeo para que você entenda bem o conceito.

Quicksort no Clojure

O Clojure é uma linguagem funcional que tem como um de seus princípios a imutabilidade, isso significa que um valor não sofre alterações ao longo da execução. Isso garante a confiabilidade nos dados e evita side-effects inesperados. Temos que levar isso em conta ao implementar o algoritmo de Quicksort.
Iremos utilizar a recursividade, para trabalhar os subgrupos, até que todo o vetor esteja devidamente ordenado. Irei explicar cada passo da função.

A Função

(ns entendendo-algoritmos-clojure.recursion.quicksort)

(defn execute
  [values]
  (let [pivot (last values)
        remaining-values (butlast values)
        left (filter #(< % pivot) remaining-values)
        right (filter #(>= % pivot) remaining-values)]
    (flatten (concat (if (> (count left) 1) (execute left) left)
                     [pivot]
                     (if (> (count right) 1) (execute right) right)))))

Caso queira testar a função acima, basta acessar o replit.com, criar um novo repl do tipo Clojure, colar a função acima e, logo na linha debaixo, adicionar uma chamada como por exemplo:

(execute [4 5 2 3 7 8 1])

O resultado deverá ser o vetor ordenado [1 2 3 4 5 7 8]

O nome da função é execute, pois o namespace já contem o contexto de quicksort: (ns entendendo-algoritmos-clojure.recursion.quicksort)

Entendendo a função

A primeira coisa sobre nossa função é que recebemos o parâmetro values, que irá representar nosso vetor na função. Logo em seguida, temos a seção (let []) onde definimos alguns símbolos para organizar nosso código. O let funciona da seguinte forma, dentro de colchetes temos nossos símbolos, seguindo a seguinte lógica:"

(let [simbolo valor
      simbolo-2 valor-2])

Onde simbolo passa a representar o valor que está logo a sua direita, por exemplo:

(let [filme "O auto da compadecia"])

Para utilizar os símbolos, precisamos estar dentro do escopo do let, portanto, antes de fechar seu parênteses. Entenda por símbolo o que, em outras linguagens, chamamos de propriedade, variável ou constante, o que nesse caso faz mais sentido, uma vez que seu valor nunca muda. Nesse caso, se quisermos imprimir o valor, faríamos da seguinte forma:

(let [filme "O alto da compadecia"]
(print filme))
; Imprime no console: O auto da compadecia

Note que antes de fechar o parênteses do let, chamamos a instrução (println simbolo). Isso acontece porque os símbolos criados no let só existem dentro do seu escopo.

Ok, agora que você entende um pouco mais sobre o escopo e como o let funciona para criar nossos símbolos locais. Vamos entender o que cada símbolo representa.
Começando pelo nosso pivot. Iremos utilizar a função last que retorna o último item do nosso array. Ele seria o equivalente a values[values.length - 1], como é visto na maioria das linguagens.

Em seguida, para não repetirmos o próprio item na lista, iremos criar uma nova lista, descartando o pivot, para isso, utilizaremos a função butlast.

Para o símbolo left, filtramos a lista com os valores menores que o pivot, e em right os valores maiores ou iguais ao pivot, utilizando a função filter, que possui dois parâmetros: o predicado e uma lista. O predicado é simplesmente uma condição para filtrar nossa lista, trazendo apenas os itens desejados. No caso de left, queremos todos os itens menores que o pivot, então usamos (< % pivot), onde % representa cada um dos elementos de values:

(filter #(< % pivot) remaining-values)

OBS: No Clojure, sempre começamos a comparação com o operador, então em vez de % < pivot, escrevemos < % pivot.

Caso base

Se não sabe o que é um caso base na recursividade sugiro a leitura desse link

O nosso caso base acontece quando o vetor (left ou right) possui apenas um elemento, nesse caso ao invés de chamarmos a função recursivamente, iremos apenas retornar o próprio vetor.
(if (> (count right) 1) (execute right) right)
Se você não está acostumado com a sintaxe Clojure, saiba que o if também é uma função e, nesse caso, ela espera três parâmetros:
(if predicate value-when-true value-when-false)

Então, para a nossa função, se o número de itens for maior que um, ela irá chamar novamente a função execute para aquele subvetor, caso contrário, retornará o próprio subvetor. Note que fizemos o mesmo para left e right, então seguem o mesmo princípio.

Nesse momento vamos então concatenar left + [pivot] + right. Então, uma certeza que temos é que nossa função sempre terá um pivô no meio da concatenação, e consequentemente, tudo que está à esquerda é menor que ele e tudo à direita é maior.

Simplificando o concat sem o if teriamos a seguinte concatenação:

(concat left [pivot] right)

Substituindo os símbolos por valores:

(concat [3 2 1] [4] [5 6 8 7])

Isso tem como resultado:
[3 2 1 4 5 6 8 7]

E por fim, como a recursão poderá retornar listas dentro de listas, temos o flaten que faz o achatamento dos dados.
Por exemplo:

(flaten [2 [2 3 [4]] [5 6] 8])

Retorna o dado achatado:
[2 2 3 4 5 6 8]

Como a função se resolve

Na imagem a seguir, ilustrei o que acontece em cada iteração da função execute e como os blocos da concatenação são organizados naquele momento. Portanto, sempre teremos três blocos na seguinte sequência: left, pivot e right.
O item que será o nosso pivô naquela interação está destacado em vermelho.

Ficamos por aqui

Espero que o exemplo tenha te ajudado a visualizar o quicksort na prática dentro do paradigma funcional.

Agradeço a todos que chegaram até aqui e peço, por favor, que me ajudem com seu feedback. Comentem se os exemplos foram claros ou se sentiram falta de algum ponto que não abordei. Ficarei feliz em ajudá-los!

Entendendo Algoritmos - CAP 2. Como usar arrays e listas encadeadas na prática

André Ulle — Tue, 10 Oct 2023 01:23:17 +0000

Este mês estou participando do clube de leitura #devslendo (Mais informações aqui) em que o livro escolhido é o Entendendo Algoritmos. No capítulo 2, são apresentados o array e a lista encadeada. O capítulo por si só é muito claro e direto. O objetivo deste post é trazer exemplos de implementações práticas em diferentes linguagens.

Para testar os exemplos aqui apresentados você pode utilizar o site replit. Basta criar um novo REPL selecionando a linguagem desejada.

Um pouquinho sobre Array

Não tenho a intenção de falar muito sobre o array. Acredito que ele seja mais familiar para a maioria das pessoas, e a implementação é introduzida nos primeiros passos de várias linguagens. No entanto, se é novidade para você, aqui vai um exemplo de array em C:

#include<stdio.h>
#include<conio.h>
int main(void)
{
  float notas[5] = {7, 8, 9.5, 9.9, 5.2};
  // declarando e inicializando o vetor notas

  printf("Exibindo os Valores do Vetor \n\n");
  printf("notas[0] = %.1f\n", notas[0]); // imprime 7
  printf("notas[1] = %.1f\n", notas[1]); // imprime 8
  printf("notas[2] = %.1f\n", notas[2]); // imprime 9.5
  printf("notas[3] = %.1f\n", notas[3]); // imprime 9.9
  printf("notas[4] = %.1f\n", notas[4]); // imprime 5.2

  getch();
  return 0;
}

Podemos pensar no vetor (também conhecido como array) como uma variável com páginas, onde sempre começamos da página 0 e podemos ir até o número de páginas que determinamos quando o declaramos. Essa é uma restrição importante sobre o array; na maioria das linguagens, você precisa definir o tamanho dele assim que o declara. No caso acima, se tentássemos atribuir ou imprimir um valor para a posição 5, que corresponderia à sexta nota, receberíamos uma exceção de índice fora dos limites do vetor, pois nesse caso o limite é a posição 4. Essa exceção em inglês é comumente traduzida como: index out of bounds exception.

Listas Encadeadas

Vou tentar ser o mais sucinto possível, sem deixar de abordar detalhes importantes para que possamos compreender a implementação das listas encadeadas em cada um dos exemplos.

Em todos os exemplos utilizarei o mesmo conceito de caixas, onde, ao abrirmos essa caixa, iremos validar se existe uma chave através do atributo temChave. Enquanto não encontramos, continuaremos abrindo as próximas caixas, ou, até não houver mais caixas.

Decidi escrever o nome das variáveis e os comentários em português para que os exemplos fossem mais acessíveis. Além disso, utilizei um laço de repetição para não dar spoilers sobre o Capítulo 3 do livro, que trata de recursividade.

Começando pelo exemplo que acredito ser o mais simples, utilizando POO, através de uma Classe que possui a si mesma como um dos tipos de atributo.

Exemplo em POO utilizando JAVA

//Estrutura das caixas
class Caixa {
  boolean temChave;
  Caixa proximaCaixa;
}

class Main {
  public static void main(String[] args) {
    //Criando as Caixas
    Caixa primeiraCaixa = new Caixa();
    primeiraCaixa.temChave = false;
    Caixa segundaCaixa = new Caixa();
    segundaCaixa.temChave = false;
    Caixa terceiraCaixa = new Caixa();
    terceiraCaixa.temChave = true;
    Caixa quartaCaixa = new Caixa();
    quartaCaixa.temChave = false;

    // Criando lista encadeada
    primeiraCaixa.proximaCaixa = segundaCaixa;
    segundaCaixa.proximaCaixa = terceiraCaixa;
    terceiraCaixa.proximaCaixa = quartaCaixa;

    Caixa caixaAberta = primeiraCaixa;

    //inicializamos com 1 porque começamos com a primeira caixa aberta
    int contador = 1;

    // Abrindo as caixas enquanto houver não encontrar a chave, ou até acabarem as caixas
    while(!caixaAberta.temChave && caixaAberta != null){
      contador++; // contador = contador + 1;
      caixaAberta = caixaAberta.proximaCaixa;
    }

    System.out.println(contador);
  } 
}

O retorno do código acima será 3, porque mesmo que exista uma caixa dentro da terceira, ela tem a chave, portanto, cumpre a nossa condição.

A magia acontece no trecho caixaAberta = caixaAberta.proximaCaixa;. Onde a caixaAberta passa a ser a próxima caixa, que por sua vez, possui uma próxima caixa, e por aí vai.

Exemplo em POO utilizando Python

class Caixa:
    def __init__(self, tem_chave, proxima_caixa=None):
        self.tem_chave = tem_chave
        self.proxima_caixa = proxima_caixa

# Criando as Caixas
primeira_caixa = Caixa(False)
segunda_caixa = Caixa(False)
terceira_caixa = Caixa(True)
quarta_caixa = Caixa(True)

# Criando lista encadeada
primeira_caixa.proxima_caixa = segunda_caixa
segunda_caixa.proxima_caixa = terceira_caixa
terceira_caixa.proxima_caixa = quarta_caixa

caixa_aberta = primeira_caixa

# Inicializamos com 1 porque começamos com a primeira caixa aberta
contador = 1

# Abrindo as caixas enquanto houver não encontrar a chave, ou até acabarem as caixas
while caixa_aberta is not None and not caixa_aberta.tem_chave:
    contador += 1
    caixa_aberta = caixa_aberta.proxima_caixa

print(contador)

O exemplo é muito parecido, mudando levemente a sintaxe utilizada. Nesse momento, vamos apenas contemplar a diferença na limpeza e elegância do Python sem {}();. Eu gosto hihi

Exemplo em Programação Estruturada utilizando C

#include <stdio.h>
#include <stdbool.h>

// Definição da estrutura Caixa
typedef struct Caixa {
    bool temChave;
    struct Caixa* proximaCaixa;
} Caixa;

int main() {
    // Criando as Caixas
    Caixa caixas[4];
    //Inicializando cada caixa com a referência da próxima "& "
    caixas[0] = (Caixa){false, &caixas[1]};
    caixas[1] = (Caixa){false, &caixas[2]};
    caixas[2] = (Caixa){true, &caixas[3]};
    caixas[3] = (Caixa){true, NULL};

    Caixa* caixaAberta = &caixas[0];

    // Inicializamos com 1 porque começamos com a primeira caixa aberta
    int contador = 1;

    // Abrindo as caixas enquanto houver não encontrar a chave, ou até acabarem as caixas
    while (caixaAberta != NULL && !caixaAberta->temChave) {
        contador++; 
        caixaAberta = caixaAberta->proximaCaixa;
    }

    printf("%d\n", contador);

    return 0;
}

Deixei o exemplo ligeiramente diferente. Note que dessa vez estou utilizando uma struct em C no lugar da classe, e as Caixas são representadas por um vetor de 4 posições. Ao contrário do que fiz no Java, inicializo as caixas já com a referência da próxima. Isso é possível porque utilizamos ponteiros e guardamos o endereço de memória daquela variável ao invés do valor. Para não me estender muito nesse universo, irei deixar esse link, para que você possa conhecer mais sobre ponteiros.
O Vetor nesse caso é apenas para simplificar os nomes das caixas, ao invés de primeiraCaixa, segundaCaixa e etc, utilizei um vetor com caixa[1], caixa[2], caixa[n]...
Apesar disso, continuo usando a referência dentro de cada caixa, para chegar na caixa seguinte, através do caixaAberta = caixaAberta->proximaCaixa;.

Porém o resultado permanece 3, pois a execução é a mesma da anterior.

Exemplo em Programação Funcional utilizando Clojure

Deixei o meu preferido para o final. Não se assuste e nem se frustre por não entender esse código logo de cara.
Existem várias particularidades no dialeto LISP, que são diferentes das linguagens baseadas em C, como C#, Java, JavaScript e até mesmo Python.
Você também estranhará o uso de hífen, ponto de interrogação e dois pontos, mas isso é comum nas convenções do Clojure.

; criando um mapa chave e valor para cada caixa
(def quarta-caixa {:tem-chave? false
                  :proxima-caixa nil});

(def terceira-caixa {:tem-chave? true
                  :proxima-caixa quarta-caixa});

(def segunda-caixa {:tem-chave? false
                  :proxima-caixa terceira-caixa});

(def primeira-caixa {:tem-chave? false
                    :proxima-caixa segunda-caixa});

; função que abre as caixas
(defn abrir-caixa 
  [caixa contador]
  ; Se tem chave imprime o contador, senão abre a próxima caixa e incrementa 1 ao contador
  (if (:tem-chave? caixa)
    (print contador)
    (recur (:proxima-caixa caixa) (inc contador))))

; incializa a operação pela primeira caixa
(abrir-caixa primeira-caixa 1)

Nesse exemplo não tive como fugir da recursividade, uma vez que o Clojure é principalmente baseado em funções.

Clojure é uma linguagem interpretada que executa suas aplicações com base na JVM (máquina virtual Java). Portanto, não podemos utilizar um símbolo que ainda não foi criado. Por isso, comecei pelas caixas internas para referenciá-las na caixa anterior.
Sim, os comentários de uma linha utilizam o caractere ; hihi.

Mesmo não entendendo completamente, nada te impede de abrir o replit e fazer alterações no código acima para ver o que acontece hihi

Ficamos por aqui

Espero que os exemplos possam ter te ajudado a visualizar um pouco as listas na prática. Apesar dos exemplos em C e Clojure, acredito que compreender bem o primeiro exemplo em Java ou Python já é mais do que suficiente para entender como as listas encadeadas funcionam e como manipulá-las.

Software design - Você entendeu o problema?

André Ulle — Thu, 05 Oct 2023 17:18:23 +0000

Esse é o primeiro artigo que escrevo sobre Discovery Técnico e minha ideia é abordar todas as etapas de forma detalhada e com exemplos práticos. Começaremos desde o entendimento inicial do problema até os entregáveis de arquitetura.

Acredito que, para a grande maioria das pessoas, quando começamos a ter contato com uma nova requisição, seja para a manutenção de algo ou para a implementação de algo novo, começamos simultaneamente a escrever mentalmente o código e o design da solução para aquele problema que ainda estamos conhecendo. Isso é natural, queremos resolver, e queremos resolver rapidamente, pois o backlog está suspirando em nosso cangote, e o prazo apertado ativa esse nosso instinto de sobrevivência, onde resolver logo é o melhor caminho. Porém, esse estado de alerta pode ser traiçoeiro, e você pode se fechar para entender o problema de fato. No meio do caminho, você pode ter o viés de uma solução pronta em sua cabeça. Conforme o problema vai tornando a sua solução inviável, existe o risco de você se apegar tanto a ela, e se deixar levar pela frustração. No pior dos casos, você pode manter a solução que veio precocemente, recorrendo a adaptações ou até abrindo mão de alguma regra ou outra, pois o foco aqui já não está mais no problema, ele se perdeu. Esqueça o código por enquanto; no primeiro momento, não existe algoritmo, não existe linguagem. Seu foco deve ser principalmente entender o problema e, para isso, o separaremos em dois pontos: dados e regras.

Dados e Regras

Eu desenvolvi essa forma de organizar as coisas na minha mente, e se por acaso a adotei de algum lugar, juro que foi de forma inconsciente hehe.

Dados

Vamos lá. Primeiro, falando sobre os Dados, eu os vejo como a matéria-prima que teremos que manipular. Neste momento, é importante compreender a natureza do dado (Oxi?), ou seja, o que quero dizer é que precisamos primeiro entender quais são os dados que serão inseridos na nossa aplicação, o que são, de onde vêm, do que se alimentam e como sobrevivem. O Dado pode ser mais livre e flexível, como uma String, ou pode seguir um padrão mais rígido, como uma lista enumerada com itens específicos.

Neste estágio inicial, gosto de criar um dicionário de dados, onde os organizo por tipo e pela semântica que possuem, além de verificar se são obrigatórios ou se têm algum tipo de restrição, por exemplo:

------  Pedido de Reparo ---------
|   Descrição.       |     Tipo.             |   Exemplo.   |   
| Relato             |   Texto               | "PC morreu"  |  
| Severidade         |   Inteiro             | 5            | 
| Status             |   Lista de Status     | "Cancelado"  | 
| Valor              |   Decimal             | 2,000.00     | 
| Data de Criação    |   Date                | 1993-08-26.  |
| Categoria          |   Lista de Categorias | "Informática"|

Perceba que estamos utilizando tipos primitivos para Relato, Severidade, Valor e Data de Criação. No entanto, para Categoria e Status, utilizaremos uma lista. Isso já me implica na necessidade de levantar as possibilidades dessa lista. Neste momento, vou apresentar apenas o exemplo para a categoria. Seguiríamos a mesma lógica para Status.

------ Categorias -----
|   Descrição    |     Tipo     |   Exemplo  
| Nome           |   Texto      | Informática

------ Categorias Existentes

- Informática
- Escritório
- Eletrodomésticos
- Outros

Entender os dados te guiará para compreender o domínio de negócio. Saber como esses dados estão interconectados proporcionará uma noção inicial de como organizar esses domínios na sua abstração. Os dados vão nos guiar aos domínios de negócio, e estes, por sua vez, vão influenciar a arquitetura e o design. Portanto seja mais que um amigo, seja friend dos dados e os conheça bem.

Regras

Legal. Agora que tenho os dados organizados e uma compreensão inicial de como estão estruturados, é crucial aprender como esses dados se transformarão em regras. É neste momento que o dado ganha vida, quando eu oriento os fluxos dentro do sistema e capacito o sistema para a tomada de decisão. Escrever regras claras e precisas ajudará a eliminar possíveis ruídos de comunicação entre mim e a pessoa que fez a requisição (PM/PO/SM/BA e tantas outras siglas que representam nossos demandantes).

Mas como poderei avaliar se a minha regra está bem escrita? Evite descrever regras abstratas ou que exijam conhecimento prévio do negócio. Por exemplo:

1 - Cancelar casos antigos

O que define se um caso é antigo? Como posso tomar essa decisão com base nos dados disponíveis?
Que tal a seguinte regra:

1 - Quando a data de criação do chamado for superior a dois dias da data atual, alterar o status do report para "Cancelado"

A regra proposta parece bem clara e precisa. Ela estabelece que, se a data de criação do chamado for superior a dois dias em relação à data atual, o status do Chamado deve ser alterado para "Cancelado". Isso proporciona uma orientação direta e mensurável para a ação a ser tomada.

Outro ponto importante é saber qual é o gatilho do fluxo em que implementaremos a regra. Em que momento na linha do tempo do nosso sistema isso vai acontecer? Deixar a regra solta, por mais bem escrita que esteja, não é suficiente. É necessário investigar as expectativas em relação a isso, talvez o stakeholder ainda não saiba que uma rotina precisa ser implementada. Nesse caso, poderíamos atualizar a regra:

Ponto de disparo: Execução de rotina de revisão dos chamados
Dado que existam chamados cadastrados
1 - Quando a data de criação do chamado for superior a dois dias da data atual, então alterar o status do report para "Cancelado"

Inseri um Gherkin subliminar na regra acima. No entanto, o que é crucial aqui é deixarmos claro o evento que irá disparar nossa regra. É quando esse dado deixa o seu ninho confortável no disco rígido para ser arranhado pelas garras das nossas regras. Posteriormente, podemos entrar em detalhes técnicos, como se essa rotina é um Job no CTRL-M (Socorro DEUS), uma Lambda na AWS, um cronjob, entre outras opções. Neste momento, o essencial é que você vai tornar evidente para todos que as coisas não acontecem magicamente, e ninguém irá te reportar um BUG dizendo que o status não foi atualizado às 6 horas da manhã, quando na verdade essa rotina é executada às 7.

Menos importante do que decidir se utilizaremos um loop FOR, um operador ternário ou cinquenta estruturas IF aninhadas que se amontoam num monte horrendo fedendo à manutenção e à complexidade, é garantir, neste momento, que o comportamento esperado esteja baseado nos dados corretos e nos momentos certos.

Em resumo, uma boa regra possui clareza quanto aos dados de entrada, quando ela deve acontecer, o comportamento desejado e quais dados ele influencia na saída.

Depois de tudo, retornamos à reflexão "Entendi o Problema?". Talvez, ao longo dessa jornada, você perceba que o problema não está claro, nem mesmo para os Stakeholders. Isso será útil para eliminar os ruídos de comunicação ou para elucidar detalhes importantes de negócio que estão subentendidos por alguma pessoa ou área. Também te ajudará a antecipar possíveis blocks relacionados a falta de insumos de negócio.

A próxima pergunta é: "Apenas você entendeu o problema?"

Mas isso fica para uma próxima leitura. Agradeço a quem chegou até aqui e peço que, por favor, me ajude com seu feedback. Isso me permitirá saber se conteúdos como este podem auxiliar as pessoas nessa aventura que é o Desenvolvimento e a Arquitetura de Software.