DEV Community: Wagner Abrantes

Compreendendo Templates

Wagner Abrantes — Tue, 17 Nov 2020 04:43:31 +0000

Um template nos permite criar um documento e em seguida, mesclar dados com ele.

Estamos aprendendo sobre Templates para que possamos criar um documento, uma página da web e, em seguida, mesclar dados personalizados a essa página. Templates Web permitem fornecer resultados personalizados aos usuários.

Pense no Twitter — você entra na sua página principal e vê os resultados personalizados para você. Essa página principal foi criada uma vez. É um template. No entanto, para cada usuário, esse template é preenchido com dados específicos desse usuário.

Outra exposição comum a Templates que a maioria de nós recebe todos os dias — Spam.

Uma empresa cria uma correspondência para enviar a todos e em seguida, mescla os dados com esse template para personalizar a correspondência para cada indivíduo. O resultado:

Caro Sr. Jones,

Você está cansado de contas altas de eletricidade?

Notamos que sua casa em …

Caro Sr. Smith,

Você está cansado de contas altas de eletricidade?

Notamos que sua casa em …

Caro {{Name}},

Você está cansado de contas altas de eletricidade?

Notamos que sua casa em …

Se você tiver alguma experiência com desenvolvimento web, você consegue olhar para uma página mesmo sem olhar o código fonte e identificar, o que é “template” e o que são “dados”.

Me faz lembrar também daqueles brinquedos de criança com geometrias e cores, onde o nosso texto seria a peça principal do brinquedo com os espaços específicos onde podemos inserir os objetos geométricos que seriam como os nossos dados.

Basicamente o que define o uso de templates em Go são duas ações, primeiro fazemos parse dos dados e depois executamos eles em alguma saída.

Parse:

    tpl, err := template.ParseFiles("tpl.html")
    if err != nil {
        log.Fatal(err)
    }

Essa primeira etapa vai ser sempre muito parecida, você vai parsear esse conteúdo de algum arquivo ou vai receber ele como string de uma função, mas o destino é o mesmo, parsear.

Inclusive, o parâmetro de ParseFiles é variado, então você pode parsear mais de um documento na mesma função ou você pode usar a variável tpl que foi criada pra fazer uma nova chamada assim tpl.ParseFiles(novos argumentos).

Executando o conteúdo parseado em uma saída de terminal:

    err = tpl.Execute(os.Stdout, nil)
    if err != nil {
        log.Fatal(err)
    }

Agora o segundo exemplo é genérico, pois como expliquei existem diversas opções de saída, você pode enviar o conteúdo parseado pra uma saída de terminal ou pra um arquivo por exemplo.

Você pode também usar tpl.ExecuteTemplate(saída, nome, err) que permite não apenas definir uma saída como o exemplo acima mas também executar um template especifico usando o argumento do nome que seria uma string com o nome do documento em questão.

Então se você usou mais de um argumento em ParseFiles, pode ser que essa opção seja útil pra que você não tenha que executar todos os templates obrigatoriamente.

Agora já sabemos pra quê servem templates e como parsear e executar um ou mais templates. Vamos ver então um exemplo de como parsear mais de um template de forma otimizada.

Arquivos

Logo de inicio temos a importação dos pacotes de “text/template”, “log” para tratamento de erros e “os” para usar como saída padrão dos templates parseados.

package main

import (
    "log"
    "os"
    "text/template"
)

Definimos tpl como uma variável com escopo global que aponta para o pacote de template.

var tpl *template.Template

A função init() é executada antes da func main() O objetivo principal da função init() é inicializar as variáveis globais que não podem ser inicializadas no contexto global.

Aqui usamos template.Must que nos auxilia com error handling, em seguida chamamos ParseGlob com o path de uma pasta com os templates que desejamos parsear.

O ParseGlob é equivalente o ParseFiles, a diferença é que ele lê um path o e faz o parse dos documentos todos de uma vez.

Com essa combinação parseamos todos os arquivos dentro da pasta em questão de uma só vez e ai vamos distribuindo a saída uma a uma.

O “nome_da_pasta/*” significa que quero parsear todos os documentos dentro da pasta.

func init() {
    tpl = template.Must(template.ParseGlob("nome_da_pasta/*"))
}

func main() {
    err := tpl.Execute(os.Stdout, nil)
    if err != nil {
        log.Fatalln(err)
    }

    err = tpl.ExecuteTemplate(os.Stdout, "arquivo1.gohtml", nil)
    if err != nil {
        log.Fatalln(err)
    }

    err = tpl.ExecuteTemplate(os.Stdout, "arquivo2.gohtml", nil)
    if err != nil {
        log.Fatalln(err)
    }

    err = tpl.ExecuteTemplate(os.Stdout, "arquivo3.gohtml", nil)
    if err != nil {
        log.Fatalln(err)
    }
}

A ordem de execução seria arquivo1, arquivo1, arquivo2, arquivo3, no caso o arquivo 1 retorna duas vezes pois ele é executado individualmente na função tpl.ExecuteTemplate e na tpl.Execute pois ele seria o primeiro na ordem dentro da pasta.

Arquivos

Lembrando a questão do exemplo do e-mail, até o momento apenas fizemos o parse e a saída dos nossos templates, mas não os tornamos dinâmicos de fato, para isso precisaremos passar tipos de dados do Go dentro dos nossos templates.

E para isso dentro dos arquivos precisamos usar uma notação com duas chaves, usando isso no momento do parse a função vai identificar essa notação e inserir nossos dados no template.

Em uma pasta “data” vou criar um arquivo chamado “dados_pessoais.txt” com esse conteúdo:

Vamos testar aqui meu nome é: {{.Nome}}
Minha idade: {{.Idade}}

Quando a função ler esse arquivo e identificar as chaves duplas vamos ter dois dados que vem de uma struct. O ponto representa a struct em si e “Nome” sendo a propriedade da struct. Se fosse uma varável comum por exemplo, seria usado apenas o ponto, assim:

{{.}}

Se eu estivesse passando um slice eu poderia usar uma Action dentro do template:

{{range .}} {{.}} {{end}}

Assim você dá um range nos itens do slice o que se torna uma opção viável para listas em html.

A estrutura de um parse com dados vindos de código Go para dentro do arquivo fica então dessa forma:

package main

import (
    "text/template"
    "log"
    "os"
)

type data struct {
    Nome  string
    Idade int
}

var tpl *template.Template

func init() {
    tpl = template.Must(template.ParseGlob("data/*"))
}

func main() {

    perfil := data{
        "vapordev",
        29,
    }

    err := tpl.ExecuteTemplate(os.Stdout, "dados_pessoais.txt", perfil)
    if err != nil {
        log.Fatalln(err)
    }
}

A estrutura é como a anterior, esse arquivo fica fora da pasta onde ficam os arquivos de texto com os templates a serem parseados, por isso as propriedades da struct estão com inicial em maiúscula, para que possam sem importadas para fora do pacote main.

As maiores diferenças aqui são que, instanciamos tipo data onde entrego a minha idade, e passo perfil como argumento na função.

Como seguimos o mesmo padrão, anterior é possível adicionar mais arquivos na pasta data e mais funções para a execução da saída.

A saída:

Vamos testar aqui meu nome é: vapordev
Minha idade: 29

Obs. As vezes quando salvamos o arquivo, caso você mesmo não tenha inserido as importações e tenha deixado isso para o fmt fazer automaticamente é muito provável que ele importe o pacote errado, pois exite text/template e html/template os dois compartilham as mesmas funções com a diferença de que o pacote de template para html possui opções de segurança.

Arquivos

Agora que já temos certa ideia de como podemos parsear texto e usá-lo em uma saída vamos tentar usar esse conhecimento como representação de dados em uma página. Apesar de não estarmos utilizando html, ainda, já podemos pensar nessas representações, inclusive acho mais interessante pois as tags html a principio acabam poluindo o documento, com texto simples você tem menos ruído.

O exercício consiste em olhar uma página web do seu interesse, e tentar representar essa página ou pelo menos um pedaço dela em txt usando o pacote text/template para parsear coisas da página que a gente sabe que são dados varáveis e não apenas texto estático.

Como exemplo eu usei a página no twitter da @tecnogueto com foco na parte de perfil.

Aqui temos diversas informações que podemos parsear mas antes precisamos identificar quais seriam.

Pensando em tipos de dados, tudo que seria variável nessa página podemos já considerar como dados em Golang, como o numero de seguidores por exemplo.

A mídia da página, administradores podem modificar o avatar e a capa, assim também como a bio.

A palavra Seguindo e Seguidores por exemplo, é apenas texto isso não seria um dado Go, o numero de seguidores por outro lado sim.

O botão de Seguir e Notificação eu consigo ver como tipos booleanos enquanto que o Botão de Direct e Opções diria que se comportam como links então acredito que não seriam tipos de dados do Go exatamente.

Esse é um exercício interessante para se fazer quando se está aprendendo sobre desenvolvimento web pois vai te trazendo mais clareza sobre como são construídas as páginas, como são escolhidos os tipos de dados num geral.

Trouxe a página da @tecnogueto como exemplo não por acaso, nesse momento ta rolando uma campanha de MatchFunding para o desenvolvimento de uma plataforma online de ensino em tecnologia pensada do gueto para o gueto.

Vou deixar um link para quem quiser saber mais sobre a iniciativa e puder contribuir, se a empresa em que você trabalha tem foco em ajudar a comunidade, principalmente focada em diversidade, essa é uma ótima oportunidade de ter uma ação concreta.

Colabore: Aqui

Voltando ao exercício, identifiquei os dados e então criei structs com os tipos que seriam usados.

type midia struct {
    Avatar string
    Capa   string
}

type tweetConfig struct {
    Tweets      float64
    Notificação bool
    Follow      bool
    DataDaConta string
    Seguindo    float64
    Seguidores  float64
}

type perfil struct {
    Nome        string
    User        string
    Bio         string
    Localização string
    Site        string
    midia
    tweetConfig
}

Decidi que seria mais interessante compor os tipos, por isso temos tweetConfig e media como tipos individuais mas que compõem o tipo perfil.

Em midia tudo é string, pois inclusive com html quando passamos um arquivo na tag o caminho ou link da mídia é uma string então aqui não muda.

tweetConfig Temos floats para numero de tweets, seguidores e etc. Notificações e Follow boleanos e DataDaConta eu imagino que seja usado um tipo como o timestamp que temos em schema de bancos de dados, aqui vou usar liberdade criativa (Gambiarra) pra que seja uma string.

O restante dos dados strings, em um db usaríamos VARCHAR com uma limitação de caracteres e etc, mas quando passamos os dados para Go podem ser strings.

Instanciar esses dados termina assim:

    tecnoGueto := perfil{
        "Tecnogueto",
        "tecnogueto",
        `Nós da Tecnogueto, queremos socializar o cenário atual, ensinando profissões 
dentro da tecnologia e promovendo a diversidade de gênero, raça/etnia e cultural.`,
        "Rio de Janeiro, Brasil",
        "tecnogueto.com.br",
        midia{"https://pbs.twimg.com/profile_images/1162103759218139137/CYfSOQFx_400x400.jpg", "https://pbs.twimg.com/profile_banners/1002022507413757958/1553770868/1500x500"},
        tweetConfig{
            448,
            true,
            true,
            "Maio de 2018",
            100,
            3.2343,
        },
    }

Essa variável é o que vamos passar como argumento para a função de executar template.

Depois disso, parsear, executar, escolher uma saída é igual ao que já fizemos então vou deixar os detalhes a sua escolha.

O meu arquivo de perfil ficou assim:

{{.Nome}}
{{.Tweets}} Tweets
{{.Capa}}

{{.Avatar}} Opções  Direct  {{.Notificação}} {{if .Follow}} Seguindo {{else}} Seguir {{end}}
{{.Nome}}
@{{.User}}

{{.Bio}}

{{.Localização}}    {{.Site}}  Ingressou em {{.DataDaConta}}

{{.Seguindo}} Seguindo  {{.Seguidores}} Seguidores

Como pode ver, além dos dados, usei uma condição como Action na propriedade de Follow, assim se instanciar como true aparece que estou seguindo, senão aparece Seguir.

Não imaginei como faria a mesma coisa com o botão de notificação pois ele não muda o texto mas sim o highlight, mas da pra pensar em algumas coisas.

A minha saída ficou assim:

Tecnogueto
448 Tweets
https://pbs.twimg.com/profile_banners/1002022507413757958/1553770868/1500x500

https://pbs.twimg.com/profile_images/1162103759218139137/CYfSOQFx_400x400.jpg Opções  Direct  true  Seguindo 
Tecnogueto
@tecnogueto

Nós da Tecnogueto, queremos socializar o cenário atual, ensinando profissões 
dentro da tecnologia e promovendo a diversidade de gênero, raça/etnia e cultural.

Rio de Janeiro, Brasil    tecnogueto.com.br  Ingressou em Maio de 2018

100 Seguindo  3.2343 Seguidores

Obviamente, nada parecido com a página, a intenção nem é essa, mas sim entender melhor como is tipos Go se relacionam em um template. Quando falar mais sobre o pacote html/template as coisas vão ficar ainda mais interessantes.

Usar funções com dados em template pode ajudar com alguns tipos de tarefas e não seriam exatamente violações de “Separation of Concerns”, modificar a forma como os dados são apresentados é uma forma de se aplicar isso.

Uma função no template que vai modificar um dado lá no Data Base já é outra conversa.

Podemos passar funções no template, vamos escolher aqui duas funções bem simples.

A primeira:

Retorna os três primeiros caracteres de uma string passada em argumento, tranquilo.

func firstThree(s string) string {
    s = strings.TrimSpace(s)
    if len(s) >= 3 {
        s = s[:3]
    }
    return s
}

A segunda:

Uma função que já vem implementada no pacote string do Go.

strings.ToUpper

Já conhecemos as funções, agora como elas são passadas no template?

Essa estrutura já é nossa velha conhecida, porém temos duas modificações, template.new inicia um template, o foco por enquanto é Funcs() que vem antes de ParseFiles() no method chaining.

func init() {
    tpl = template.Must(template.New("").Funcs(fm).ParseFiles("tpl.gohtml"))
}

Funcs() tem um argumento do tipo FuncMap que é esse “fm”, vamos dar uma olhada nele mas precisamos entender algumas particularidades antes.

FuncMap recebe dois argumentos, uma string e uma interface vazia.

Interface vazia é uma interface sem nenhum método, um tipo Go tem pelo menos nenhum método, a interface vazia implementa todos os tipos Go, inclusive os tipos customizados que você quiser criar.

Então significa que FuncMap recebe como argumento uma string e qualquer coisa.

Estamos passando uma string que vai funcionar como apelido das nossas funções e as funções em si que é o argumento da interface vazia que recebe qualquer coisa.

var fm = template.FuncMap{
    "uc": strings.ToUpper,
    "ft": firstThree,
}

fm vai como argumento para Funcs() e em seguida processado em ParseFiles() que projeta os dados no template juntamente com as funções pré definidas.

A partir daqui é o básico, instanciar o objeto com os dados, passar como argumento para função de Execute com uma escolha de saída.

Arquivo

Atribuímos “apelidos” para as funções, passamos as funções como parametro na chaining de ParseFiles().

Como decidimos quais dados irão receber essas funções? Usamos o apelido da função no template!

uc = Upper Case
ft = First three

{{uc .}} <!-- apelido + dado -->

Repare que estamos usando html, mas o pacote ainda é o text/template.

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>functions</title>
</head>
<body>

{{range .}}
{{uc .Manufacturer}}
{{end}}


{{range .}}
{{ft .Manufacturer}}
{{end}}


</body>
</html>

Range passa por duas structs que estão dentro de um slice do qual usaremos as funções na propriedade Manufacturer, por isso o Range é aplicado somente ao “.” que é uma struct chamada car.

A nossa saída de template:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>functions</title>
</head>
<body>

FORD

TOYOTA


For

Toy

</body>
</html>

A primeira deixando os nomes das marcas em maiúsculas, e a segunda imprimindo somente os três primeiros caracteres.

Já entendemos melhor o resultado, vamos analisar essa cadeia de métodos novamente pois é bem fácil se perder aqui.

    tpl = template.Must(template.New("").Funcs(fm).ParseFiles("tpl.gohtml"))

Talvez você se pergunte pra que serve o template.new, se verificarmos a documentação, Funcs() tem um receptor com um ponteiro para Template então precisamos ter um template existente na cadeia de métodos antes de usar Funcs().

template.new vai criar esse template vazio que vai ser usado como receptor em Funcs() que em seguida vai aplicar os “apelidos” das nossas funções no template vazio, para só então fazermos o ParseFiles.

Outro exemplo de aplicação de função que não viola o principio de “Separation of Concerns” é a utilização de funções para modificar os dados de Horário e Data, aplicamos com funções uma disposição diferente no template, mas não estamos de fato fuçando no dado real.

Exemplo da aplicação: clique aqui

Podemos usar também Pipelines para aplicar o mesmo dado a várias funções.

Levando em consideração ainda as funções do exemplo anterior de upercase e três caracteres:

{{. | uc | ft }}

Se o dado utilizado fosse Fiat a nossa saída seria assim:

Fiat    FIAT    Fia

Dependendo da ocasião ter funções que modificam a disposição dos dados de acordo com o usurário tendo como base uma condicional no template é uma opção comum.

Além das funções que podem ser passadas para o template com Funcs() existem funções globais de template que podemos usar seus “apelidos” sem a necessidade de utilizar template.new e Funcs() pois essas funções já são globais no pacote de template.

Um exemplo simples é a função de index, podemos chamar cada item de um slice através do seu index ao invés de chamar todos de uma só vez com range.

Assim:

{{index . 0}} <!-- chamando o item 0 do slice -->
{{index . 2}} <!-- chamando o item 2 do slice -->
{{index . 1}} <!-- chamando o item 1 do slice -->

Aqui na documentação você encontra uma lista com todas as funções globais para templates: Clique aqui

É possivel modularizar páginas assim você tem vários arquivos especializados em uma parte especifica da sua página principal e então chamar esse pedaço onde for necessário. É um pouco parecido com as Partials do Ruby on Rails.

Exemplo:

Eu quero uma página index, mas eu não quero colocar nela, o conteúdo do meu footer e minha lista de compras pois se apresentar no index e estiver em um só arquivo vai se tornar confuso para dar manutenção quando essa pagina tiver uma quantidade muito grande de conteúdo.

Tem uma template golang com uma notation diferente,

{{define “”}} {{end}}

define e uma string que seria o nome desse template.

footer.gohtml

{{define "footer"}}
<footer>
  Algumas informações de copyright ou talvez alguma informação do autor?
</footer>
{{end}}

list.gohtml

{{define "lista"}}
    <h2>Lista de compras</h2>

    <ul>
      <li>Café</li>
      <li>Pão Integral</li>
      <li>Manteiga</li>
    </ul>
{{end}}

Repare que o nome dado na string não é o mesmo do arquivo, pois quando chamar esses dois arquivos separados no index, vamos chamar pela string.

Assim:

index.gohtml

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Lista de Compras</title>
  </head>
  <body>
    {{template "lista"}}
  </body>
  {{template "footer"}}
</html>

Usamos a notation template seguida do nome do template.

A nossa saída:

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Lista de Compras</title>
  </head>
  <body>

    <h2>Lista de compras</h2>

    <ul>
      <li>Café</li>
      <li>Pão Integral</li>
      <li>Manteiga</li>
    </ul>

  </body>

<footer>
  Algumas informações de copyright ou talvez alguma informação do autor?
</footer>

</html>

O arquivo main.go faz as chamadas normalmente, usando ParseGlob() para parsear todos os templates de uma vez.

Caso queira consultar o arquivo: clique aqui

Caso seja necessário é possível passar dados dentro de templates aninhados, chamando o dado nas duas notations.

Definição de onde o dado vai aparecer no template

{{define "footer"}}
    <p>Olá senhor {{.}} gostariamos muito de...</P>
{{end}}

Chamada do template passando o dado:

{{template "footer" .}}

Eu extrai o html da página de documentação do Go, dei uma limpada nas coisas que não eram necessárias como o Go playground e etc.

Você pode baixar o arquivo: aqui

O objetivo:

Criar tipos de dados diferentes para

Titulos "H1,H2,H3" e etc
Links
Paragrafos Titulos, Links e Paragrafos serão slices e cada um pertence a sua própria struct, no total três.

Cada titulo, link e Paragrafo deve:

Ser chamado no template através do seu index no slice.

Onde houver divs:

Precisa ser feito um template aninhado.

Nesse paragrafo aplique uma função a sua escolha: Tutoriais por Daniel Mazza
Sugestão:

Inverter strings

Opcional:

Pesquisar sobre o pacote Time e passar no final do body uma função que retorna Dia/Mês/Ano

O pacote de templates termina aqui, porém existe ainda muito mais na documentação que eu recomendo a leitura.

No repositório desse artigo vou deixar uma pasta de respostas livre nos dois exercícios, você poderá clonar esse repo, colocar seu exercício nesse repositório com seu user na pasta, ex:

├── exercicio
|    └── respostas
|        └── wagnerdevocelot
└── index.gohtml

A trilha de web não termina aqui, falaremos sobre servers na próxima oportunidade.

TestingGo

Wagner Abrantes — Sat, 07 Nov 2020 05:23:46 +0000

É muito provável que você já tenha ouvido falar de testes então vamos dar uma molhada nos pés aqui.

O teste em si serve pra você verificar a integridade do seu software e por meio desse garantir que funcione sem ou com o mínimo de efeitos colaterais. Em outras palavras, você precisa garantir que seu código faz o que você diz que ele faz.

Existe uma infinidade de convenções a respeito de testes em várias comunidades, e pode ser que em cada uma delas os testes sejam feitos de formas diferentes.

Meu foco não será na técnica e sim em um tipo especifico de teste, o Teste de Unidade ou Unit Test, onde se verifica a integridade da menor unidade dentro do software, uma função por exemplo.

Ao final do desenvolvimento de uma feature é muito comum que se tenha dezenas de testes de unidade inclusive mais código de teste do que de feature, isso porque o teste de unidade é muito simples e rápido de ser escrito.

Por ser rápido e simples costumamos chamar esse tipo de teste de “barato”, pois demanda pouco esforço durante do desenvolvimento.

Podemos mensurar o custo dos tipos de teste através da pirâmide de testes.

Geralmente no meio da pirâmide tem outros tipos, essa é uma versão mais simplificada.

Teste de Integração: É definido como um tipo de teste onde os módulos do software são testados como um grupo. Um projeto de software típico consiste em vários módulos de software, codificados por diferentes programadores. O objetivo deste nível de teste é expor defeitos na interação entre esses módulos quando eles são integrados.

E2E (End to End) O objetivo do teste de ponta a ponta é testar tanto o software quanto as dependências, integridade de dados e comunicação com outros sistemas, interfaces e bancos de dados para exercer a produção completa como cenário.

Existem ainda mais alguns, aqui eu vou falar mais dos unitários pois quem está aprendendo a programar começa com programas menores então nem faz muito sentido algo como E2E.

Na maioria das empresas é o mais utilizado justamente por ter um custo menor, pelo menos é o que dizem hahaha. Inclusive algumas empresas nem testam…

Como funciona?

Matemática básica é sempre muito simples de se entender então acredito que a função mais simples de uma calculadora como, soma é um bom começo, se você quiser pode complicar depois, mas não seremos rasos aqui.

A questão aqui é saber quais os dados de entrada e saída, o teste é basicamente uma afirmação do que você deseja como software.

EX: Entrada{2,2}, Esperado{4} para uma função de soma, é bobinho a principio, mas boa parte das coisas sobre software são assim, as pessoas que estragam tudo criando complexidade desnecessária, muitos iniciantes evitam testes no inicio por isso.

Vamos dizer que alguém escreveu a função Sum() e de alguma forma onde temos Esperado{4} o teste nos retorna Obteve{0}, provável que a função tenha sido mal escrita e precisa ser corrigida, então depois de mudanças finalmente ela retorna Obteve{4} PASS, significa que obtivemos sucesso em fazer com que a nossa função se comportasse como era esperado.

Vamos a um exemplo com código um pouco mais concreto:

Essa é a nossa função de soma, muito simples nada demais.

func Sum(a, b int) int {
    return a + b
}

E esse é o nosso teste:

package calculator

import (
    "testing"
)

func TestSum(t *testing.T) {

    verifica := func(t *testing.T, resultado, esperado int) {
        t.Helper()
        if resultado != esperado {
            t.Errorf("resultado '%d esperado '%d'", resultado, esperado)
        }
    }

    t.Run("Soma dois inteiros", func(t *testing.T) {
        resultado := Sum(2, 2)
        esperado := 4
        verifica(t, resultado, esperado)
    })

    t.Run("Soma dois negativos:", func(t *testing.T) {
        resultado := Sum(-4, -5)
        esperado := -9
        verifica(t, resultado, esperado)
    })

    t.Run("Soma numeros grandes:", func(t *testing.T) {
        resultado := Sum(100000000000000, 455456745455745342)
        esperado := 455556745455745342
        verifica(t, resultado, esperado)
    })
}

Dissecação

Disse que era bem simples e isso na verdade é 10x maior que a função que estamos testando haha, mas agora que você sabe o conceito eu vou explicar a parte prática e tu vai ver que é tranquilo.

Uma das nossas opções, seria algo como isso:

func TestSum(t *testing.T) {
    soma := Sum(10, 10)
    if soma != 20 {
        t.Error("Falhou no teste!")
    }
}

Assim é bem mais simples, apesar de ser um teste feito na mesma unidade (Sum) temos apenas um bloco de código. Todo teste tem um prefixo Test, seguido do nome da função que queremos testar.

func TestXxx(*testing.T)

Um parâmetro com um ponteiro importado do pacote “testing” o type T possui três propriedades:

common: É outra struct que compartilha os elementos em comum entre type T e type B essa segunda serve para funcionalidades de benchmark que falarei sobre futuramente. O type common é usado como receiver em várias funções presentes na interface TB que agrega todas as funções que utilizam dados de common, sendo a maioria de log, error e fatal.

isParallel: É um tipo booleano, que sinaliza se os testes estão rodando em paralelo ou não.

context: Um ponteiro de testContext que define testes em paralelo, channels e coisas como onde começam e onde terminam usando o pacote Time.

Esse miolo que é onde entra a especificação do que seria a entrada de dados, a função Sum com os parâmetros é declarada em uma variável e em seguida perguntamos, soma é diferente de 20?

    soma := Sum(10, 10)
    if soma != 20

Por final temos o que seria a saída, a função Error que vem da interface TB usa a type common como receiver.

t.Error(“Falhou no teste!”)

Analisando o conjunto

Agora que temos uma ideia de como funciona a estrutura de um teste vamos ver com mais detalhes aquele primeiro maior mas por partes, vamos saindo do micro para o macro.

Esse teste possui uma estrutura parecida, podemos ver que a função Run vem da mesma struct que estávamos falando type T então é muito provável que ela venha da interface TB, mas não, ela tem apenas type T como receiver existe outra função Run que tem como receiver type B mas essa fica no arquivo benchmark.go do pacote testing.

A estrutura de Run é assim:

func (t *T) Run(name string, f func(t *T))

Name: “Soma dois inteiros”

f: func TestSum()

Temos um miolo com uma separação mais interessante, aqui fica muito claro que resultado é o retorno de Sum() e nosso esperado é um int ao invés de colocar o numero hardcoded numa condicional.

t.Run("Soma dois inteiros", func(t *testing.T) {
    resultado := Sum(2, 2)
    esperado := 4
    verifica(t, resultado, esperado)
})

Agora temos verifica(), vamos dar uma olhada melhor nela:

verifica  :=  func(t *testing.T, resultado, esperado int)

verifica recebe uma função que tem type T, Sum() e o retorno de Sum() como argumentos.

Helper() faz parte de common então temos duas versões uma com type T e outra type B ela serve para marcar a sua função como auxiliar o que é justamente o caso.

A condicional é usada em verifica para que todas as condições de teste que você deseja não precisem aumentar a complexidade.

Errorf() indica que temos uma saída formatada, ela funciona como Logf() porem tem uma chamada de Fail() que serve pra marcar o teste como falho, mas continua a execução para que os demais testes terminem.

E então como argumento de Errorf() temos as saídas que irão nos dizer o que o teste nos retornou e o que ele esperava, porém agora numa função auxiliar dedicada a dar a saída de dados de todos os test cases.

verifica := func(t *testing.T, resultado, esperado int) {
    t.Helper()
    if resultado != esperado {
        t.Errorf("resultado '%d esperado '%d'", resultado, esperado)
    }
}

O que parecia complicado, já não é mais tão complicado assim, teste analisar o mesmo código agora conhecendo a base.

package calculator

import (
    "testing"
)

func TestSum(t *testing.T) {

    verifica := func(t *testing.T, resultado, esperado int) {
        t.Helper()
        if resultado != esperado {
            t.Errorf("resultado '%d esperado '%d'", resultado, esperado)
        }
    }

    t.Run("Soma dois inteiros", func(t *testing.T) {
        resultado := Sum(2, 2)
        esperado := 4
        verifica(t, resultado, esperado)
    })

    t.Run("Soma dois negativos:", func(t *testing.T) {
        resultado := Sum(-4, -5)
        esperado := -9
        verifica(t, resultado, esperado)
    })

    t.Run("Soma numeros grandes:", func(t *testing.T) {
        resultado := Sum(100000000000000, 455456745455745342)
        esperado := 455556745455745342
        verifica(t, resultado, esperado)
    })
}

Agora que você leu até aqui eu tenho duas coisas pra dizer, uma é que não terminei de falar sobre testes ainda e tem mais conteúdo pela frente, a segunda é que eu gostaria do seu feedback aqui nos comentários ou você pode me chamar no meu Twitter.

Eu quero saber é a sua senioridade e qual a adequação da minha abordagem e linguagem durante não apenas esse artigo mas também em relação aos demais, assim posso ter uma ideia mais clara de como devo abordar os assuntos por aqui.

Se conectando ao PostgreSQL usando Golang

Wagner Abrantes — Tue, 27 Oct 2020 23:43:11 +0000

Nem tudo precisa ser na CLI - Instalando o PostgreSQL e o pgAdmin4

O inicio é bem simples e vai depender mais do SO, estou usando o postgreSQL pois é um dos databases mais utilizados, mas você pode utilizar outro banco relacional com pequenas modificações.

Não se trata de um tutorial sobre SQL em si e sim de fazer a conexão do seu banco de dados com o Golang.

Por esse motivo eu vou instalar e administrar o Postgres da forma mais simples possível, que é através de um client, pois não sou de ferro. Estou usando o Manjaro no momento e vou instalar o Postgres através do gerenciador de aplicações e também vou instalar o pgAdmin para gerenciamento de servidores e bancos de dados visual no PostgreSQL.

Acredito que essa seja uma abordagem interessante para iniciantes que não tem experiência com banco de dados, existe um folclore muito grande a respeito de UPDATE sem WHERE por aí e apesar das histórias parecerem engraçadas depois de um tempo o medo é real hahaha.

Na loja de apps do seu SO é muito provável que você encontre os dois mas de qualquer forma vou deixar alguns links.

Aqui vou deixar um link pra quem quiser baixar o PostgreSQL no ubuntu.

Aqui o link de download do pgAdmin4

Terminando de instalar os dois, quando abrir o pgAdmin ele vai subir o client no seu browser e em seguida pedir pra você definir uma senha, vou definir a minha como “vapordev123”.

Clicando com o botão direito em cima de servers podemos criar um, vou chamar o meu de “AHAB”.

Abaixo uma mensagem de erro nos avisa de que precisamos definir mais informações.

Na aba de connection vamos definir o nosso host que será o “localhost” e a porta que será “5432” o restante vamos manter, clicamos em save e temos nosso servidor.

Vou criar agora um banco de dados, clico com o botão direito em cima do server AHAB, create/database.

Aqui só precisamos definir o nome do banco, que será “MobyDick”, e agora save!. O Banco de dados tá pronto, agora vamos criar a tabela que vamos manipular usando Go.

Acompanhe na imagem:

Azul: Clique em cima para selecionar MobyDick.
Vermelho: Clique no Query Tool e abrira um console para escrevermos.
Verde: Nossa tabela se chama “article”, terá um “id”, “title” e “body”.
Rosa: Clique no botão de execução para criar a tabela.



CREATE TABLE article (
    id SERIAL PRIMARY KEY,
    title VARCHAR(255),
    body TEXT

);

Clicando com o botão direito sobre MobyDick clique em refresh e agora você pode verificar a tabela em:

MobyDick/Schemas/public/Tables, e article estará lá.

Os bancos de dados tem seus próprios tipos, para ter uma ideia simples da tabela que criamos, id é apenas um identificador, ele serve também para quando tivermos uma nova tabela criar uma relação entre elas passando o id como uma chave estrangeira.

Nosso title recebeu um VARCHAR(255) que é um dado de caractere como string e tem uma limitação de 255 caracteres.

Body recebeu o tipo TEXT pois esse é um dado de caractere que não tem limite, que o torna o candidato mais adequado para ser o corpo de um artigo.

Aqui mesmo no pgAdmin vamos inserir o primeiro artigo na nossa tabela antes de ir ao código Golang.

Clique no Query Tool e use o seguinte código e execute.



INSERT INTO article (id, title, body) VALUES (1, 'Golang + PostgreSQL', 'But I must explain to you how all this mistaken idea');

Esse é um artigo em que no body eu coloquei um “lorem ipsum”. Mas a estrutura desse insert é essa:



INSERT INTO article (id,title,body) VALUES (O que você quer inserir separado por vírgulas);

Depois que conseguir damos um refresh no DB e vamos agora fazer um select para verificar nossos dados.



SELECT * FROM article

Isso deve retornar na parte de baixo a tabela e dados inseridos. Estou usando cada vez menos imagens pois imagino que você deva estar se habituando a página de administração do DB e também para evitar repetição.

Database Driver Config

A estrutura das pastas é assim:



├── gopostgres
|    └── dbconfig
|        └── driverConfig.go
└── main.go

Você pode escolher o nome que for melhor, mas eu fiz uma pasta diferente para o arquivo driverConfig.go pois vou usá-lo como pacote e importar no main.go mais a frente.



package dbconfig

import "fmt"

type Article struct {
    ID    int
    Title string
    Body  []byte
}

A struct que será a nossa representação da tabela Article aqui no código, caso você tenha visto o tutorial o WEBtrhough a estrutura é parecida, foi proposital pra que esse artigo seja um complemento.



const PostgresDriver = "postgres"

const User = "postgres"

const Host = "localhost"

const Port = "5432"

const Password = "vapordev123"

const DbName = "MobyDick"

const TableName = "article"

Uma série de constantes, com strings que já são familiares, todas as informações que definimos no banco de dados usaremos aqui para que a conexão possa ser feita.

A única constante definida aqui em função do código é a PostgresDriver, vamos usar um driver de terceiros pois não existe opção na biblioteca padrão.

O driver é especifico de acordo com o banco de dados que você pretende utilizar, e com as suas ambições, alguns drivers vem com um toolkit para aplicações, aqui eu quero apenas fazer a conexão e usar a biblioteca padrão de SQL do Go para fazer as operações necessárias.



var DataSourceName = fmt.Sprintf("host=%s port=%s user=%s "+
    "password=%s dbname=%s sslmode=disable", Host, Port, User, Password, DbName)

Essa é a criação da string completa com todas as informações necessárias para conectar e fazer operações.

A única coisa que não cheguei a mencionar for essa ultima parte da string "sslmode" quando criamos nosso banco de dados não fizemos modificação no SSL, então aqui o valor na string é "disable" pois esse é o valor padrão.

A função Sprintf envia strings formatadas, então iremos usar DataSourceName como argumento mais adiante.

main.go

O arquivo main.go fica fora da pasta dbconfig por isso precisamos importar aqui ./dbconfig e usamos uma variável para chamar os itens presentes no arquivo driverConfig.go.

Importamos também "fmt", o pacote SQL, e o github.com/lib/pq que é o driver do postgres temos um underscore na importação do driver pois não usaremos funções dele aqui, só iremos enviar a string de conexão.

Como já disse as libs de drivers são de terceiros então você precisará usar go get para fazer download do pacote.



go get github.com/lib/pq

Duas variáveis com package level scope db que aponta para o struct DB presente no pacote SQL e a err do tipo error que será usada em conjunto com a função checkErr para checagem de erros adiante.



package main

import (
    "database/sql"
    "fmt"

    dbConfig "./dbconfig"

    _ "github.com/lib/pq"
)

var db *sql.DB
var err error

Uma função bem simples para tratar erros durante o uso das queries.



func checkErr(err error) {
    if err != nil {
        panic(err.Error())
    }
}

Na main func sinalizamos o acesso e você já pode ver como usamos dados importados do driverConfig.go usando o nome definido aqui na importação e chamando o nome original presente na constante.

Atribuímos as variáveis o valor da função de Open do sql que recebe como parâmetro, o driver e a dataSourceName com todas as constantes definidas como senha, host e etc.

Fazemos error handling para checar tudo ocorreu como esperado, pode ser usada também a função Ping() que bate no host do banco pra verificar a conexão.

O defer é um statement do Golang, ele serve pra fazer o adiamento de algo, abaixo de db.Close tem as funções que para manipular a nossa tabela, usar um defer aqui quer dizer: "Fecha a conexão com o banco de dados, mas só depois que terminar de executar essas chamadas de função".



func main() {

    fmt.Printf("Accessing %s ... ", dbConfig.DbName)

    db, err = sql.Open(dbConfig.PostgresDriver, dbConfig.DataSourceName)

    if err != nil {
        panic(err.Error())
    } else {
        fmt.Println("Connected!")
    }

    defer db.Close()

    sqlSelect()
    sqlSelectID()
    sqlInsert()
    sqlUpdate()
    sqlDelete()
}

Para testar a conexão só precisamos comentar as chamadas de funções com "//" e também não podemos esquecer de deixar aberto o client do PostgreSQL pois precisamos bater no localhost para obter as respostas.

Output:



Accessing MobyDick ... Connected!

SELECT

A estrutura original do SELECT que a maioria deve conhecer:



SELECT id, title, body FROM article

Ou poderia ser:



SELECT * FROM article

Significa, "Postgre, me da todas as informações dessa tabela aqui", isso é chamado de statement no SQL que você pode traduzir e chamar de "declaração", o SELECT seria apenas uma dessas declarações.



func sqlSelect() {

    sqlStatement, err := db.Query("SELECT id, title, body FROM " + dbConfig.TableName)
    checkErr(err)

    for sqlStatement.Next() {

        var article dbConfig.Article

        err = sqlStatement.Scan(&article.ID, &article.Title, &article.Body)
        checkErr(err)

        fmt.Printf("%d\t%s\t%s \n", article.ID, article.Title, article.Body)
    }
}

Temos um error handling.

A função db.Query retorna "rows" que são as linhas do sql, essas linhas precisam ser scaneadas uma a uma com auxilio de outras duas funções.

Usamos o for com sqlStatement.Next o Next prepara as linhas do DB uma a uma para serem lidas pelo sqlStatement.Scan.

Instanciámos article para passar os valores do DB para a struct, o método Scan recebe os valores da struct e transforma os tipos do PostgreSQL como VARCHAR, ID, TEXT em tipos do Go.

Depois de recuperados os dados printamos eles no console.
Essa é a primeira linha que adicionei na tabela usando o pgAdmin.

Output:



Accessing MobyDick ... Connected!

1   Golang + PostgreSQL But I must explain to you how all this mistaken idea

SELECT BY ID

Fazemos um SELECT para buscar apenas uma linha da tabela pelo seu id.



SELECT id, title, body FROM article WHERE id 1

"Postgre, me retorna id, title e body da tabela article onde o id é 1"

O Sprintf para enviar o sqlStatement para db.QueryRow que é usado quando se precisa retornar apenas uma linha da tabela, podendo receber mais argumentos além do statement, nesse caso "1" que é o id da linha que devemos retornar.

Em seguida a mesma estrutura de Scan e Print que usamos para resgatar os valores e imprimir o output.



func sqlSelectID() {

    var article dbConfig.Article

    sqlStatement := fmt.Sprintf("SELECT id, title, body FROM %s where id = $1", dbConfig.TableName)

    err = db.QueryRow(sqlStatement, 1).Scan(&article.ID, &article.Title, &article.Body)
    checkErr(err)

    fmt.Printf("%d\t%s\t%s \n", article.ID, article.Title, article.Body)
}



Accessing MobyDick ... Connected!

1   Golang + PostgreSQL But I must explain to you how all this mistaken idea

Temos o mesmo resultado pois não fizemos alterações com a tabela e esse select usa o id "1" como parâmetro, vou mostrar mais um output usando "2" como id pra mostrar como fica a saída de erro.



Accessing MobyDick ... Connected!
panic: sql: no rows in result set

goroutine 1 [running]:
main.checkErr(...)
    /home/vapordev/workspace/GoPostgres/main.go:114
main.sqlSelectID()
    /home/vapordev/workspace/GoPostgres/main.go:58 +0x34b
main.main()
    /home/vapordev/workspace/GoPostgres/main.go:29 +0x1aa
exit status 2

Ele conecta com o DB mas não retorna a linha pois ela não existe.
Podemos ver tbm as linhas com o rastro do erro, linha 114 é onde está a nossa função checkErr() então toda fonte de erro começa nela, em seguida temos linha 58 que é exatamente onde o erro ocorreu e linha 29 que é de onde foi feita a chamada da função.

INSERT

Um statement que insere informações na tabela, esse e os demais tem uma estrutura muito parecida pois nenhum precisará retornar uma tabela só precisaremos verificar se a ação foi executada com sucesso.

Criamos o statement:



INSERT INTO article VALUES ("o que você quer inserir separado por virgulas")

O db.Prepare cria uma instrução para queries ou execuções posteriores, várias queries ou execuções podem ser executadas de forma concorrente.

O db.Prepare atribuído na variável insert é usado com o método Exec que executa uma instrução preparada com os argumentos e retorna um Resultado. Nessa etapa é onde inserimos os dados que foram interpolados no statement ($1=id, $2=title, $3=body).

RowsAffected retorna o número de linhas afetadas pela operação. Nem todos os bancos suportam essa função, no caso o RowsAffected faz parte de uma interface result que tem outra função chamada LastInsertId() que nesse caso não funciona com o driver do postgres então vamos usar RowsAffected mesmo.



func sqlInsert() {

    sqlStatement := fmt.Sprintf("INSERT INTO %s VALUES ($1,$2, $3)", dbConfig.TableName)

    insert, err := db.Prepare(sqlStatement)
    checkErr(err)

    result, err := insert.Exec(5, "Maps in Golang", "Sed ut perspiciatis unde omnis iste natus error sit voluptatem accusantium")
    checkErr(err)

    affect, err := result.RowsAffected()
    checkErr(err)

    fmt.Println(affect)
}

A saida mostrando que a conecxão foi bem sucedida e que uma linha foi afetada, a partir daqui não temos retorno de linhas da tabela, mas se quisermos verificar o conteúdo do banco basta dar um novo select.

Output:



Accessing MobyDick ... Connected!
1

A saida após feito o insert e utilizado select novamente.

Output:



Accessing MobyDick ... Connected!
1   Golang + PostgreSQL But I must explain to you how all this mistaken idea 
5   Maps in Golang  Sed ut perspiciatis unde omnis iste natus error sit voluptatem accusantium

UPDATE

A partir daqui as coisas ficam entediantes pois o que muda são os padrões de statement, mas o código tem pouca diferença.

Novamente preparamos uma string com o Statement da vez que é um UPDATE.



UPDATE article SET body WHERE id 5

"Vamos fazer uma modificação em article no campo body do elemento com o id numero 5"



func sqlUpdate() {

    sqlStatement := fmt.Sprintf("update %s set body=$1 where id=$2", dbConfig.TableName)

    update, err := db.Prepare(sqlStatement)
    checkErr(err)

    result, err := update.Exec("But I must explain to you how all this mistaken idea", 5)
    checkErr(err)

    affect, err := result.RowsAffected()
    checkErr(err)

    fmt.Println(affect)
}

Temos a mesma estrutura agora porém com apenas dois argumentos no updade.Exec o body e o id da linha que queremos modificar na tabela.

O identificador no final das contas ajuda muito nas buscas quando precisamos editar algo pois é mais fácil de usar como referência.

A saida após o UPDATE na linha que acabamos de inserir na tabela, nesse caso mudamos o body.

Output:



Accessing MobyDick ... Connected!
1

Aqui vou dar mais um SELECT pra mostrar o resultado da tabela após as alterações, você pode chamar a função de sqlSelect() que foi criada, dentro das outras funções pra verificar a tabela após a modificação se quiser.

Output:



Accessing MobyDick ... Connected!
1   Golang + PostgreSQL But I must explain to you how all this mistaken idea 
5   Maps in Golang  But I must explain to you how all this mistaken idea

DELETE

O DELETE é ainda mais simples pois só precisamos do identificador para passar como referência do que queremos deletar.



DELETE FROM article WHERE id=1

"Deleta da tabela article o item de id 1"



func sqlDelete() {

    sqlStatement := fmt.Sprintf("delete from %s where id=$1", dbConfig.TableName)

    delete, err := db.Prepare(sqlStatement)
    checkErr(err)

    result, err := delete.Exec(5)
    checkErr(err)

    affect, err := result.RowsAffected()
    checkErr(err)

    fmt.Println(affect)
}

Aqui temos também o retorno de linhas afetadas e vou chamar o SELECT novamente para mostrar o estado atual da tabela.

Output:



Accessing MobyDick ... Connected!
1

Chamando o SELECT após as alterações.

Output:



Accessing MobyDick ... Connected!
1   Golang + PostgreSQL But I must explain to you how all this mistaken idea

Sobrou apenas a linha original.

Existem outras alterações com SQL que podem ser feitas com duas ou mais tabelas como JOINS, esse não é o caso então podemos deixar essa para uma proxima.

Stack

Wagner Abrantes — Thu, 15 Oct 2020 20:54:29 +0000

Uma Stack é a estrutura de "último a entrar, primeiro a sair" (last in last out), na qual os itens são adicionados a partir do topo. As stacks são usadas em parsers para resolver algoritmos de labirinto. Push, pop, top e get size são as operações típicas permitidas nas estruturas de dados da stack. Parsing de sintaxe, backtracking e gerenciamento de memória de tempo de compilação são alguns cenários da vida real onde as stacks podem ser usadas.

Nesse exemplo usando a dinâmica de um web browser vamos implementar o que seria o seistema de avançar e voltar nas paginas.

Como o ultimo item a entrar é o primeiro a sair significa que vamos gurdar URL's em uma pilha e cada vez que quisermos voltar para a página anterior seria como uma função de pop para retirar da stack o ultimo item, que seria a URL atual.

Exemplo:

Eu visiitei o "Google, Facebook, Twitter e Youtube". Então tenho uma lista onde a posição 0 é o Google e a ultima osição é o Youtube, o que seria como a URL atual e também o ultimo item que entrou na stack.

Então se eu quiser voltar na navegação do browser significa que essa operação contecerá:

Browser.pop

E o estado atual da lista seria "Google, Facebook, Twitter"

Data

A struct de página contem os dados das páginas como o nome que aparece do header da aba e o caminho relativo.
Com a struct de stack definimos o que seria a estrutura onde as paginas são armazenadas e de onde podem ser feitas as operações.

type pagina struct {
    nome string
    url  string
}

type stack struct {
    slice []pagina
}

The Push method

O método avançar que é uma representação do push adiciona uma nova página no topo da stack. O exemplo é muito simples e é praticamente o mesmo padrão usado para queues quando usamos slices.

func (navegador *stack) avancar(home pagina) {

    navegador.slice = append(navegador.slice, home)
}

Empty

Precisamos verificar se a stack está vazia antes de dar pop nela então vamos criar um método para isso.

func (navegador *stack) vazia() bool {

    return navegador.slice == nil
}

The Pop method

O método voltar na implementação da stack remove a última página do slice, esse seria analogo ao pop.

Para isso usamos a mesma operação de slice que também foi feita quando usamos queues, porém aqui retiramos os itens desde a posição 0 até o tamanho do slice - 1, mesmo falando que eu quero fatiar o slice da posição 0 a 4 ele me devolve "0,1,2,3".

Também fazemos uma checagem usando o método vazio para saber se a lista contem intens antes de utilizar o pop.

func (navegador *stack) voltar() bool {

    if navegador.vazia() {
        return false
    }

    tamanho := len(navegador.slice) - 1
    navegador.slice = navegador.slice[:tamanho]

    return true
}

The main method

Aqui instaciamos as páginas como o histórico acessado e a nossa stack como o nagevador chrome.
Depois tem um for iterando sobre os itens no historico fazendo push dos itens do historico no chrome. Como se estivessemos acessando as páginas uma depois da outra.
Vem então a chamada do pop que retira o ultimo item e fazemos o print do estado atual da stack.

func main() {

    historico := []pagina{
        {"GeeksforGeeks", "https://www.geeksforgeeks.org/"},
        {"Youtube", "https://www.youtube.com/"},
        {"Github", "https://github.com/"},
        {"Twitter", "https://twitter.com/home"},
    }

    var chrome *stack = new(stack)

    for i := range historico {
        chrome.avancar(historico[i])
    }

    fmt.Println(chrome)
    chrome.voltar()
    fmt.Println(chrome)

    fmt.Println(chrome.vazia())

}

Output:

&{[{GeeksforGeeks https://www.geeksforgeeks.org/} {Youtube https://www.youtube.com/} {Github https://github.com/} {Twitter https://twitter.com/home}]}

&{[{GeeksforGeeks https://www.geeksforgeeks.org/} {Youtube https://www.youtube.com/} {Github https://github.com/}]}

false

A primeira stack com todos os itens e a segunda depois da operação de pop e em seguida a chamada de vazio para ver o estado da stack. Que retorna false já que nossa stack ainda está populada.

Sets

Wagner Abrantes — Thu, 15 Oct 2020 20:53:19 +0000

Um Set é uma estrutura de dados linear que possui uma coleção de valores que não se repetem. Um Set pode
armazenar valores únicos sem qualquer ordem particular.

No mundo real, os Sets podem ser usados para coletar todas as tags para postagens de blog ou participantes em uma conversa de chat.

Não tem muito segredo, como queremos uma estrutura que não permita dados duplicados vamos basear a estrutura do set em uma outra estrutura do golang chamada map que é baseada em hash, um conjunto de chave valor.

Então definimos o segundo tipo de dados como boleano, assim sendo possível fazer comparações de true e false entre os valores.

type Set struct {
    estrutura map[int]bool
}

func (set *Set) Criar() {
    set.estrutura = make(map[int]bool)
}

The insert method

O método AddValor adiciona o valor a um Set.

Aproveitados a o método PossuiValor para verificar se existe o valor dentro do set.
Se o resultado do método não for verdadeiro então set.estrutura recebe valor e definimos o segundo parâmetro do map como true.

func (set *Set) AddValor(valor int) {

    if !set.PossuiValor(valor) {
        set.estrutura[valor] = true
    }
}

The delete method

Aqui é reaproveitado o delete do próprio map da sdtlib do Golang então a implementação é mínima.

func (set *Set) DeletaValor(valor int) {

    delete(set.estrutura, valor)
}

The lookup method

O método PossuiValor do Set verifica se o valor existe ou não em set.estrutura e retorna um boolean com a resposta.

Definimos localizado como um boolean, o zaro value dele é false

Esse underline cheguei a comentar antes, mas ele anula o valor de uma variável, no caso aqui ele é anula o valor inteiro de set.estrutura para que a comparação possa ser feita apenas com o os boleanos.

func (set *Set) PossuiValor(valor int) bool {

    var localizado bool

    _, localizado = set.estrutura[valor]

    return localizado
}

The InterSect method

No código a seguir, o método CruzarCom retorna um setCruzado que consiste na interseção de set e setDiferente.

Instanciamos um set que será o retorno da interseção, em seguida fazemos um loop ao longo da estrutura já existente verificando apenas os valores, e anulando o segundo parâmetro do map que seria o boleano.

Reaproveitamos o método PossuiValor no parâmetro para fazer a comparação e com o valor da condição reutilizamos AddValor para inserir o valor no set que instanciamos.

func (set *Set) CruzarCom(setDiferente *Set) *Set {

    var setCruzado = &Set{}
    setCruzado.Criar()
    var valor int

    for valor, _ = range set.estrutura {

        if setDiferente.PossuiValor(valor) {

            setCruzado.AddValor(valor)
        }
    }

    return setCruzado
}

The Union method

O método UnirCom retorna um setReunido que consiste em uma união de set e setDiferente.

Instanciamos setReunido que será o retorno. E reutilizamos AddValor percorrendo o set original e o set no parâmetro inserindo os valores no set instanciado.

func (set *Set) UnirCom(setDiferente *Set) *Set {

    var setReunido = &Set{}
    setReunido.Criar()
    var valor int

    for valor, _ = range set.estrutura {
        setReunido.AddValor(valor)
    }

    for valor, _ = range setDiferente.estrutura {
        setReunido.AddValor(valor)
    }

    return setReunido
}

The main method

Utilizando a estrutura set na main func.

func main() {

    var set *Set
    set = &Set{}

    set.Criar()

    set.AddValor(1)
    set.AddValor(2)

    fmt.Println("set inicial", set)
    fmt.Println(set.PossuiValor(1))

    var setDiferente *Set
    setDiferente = &Set{}

    setDiferente.Criar()
    setDiferente.AddValor(2)
    setDiferente.AddValor(4)
    setDiferente.AddValor(5)

    fmt.Println("outro set", set)

    fmt.Println("cruzamento de sets", set.CruzarCom(setDiferente))

    fmt.Println("união de sets", set.UnirCom(setDiferente))

}

Output:

set inicial &{map[1:true 2:true]}
true
outro set &{map[1:true 2:true]}
cruzamento de sets &{map[2:true]}
união de sets &{map[1:true 2:true 4:true 5:true]}

Queues

Wagner Abrantes — Thu, 15 Oct 2020 20:52:11 +0000

Uma queue consiste em elementos a serem processados em uma ordem específica ou com base na prioridade.

Operações como enqueue (entra na fila), dequeue (sai da fila) e peek (observar fila) podem ser executadas na queue.
A queue é um estrutura de dados linear e uma coleção sequencial.

Os elementos são adicionados ao final e são removido do início da coleção. As queues são comuns para armazenar tasks, ou requisições HTTP que precisam ser processadas por um servidor.
Tratamento de interrupções em real-time systems, call handling e scheduling de tasks de CPU
são bons exemplos de uso de queues.

Queues podem ser implementadas de formas diferentes, isso vai depender do propósito.

ROLL THE DICE

Um bom exemplo de como funciona uma queue é pensar num jogo de rpg, geralmente quando vamos iniciar uma batalha precisamos jogar os dados e definir através do resultado quem tem mais pontos de iniciativa, e baseado na iniciativa sabemos a ordem de cada personagem atuar.
Faz um bom tempo que não jogo então não lembro tão bem, mas acho que a iniciativa é baseada em quem tirar o menor número no dado, mas talvez isso possa variar.

Então o primeiro na fila é o primeiro a atuar e também o primeiro a sair da fila dando lugar para o próximo. O primeiro da fila é o primeiro a sair dela. First In First Out (FIFO).

Já em rpgs eletrônicos com batalhas de turno se define o primeiro da fila como aquele que tem o maior numero no stat de agility, speed ou move.

Personagens

Vou dar um exemplo de uma queue bem simples, aqui vou definir os dados de personagens do rpg.

type personagem struct {
    nome string
    mov  int
}

Queue

Essa aqui é a queue, vou usar um slice mas queues são implementadas de diferentes formas, essa é para se ter uma introdução.

type queue struct {
    slice []personagem
}

Ordenando o Turno

Esse é um sort customizado que é possível de ser feito em Go, ele não é necessário para se fazer uma queue, mas nesse exemplo eu quero utilizar o sort para ordenar um slice de personagens baseado no atributo de movimento, fazendo com que o personagem que tenha o maior nível nesse atributo possa entrar na fila primeiro.

Geralmente eu não gosto de usar parâmetros como (i, j, a, k) mas como esse sort vem da documentação padrão então vou deixá-lo como na documentação, pois ele não é o foco nesse caso.

type primeiroDaFila []personagem

func (a primeiroDaFila) Len() int           { return len(a) }
func (a primeiroDaFila) Less(i, j int) bool { return a[i].mov > a[j].mov }
func (a primeiroDaFila) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

FIFO enqueue/dequeue

Esses aqui são os métodos que mencionei no inicio enqueue insere um personagem na queue, dequeue retira o primeiro personagem da queue.

Caso não tenha familiaridade com Go talvez você tenha estranhado essa parte (fila.slice[1:len(fila.slice)]) essa é uma operação de slicing, [1:] significa: "eu quero tudo que está do index 1 até, o limite do slice = len(fila.slice)" Excluindo o index 0.

O dequeue não leva parametros justamente porque a ideia da queue não é escolher quem retirar da fila então só retornamos o personagem removido.

func (fila *queue) enqueue(nome personagem) {

    fila.slice = append(fila.slice, nome)
}

func (fila *queue) dequeue() personagem {

    removido := fila.slice[0]
    fila.slice = fila.slice[1:len(fila.slice)]

    return removido
}

Iniciando o Turno

Agora na func main é hora de fazer isso tudo funcionar, criamos uma instância de personagens e uma fila, em seguida usamos a função de ordenação para que essa lista fique na ordem em que o personagem com maior nível de movimento esteja na primeira posição.

Fazemos uma iteração para inserir na fila todos os personagens que foram ordenados.

func main() {

    equipe := []personagem{
        {"Saravasti", 4},
        {"Athena", 4},
        {"Argath", 5},
    }

    var fila *queue = new(queue)

    sort.Sort(primeiroDaFila(equipe))

    for i := range equipe {
        fila.enqueue(equipe[i])
    }

    fmt.Println(fila)
    fila.dequeue()
    fmt.Println(fila)

}

Aqui tem a primeira saída mostrando a fila ordenada.

&{[{Argath 5} {Saravasti 4} {Athena 4}]}

Uma chamada para o método dequeue, para que o primeiro personagem após realizar sua ação dê seu lugar ao próximo personagem com maior atributo de movimento, e a saída mostrando a fila depois do dequeue.

&{[{Saravasti 4} {Athena 4}]}

Doubly Linked List

Wagner Abrantes — Thu, 15 Oct 2020 20:50:59 +0000

Em uma Doubly Linked List, (que a partir de agora vou chamar de DLL) todos os nodes têm um ponteiro para o node ao qual estão conectados.
Isso significa que cada node está conectado a dois nodes, e podemos avançar para o próximo node ou retroceder até o node anterior.

DLL permitem operações de insert, deleting e, obviamente, de traversing.

E Para fins de manter o exemplo de linhas temos agora o que seria uma representação de estações de trem.
Enquanto que a single linked list representa um monotrilho aqui temos duas ligações.

Quem nunca voltou da paulista mais loco e que o coringa chegou na consolação e se perguntou "o meu é sentido vila madalena ou é sentido vila prudente? E o sentido da vida?"

Listas duplamente ligadas são exatamente iguais a estações de metrô pois através de um Node você pode seguir para o próximo ou para o anterior pois temos ponteiros nas duas direções.

// Estacao struct = Node
type Estacao struct {
    // property
    nome string
    // nextNode
    estacaoSeguinte *Estacao
    // previousNode
    estacaoAnterior *Estacao
}

Assim como na single LinkedList temos o mesmo conceito de head e tail então a struct é exatamente igual.

// Metro = Doubly linked list
type Metro struct {
    // head
    inicioDaLinha *Estacao
    // tail
    finalDaLinha *Estacao
}

Node Between Values

O método EntreDuasEstacoes do Metro retorna a Estacao que tem um nome situado entre os valores anterior e proxima. O método percorre a lista para descobrir se as strings anterior e proxima correspondem em Nodes consecutivos.

func (linhaVerde *Metro) EntreDuasEstacoes(anterior string, proxima string) *Estacao {

    var estacao *Estacao
    var estacaoAtual *Estacao

    for estacao = linhaVerde.inicioDaLinha; estacao != nil; estacao = estacao.estacaoSeguinte {

        if estacao.estacaoAnterior != nil && estacao.estacaoSeguinte != nil {

            if estacao.estacaoAnterior.nome == anterior && estacao.estacaoSeguinte.nome == proxima {
                estacaoAtual = estacao
                break
            }
        }
    }
    return estacaoAtual
}

Primeiro instanciamos o Node fazemos um for para percorrer os itens do head ao tail enquanto estacao for diferente de nil. Em seguida uma comparação com os parâmetros anterior e proxima feitos com o tail e head para reconhecer o node entre eles, sendo que a comparação é feita somente se head e tail forem diferentes de nil.

The AddToHead method

O método AddInicioDaLinha define o head para que possamos seguir construindo mais estacões assim como fizemos com o monotrilho.

func (linhaVerde *Metro) AddInicioDaLinha(novaEstacao string) {

    var estacao = &Estacao{}
    estacao.nome = novaEstacao
    estacao.estacaoSeguinte = nil

    if linhaVerde.inicioDaLinha != nil {

        estacao.estacaoSeguinte = linhaVerde.inicioDaLinha
        linhaVerde.inicioDaLinha.estacaoAnterior = estacao
    }
    linhaVerde.inicioDaLinha = estacao
}

AddAfter method

Aqui fazemos um insert de um node após outro node que é passado como parâmetro presente na lista, e para saber se o Node está presente reutilizamos o método ProcuraEstacao() que havíamos feito para a Single Linkedlist.

func (linhaVerde *Metro) AddEstacaoSeguinte(destino string, novaEstacao string) {

    var estacao = &Estacao{}
    estacao.nome = novaEstacao
    estacao.estacaoSeguinte = nil

    var estacaoAtual *Estacao
    estacaoAtual = linhaVerde.ProcuraEstacao(destino)

    if estacaoAtual != nil {

        estacao.estacaoSeguinte = estacaoAtual.estacaoSeguinte
        estacao.estacaoAnterior = estacaoAtual
        estacaoAtual.estacaoSeguinte = estacao
    }
}

Fazemos a instância do Node atribuímos o nome usado como parâmetro e setamos o node seguinte como nil para que se mantenha o conceito de tail.

Fazemos a busca e recuperamos a localização do Node de referência como estacaoAtual.

Então a estacao seguinte do node atual para a ser a estacao seguinte do node recuperado (mindfuck)
Parece um malabarismo de valores e é na verdade isso mesmo, talvez por isso pareça complicado mas basta trackear onde estão os valores e prestar atenção por onde eles estão passando.

The AddToEnd method

AddEstacaoNoFinalDaLinha cujo o nome é bastante descritivo, faz uma nova instância de um node e reutiliza o método UltimaEstacao() para recuperar o ultimo node e passar o valor do Node instanciado como referencia através de ponteiro.

func (linhaVerde *Metro) AddEstacaoNoFinalDaLinha(novaEstacao string) {

    var estacao = &Estacao{}
    estacao.nome = novaEstacao
    estacao.estacaoSeguinte = nil

    var fimDaLinha *Estacao
    fimDaLinha = linhaVerde.UltimaEstacao()

    if fimDaLinha != nil {

        fimDaLinha.estacaoSeguinte = estacao
        estacao.estacaoAnterior = fimDaLinha
    }
}

Main Func

Aqui vou fazer o mesmo processo que usei com o monotrilho pra popular a DLL, e além desses métodos no arquivo doubly.go no repositório tem mais exemplos de métodos para DLL e os métodos reaproveitados da Single Linked List.

func main() {
    var linhaVerde Metro
    linhaVerde = Metro{}

    estacoes := []string{"Tamanduateí", "Sacomã", "Alto do Ipiranga", "Santos-Imigrantes", "Chácara Klabin",
        "Ana Rosa", "Paraíso", "Brigadeiro", "Trianon-MASP", "Consolação", "Clínicas",
        "Sumaré", "Vila Madalena",
    }

    linhaVerde.AddinicioDaLinha("Vila Prudente")
    for i := range estacoes {
        linhaVerde.AddEstacaoNoFinalDaLinha(estacoes[i])
    }

    linhaVerde.ListarEstacoes()
}

Output:

Vila Prudente
Tamanduateí
Sacomã
Alto do Ipiranga
Santos-Imigrantes
Chácara Klabin
Ana Rosa
Paraíso
Brigadeiro
Trianon-MASP
Consolação
Clínicas
Sumaré
Vila Madalena

Doubly vs Single

Vantagens sobre a single linked list

Uma DLL pode ser percorrida de trás para frente e vice versa.
A operação de delete na DLL é mais eficiente se o ponteiro para o node excluído for fornecido.
Podemos usar insert mais rapidamente em referencia a um item tanto a frente quanto trás.
Na SLL (single linked list), para excluir um node, é necessário um ponteiro para o node anterior. Para obter esse node anterior, às vezes a lista precisa ser percorrida. Na DLL, podemos obter o node anterior usando o ponteiro anterior.

Desvantagens sobre a singly linked list

Cada node da DLL requer espaço extra para um ponteiro anterior. (ainda assim é possível criar uma DLL sem um segundo ponteiro.)
Todas as operações requerem um ponteiro extra para ser mantida. Por exemplo, no insert, precisamos modificar os ponteiros anteriores junto com os próximos ponteiros.

Single Linked Lists

Wagner Abrantes — Thu, 15 Oct 2020 20:49:10 +0000

Você pode chamar de lista ligada, lista encadeada, eu vou chamar de linked list.

A grande diferença linked list e arrays é que linked list não são indexadas, não tem como buscar o sexto elemento, ou o segundo e etc. A linked list funciona como estações do monotrilho, onde cada estação é um valor e existe uma conexão entre uma estação e outra, formando uma linha.

E por isso podemos declarar a Linked list como uma estrutura de dados linear.

O exemplo com o monotrilho é bem específico exatamente porque vou falar de doubly linked list também e essa tem mais a ver com linhas de metrô.

N_a linked list_ cada Node ou nó irá representar uma estação, cada node tem uma propriedade que pode ser um int, string ou qualquer outro tipo. Nesse caso será uma string e a propriedade são as estações do monotrilho.

A segunda parte de um Node é um ponteiro que faz a ligação apontando para o próximo node, no nosso exemplo, a próxima estação, criando assim uma ligação entre todos os nós.

No nosso exemplo enquanto os Nodes são as estações, o Monotrilho vai representar a própria linked list.

Outras duas partes importante nas linked list são o headNode e o tail o head é o primeiro item que entra na lista e o tail o último, no caso do tail o pointer dele aponta para nil, o que representa o fim da lista. Essas duas partes também são importantes pois são referência para a criação dos métodos que precisaremos usar na linked list.

Claro que uma estrutura da de dados não é nada seus seus métodos, e vamos implementá-los aqui. Para entender por completo é necessário que você saiba como usar ponteiros, então vou deixar alguns recursos aqui pra você consultar antes de começar a falar de código.

Go by Example: Pointers

Aprenda Go: O que são ponteiros?

A estrutura

O struct Estação é o que vai representar os nós dessa Linked List, então temos a propriedade que é o valor nome e proximaEstacao que faz a ligação entre os nós apontando para o próximo Node.

Com a struct Monotrilho temos agora como setar a primeiraEstacao (head) que é onde começa a linked list, então primeiraEstacao vai apontar para Estacao (Node) que é onde fica a proximaEstacao.

Adicionar um head

O método AddPrimeiraEstacao vai adicionar um valor ao primeiro Node que é primeiraEstacao.

AddPrimeiraEstacao usa a struct Monotrilho como receiver e possui um parâmetro string. Instanciamos Estacao e atribuímos o parâmetro a propriedade nome.

Agora linha.primeiraEstacao recebe a referencia de memória presente na Estacao instanciada.

IterateList

Basicamente o que faríamos com um for statement em um array porém usando as propriedades das structs para percorrer a lista de Estações.

Enquanto a Estacao instanciada for diferente de nil (representação do fim da lista) estacao é igual a proximaEstacao análogo ao i++.

LastNode

O método UltimaEstacao do Monotrilho retorna o node no final da linha. A linha é percorrida para verificar se proximaEstacao é nil caso seja a variável ultimaEstacao recebe o valor atual de estacao feito no for.

AddToEnd

O método AdicionaEstacao adiciona um node no final da linha.

Primeiro buildamos um Node, nome = parâmetro e o proximaEstacao que recebe nil pois como essa estação é adicionada no final da linha ela precisa ser um tail.

Em seguida encontramos o fim da linha atual reutilizando UltimaEstacao() o método criado anteriormente e setamos seu valor com o a estacao criada.

NodeWithValue

O método ProcuraEstacao do Monotrilho retorna o node com o valor do parâmetro. A lista é percorrida e verificada para ver se o valor da propriedade é igual ao parâmetro caso contrário retorna nil.

AddAfter

O método AddProximaEstacao adiciona um Node após uma Estacao específica.

O método AddProximaEstacao do Monotrilho possui dois parâmetros, onde o primeiro é o node de referencia e o segundo o novo node a ser adicionado na posição seguinte a referência.

Uma estacao com o valor nomeDaEstacaoAnterior é recuperada reutilizando o método ProcuraEstacao().

Um node (parâmetro 2) é criado e adicionada após o retorno de ProcuraEstacao().

RemoveNode

O método RemoveEstacao verifica se o primeiraEstacao é nil, caso o Monotrilho esteja vazio.

Em seguida se a propriedade do primeiraEstacao for a mesma do parâmetro então proximaEstacao é movido para primeiraEstacao assim ocupando a posição do Node removido.

Em seguida uma nova condição onde estacaoAtual é setada como head para que possamos verificar os itens além da primeiraEstacao e assim caso seja encontrado fazemos a atribuição para a esquerda novamente alocando os nodes seguintes a posição do node removido.

SizeList

TamanhoDaLinha faz o mesmo papel que len() em estruturas de array retornando a quantidade de Nodes presentes no Monotrilho.

FuncMain

Depois disso tudo você pode utilizar os métodos para construir a sua LinkedList como preferir.

Output

<<<<<<< HEAD

A versão em código no repositório não utiliza a os mesmos exemplos com o Monotrilho, os nomes no arquivo original contam com os nomes comuns usados na estrutura de LinkeList.

LinkedList vs Arrays

Um array é a estrutura de dados que contém uma coleção de elementos de dados de tipo semelhante, enquanto a linked list é considerada como uma estrutura de dados não primitiva contém uma coleção de elementos vinculados não ordenados conhecidos como nodes.
No array, os elementos pertencem a índices, ou seja, se você deseja o quarto elemento, deve escrever o nome da variável com seu índice ou localização dentro do colchete.
Em uma linked list, porém, você tem que começar do head e ir trabalhando até chegar ao quarto elemento. O acesso a um elemento em um array é rápido, enquanto a linked list leva um tempo linear, portanto, é um pouco mais lento.
Operações como insert e delete em arrays consomem muito tempo. Por outro lado, o desempenho dessas operações em linked lists é rápido.
Arrays são de tamanho fixo. Em contraste, as linked lists são dinâmicas e flexíveis e podem expandir e diminuir seu tamanho.
Em um array, a memória é atribuída durante o tempo de compilação, enquanto uma linked list é alocada em tempo de execução.
Os elementos são armazenados consecutivamente na memória com arrays, enquanto que são armazenados aleatoriamente em linked lists.

Tudo em relação as estruturas terão tradeoff então a aplicação de cada uma vai depender da necessidade do desenvolvedor.

Resolução de Problemas

Wagner Abrantes — Thu, 15 Oct 2020 20:46:52 +0000

Dicas e padrões para problem solving

Como funciona um algoritmo

A questão é que para entender como resolver algoritmos temos que primeiro entender o que são.
E a definição mais simples que se encontra em qualquer lugar é que Algoritmos são compostos de passos lógicos para resolver um problema.

Apesar de ser simples esquecemos disso as vezes! Por exemplo quando deixamos de pensar realmente nos passos que o algoritmo excuta deixamos de entender a sua propria lógica.

Em uma busca linear nós simplesmente pensamos, ok vamos fazer um for e procurar o parametro.
Se pensarmos na lógica é como se indice fosse um carteiro e ele tem que entregar uma carta na casa do pedro e as casas estão dentro do array.
E ai o carteiro vai passando de casa em casa

0- "É aqui que mora o Pedro?"
"não"
1- "É aqui que mora o Pedro?"
"não"
2- "É aqui que mora o Pedro?"
"não"
3- "É aqui que mora o Pedro?"
"não"
4- "É aqui que mora o Pedro?"
"sim"
"Essa carta é pra você"

Bem engraçado, mas é isso que um loop ta fazendo e nós já sabemos disso. A questão é que em certo momento a gente deixa de se preocupar, porque é tão bobo, só que quando aparece um desafio e a gente ta preocupado com alto nível a nossa cabeça meio que da um tilt.

Isso é muito comum, e se você tem dificuldade para resolver problemas com algoritmos possivelmente é porque você nunca foi cobrado por isso, não era uma questão entre conseguir ou não uma vaga. Também porque a maioria das empresas fazem seus testes baseados na premissa de que vão contratar pessoas já formadas então é pressuposto que esse tipo de conhecimento ja tenha sido aprendido.

E a diferença entre você e uma pessoa que resolve problemas com facilidade não é que ela tem um cerebro superior, é só que ela se propos a resolver mais problemas que você. Então a questão toda é prática.
Da mesma forma a gente pode comparar alguem que já deu umas 10 palestras em meetups e outra que vai palestrar pela primeira vez, a primeira não é um ser superior inalcançavel, para de ficar endeusando qualquer um a troco de nada.

Como Solucionar um problema que eu não conheço?

O primeiro problema sempre vai ser muito dificil, o segundo ainda mais. Só que existem algumas estratégias que ajudam a gente a resolver esses problema e podemos fazer uso delas para que essa trajetória não seja tão desgastante.

Então baseado nisso podemos:

Criar um plano para resolução de problemas
Dominar padrões para solução de problemas simples

Quando já temos uma ideia de abordagem para resolver problemas as coias se tornam um pouquinho mais simples. Não se trata de algo milagroso que vai resolver o problema pra você, a tarefa ainda é nossa, mas pelo menos ficamos mais relaxados e conseguimos lidar melhor com a ansiedade durantes um teste.

Primeiro:

Entenda o problema
Decompor
Resolva
Refatore

Entenda o problema

Parece bobo, mas a maioria dos problemas que resolvemos são problemas que já conhecemos e se já conhecemos já sabemos como resolver.
Se alguém nos da um problema que nunca vimos e não fazemos nem ideia de por onde começar, o que faríamos?

Então nesse momento o que precisamos fazer é dar um passo para trás, soltar o teclado e pensar no problema.
A maior parte do stress no trabalho vem das pessoas que se colocam no meio de vários problemas e ela fica tão desnorteada que acaba ficando irritada e até agressiva com toda a frustração.

O melhor nesses casos é sair de onde está o problema, o ambiente é consimido pelo problema pois as pessoas se deixam consumir pelo problema. Então nos momentos de stress o ideal é nos levantarmos, beber um café uma água e pensar no problema fora do ambiente onde ele está sendo discutido.

Agora dando minha opnião, esse é um dos grandes motivos para reuniões serem desastres quando temos problemas sérios. Quando tudo está funcionando a reunião é completamente amigável todos contribuem com coisas que não precisamos no momento, e quando a coisa aperta e as reuniões tem uma atmosfera ruim dificilmente alguém vira com uma ideia que partiu dessa reunião.

Isso serve um pouco pra algoritmos mas também pra vida pessoal, não deixemos nos levar pelo clima que é gerado no ambiente se tem 10 pessoas usando o metodo Y pra resolver X e não ta funcionado porque 11 + Y resolveria X?

Pra saber se conseguimos entender o problema algumas perguntas podem ser feitas:

Eu consigo explicar o problema com as minhas proprias palavras?
Quais os inputs são feitos ao problema?
Qual o output é esperado? Como ele se parece? Qual o seu tipo?
O output é determinado pelo input?
Como eu posso nomear os dados que fazem parte do problema?

Decompor

Se um algoritmo é uma sequencia de passos lógicos finitos, uma boa ideia para resolver um problma que não conhecemos é decompor os passos lógicos como se já tivessemos o algoritimo pronto e fossemos tirando pedaço a pedaço e analisando um por um.

Geralmente em uma entrevista quando o entrevistador passa um challenge ele quer que expliquemos as suas ações para entender a nossa linha de raciocinio como programador, então é bom manter um nivel de comunicação enquanto se resolve o problema, explicando os passos lógicos que pretendemos tomar.

Isso nos ajuda a pensar no código antes mesmo de escrevê-lo e durante essa decomposição podemos acabar diferenciando quais são os passos que, "já sei como vou fazer isso" dos "não sei nem por onde começar".

Resolva

Agora que já temos um plano e uma linha de raciocinio já vale a pena começar a escrever código. Não dá pra sair escrevendo qualquer coisa e achar que vai resolver na sorte, isso já não funciona nem no dia a dia imagine em uma entrevista onde o tempo é curto.

Refatore

Com o problema resolvido já da pra fazer algumas perguntas, a complexidade ta lega? Eu escolhi bons nomes para as variáveis? Tá legível o negócio? Caso não esteja de uma revisada pra deixar a solução bacana.

ABORDAGENS

Brute Force

Um algoritmo de força bruta resolve um problema com base na sua própria declaração e definição como ordenação e busca. Um algoritmo de força bruta pode ser uma pesquisa exaustiva onde a solução está na propridade de um conjunto. Talvez você lembre do termo de brute force baseado em "brute force attack" que tem a ver com a quebra de senhas através da abordagem de tentativa e erro. Apesar das abordagens serem parecidas a usabilidade é diferente.

Ela acaba sendo exaustiva pois o numero de processamentos feitos para ser realizado é muito grande. Como o exemplo do carteiro.

Algoritmos de força bruta são conhecidos por sua ampla aplicabilidade e simplicidade na resolução de problemas complexos. Busca, string matching e multiplicação de matrizes são alguns cenários onde eles são usados.
Apesar de resolverem diversos problemas e serem de fácil implementação podem ser muito pouco performáticos.

A representação de um algoritmo de força bruta é mostrada no seguinte código:


package main

import (
    "fmt"
)

func encontraElemento(arr [10]int, elemento int) bool {
    for i := range arr {
        if arr[i] == elemento {
            return true
        }
    }
    return false
}

func main() {
    var arr = [10]int{1, 4, 7, 8, 3, 9, 2, 4, 1, 8}
    var tentativa bool = encontraElemento(arr, 10)
    fmt.Println(tentativa)
    var tentativa2 bool = encontraElemento(arr, 9)
    fmt.Println(tentativa2)
}

Essa é uma busca linear e como no exemplo do carteiro ela passa por todos os elementos do array por isso é considerada brute force pois ela exerce o número máximo de operações até chegar no objetivo o que tem bastante a ver com a questão de Big O que abordei anteriormente sobre o pior caso.

Aqui tem um vídeo do programação dinâmica falando um pouco sobre com o exemplo do handshake

https://youtu.be/tnb2V7h4Fa4

Divide and conquer algorithms

Um algoritmo de divisão e conquista divide um problema complexo em problemas menores e
resolve esses problemas menores. O problema menor será subdividido até que seja resolvido.

Esta abordagem pode ser dividida nas seguintes partes:

Divide: Envolve dividir o problema em algum subproblema.
Conquiste: Subproblema chamando recursivamente até que o subproblema seja resolvido.
Combine: O Sub problema foi resolvido para que possamos encontrar a solução do problema.

Se lembrarmos do exemplo de busca binária do tweet anterior sobre Big O Notation a ideia aqui é a mesma dividir e conquistar, utilizando a recursão.

Recursão, quick sort, binary search e merge sort são bons exemplos de algoritmos de dividir e conquistar.
A memória é usada de forma eficiente com estes algoritmos.


package main

import (
    "fmt"
)

Conforme mostrado no código a seguir, o método Fibonacci leva o parâmetro inteiro numero e
retorna o Fibonacci para numero usando recursão.

Caso não lembre a formula da sequencia fibonacci: Fn = Fn-1 + Fn-2
O Fibonacci de 9 é 55 pois 144 e 89 são os próximos números na sequencia.

Usando um loop aqui gerando uma sequência de 10 números fibonacci.


func fibonacci(numero int) int {
    if numero <= 1 {
        return 1
    }
    return fibonacci(numero-1) + fibonacci(numero-2)
}

func main() {
    for i := 0; i < 10; i++ {
        fmt.Println(fibonacci(i))
    }
}

Backtracking algorithms

Backtracking é uma técnica algorítmica para resolver problemas recursivamente, tentando construir uma solução de forma incremental, uma peça de cada vez, removendo as soluções que falham em satisfazer as restrições do problema.

A seguir um exemplo de um algoritmo de backtracking. Onde problema é identificar combinações de elementos em uma matriz de 10 elementos cuja soma é igual a 18.
O método combinacaoDeSoma tenta recursivamente encontrar a combinação. Sempre que
soma vai além da meta chave, ele volta atrás:


package main

import (
    "fmt"
)

func main() {
    var arr = [10]int{1, 4, 7, 8, 3, 9, 2, 4, 1, 8}
    var chave int = 18
    var combinacoes [19]int
    combinacaoDeSoma(arr, combinacoes, len(arr), chave, 0, 0, 0)
}

func combinacaoDeSoma(arr [10]int, combinacoes [19]int, tamanho int, chave int, addValor int, l int, m int) int {
    numero := 0

    if addValor > chave {
        return -1
    }

    if addValor == chave {
        numero = numero + 1
        for p := 0; p < m; p++ {
            fmt.Printf("%d,", arr[combinacoes[p]])
        }
        fmt.Println(" ")
    }

    for i := l; i < tamanho; i++ {
        combinacoes[m] = l
        combinacaoDeSoma(arr, combinacoes, tamanho, chave, addValor+arr[i], l, m+1)
        l = l + 1
    }
    return numero
}

Ainda falaremos mais sobre backtracing.

Quais habilidades o entrevistador procura?

Se pensarmos pelo ponto de vista do entrevistador em um code challenge quais seriam as habilidades que eles prestariam atenção?

Habilidade de Análise - Não querem que apenas resolvamos o problema e vamos embora, querem saber como pensamos no problema. Então é importante dizer os passos lógicos enquanto pensa na solução assim eles podem entender como é o nosso raciocinio.

Código - Essa já é uma questão mais próxima do que estamos acostumados, nosso código é bem escrito? Limpo e organizado ou legivel?

comunicação - Durante a analise como nos comunicamos? fazemos perguntas pertinentes? O perfil bate com a cultura da empresa?

O passo a passo através de um problema.

Quando o entrevistador explicar o desafio, anote os pontos chave para que você consiga interpretar a sua forma e assim compreender melhor o problema. Mostre como você organiza seu pensamento.
Tenha total compreensão de quais são os inputs e outputs, se não tiver certeza pergunte.
Qual é o valor mais importante do problema? Você tem tempo, espaço e memória, etc. Qual é o objetivo principal?
Não faça perguntas demais, pode ser um pouco irritante.
Comece com a abordagem ingênua / força bruta. Geralmente a primeira solução que vem na cabeça, e fale sobre ela, não precisa necessáriamente escrever a implementação.
Diga por que essa abordagem não é a melhor (ou seja, O(n^ 2) ou superior, não legível, etc ...)
Percorra sua abordagem, comente coisas e veja onde você pode quebrar coisas. Qualquer repetição, gargalos como O (N^ 2) ou trabalho desnecessário? Você usou todas as informações disponíveis? Gargalo é a parte do código com o maior Big O.
Antes de começar a codificar, analise seu código e anote as etapas que você pretende fazer.
Modularize seu código desde o início. Divida seu código em pedaços pequenos e adicione apenas comentários, se necessário.
Comece realmente a escrever seu código agora. Tenha em mente que quanto mais você se prepara e entende o que você precisa codificar, melhor será o whiteboard. Portanto, nunca comece a codar sem ter certeza de como as coisas vão funcionar. Essa é uma receita para o desastre.
Pense nas verificações de erro e como você pode quebrar esse código. Nunca faça suposições sobre o input. Suponha que as pessoas estão tentando quebrar seu código. Como você o protegerá? Dica: Comente no código, as verificações que deseja fazer ... escreva a função e diga ao entrevistador que você escreveria testes agora para fazer sua função falhar (mas você não precisará realmente escrever os testes caso tenha pouco tempo).
Não use nomes ruins/confusos como i e j. Escreva um código legivél.
Teste seu código: verifique se há parâmetros, 0, indefinido, nulo, matrizes massivas, código assíncrono, etc ... Pergunte ao entrevistador se pudermos fazer suposições sobre o código. Você pode fazer a resposta retornar um erro?
Se o seu entrevistador estiver satisfeito com a solução, a entrevista geralmente termina aqui.

Verificação de código:

[✅] Funciona
[✅] Bom uso de estruturas de dados
[✅] Reutilizar código/não se repetir
[✅] Modular - torna o código mais legível, sustentável e testável
[✅] Menor que O (N^ 2). Queremos evitar loops aninhados, se possível, pois eles são caros.
[✅] Baixa complexidade de espaço -> Recursão pode causar stackoverflow, a cópia de matrizes grandes pode
exceder a memória da máquina.

Essas dicas são mais valiosas para entrevistas em empresas como o Google, Amazon, Facebook e etc, pois é mais comum que eles utilizem estrutura de dados e algoritmos como foco da entrevista, no restante das empresas a solução varia de acordo com o segmento. Mas se temos dominio nesse nível é muito provável que consigamos lidar com testes de outras empresas.

Essas são dicas interessantes e que são possíveis de praticar em diversas plataformas de code Challenge como o HackerRank por exemplo. A ideia toda aqui é nos fazer passar por problemas de algoritmos que não sabemos a resposta mas que temos as ferramentas necessárias para ler o enunciado, interpretar e pensar na nossa própria solução antes de procurar uma explicação no google.

Se olharmos pra um desafio, sentirmos que não sabeamos como resolver mas não despendemos de um tempo pra pelo menos pensar em uma solução e procuramos tutoriais no google pra que expliquem como chegaram naquela resposta é meio que terceirizar nosso cerebro pro google e da forma que eu to falando parece até que eu sou o mestre dos code challenges, mas não eu me sinto tão desconfortável pensando em uma resolução quanto você.

Você não é uma fraude por não conseguir resolver X problema, isso tudo é um processo pra mim e pra você e logo mais vamos estar ajudando outras pessoas a resolverem esses problemas.

Recursions & Dragons

Wagner Abrantes — Thu, 15 Oct 2020 20:44:39 +0000

Recursão da forma mais simples que dá pra explicar

Intro

Sabe aquelas coisas que todo mundo diz, “isso é muito simples depois que você entende”.

E eu fico tipo??? Óbvio né kkkk

Esse é outro assunto que nós só entendemos depois que a ficha cai, recursão.

Junto com esse conteúdo uma outra parte já está no repositório sobre problem solving porém apenas esse será em formato de thread alguns padrões de problem solving envolvem o uso de recursão então é uma boa ideia ler os dois em sequência.

A recursão é antes de qualquer coisa uma forma diferente de pensar em soluções. A principio pode ser uma dor de cabeça para se acostumar, mas depois que vira uma segunda natureza você visualiza a programação de uma nova forma, meio que análogo aquele “click” que cheguei a comentar quando falei sobre Big O Notation.

Talvez seja desmotivante, mas se você ainda não sabe recursão, pode ser que leve até algumas semanas pra cair a ficha então é recomendado absorver muito conteúdo, não é um artigo que vai esclarecer todas as nossas dúvidas.

Bora de lado essa coisa de ficar comprando curso “Ultimate”, “Premium”, “Advanced”.

Parte do processo de estudar é aprender a procurar recursos interessantes e aprender com mais de um se possível ou viável.

Ter muito mais do que apenas um ponto de vista sobre o mesmo assunto nos ajuda a ter o nosso próprio. Essa é uma dificuldade muito grande pra maioria visto que desde o nosso ensino fundamental todo o conteúdo é pré definido, e por isso existe essa ânsia de comprar o “melhor” curso ou o mais completo, porque a gente precisa do material pronto na nossa mão ninguém ensinou a gente a fazer pesquisa.

Pensando nesse caso tenho aqui um repositório interessante com boas dicas de como pesquisar melhor e tirar dúvidas sobre programação.

Joga No Google

Se puder contribuir também vai ser muito bom.

Mesmo que termine esse artigo sem entender recursão e eu espero que não, não desista, corre atrás que tem muita coisa interessante na web sobre isso e quem sabe exista um conteúdo na medida.

Definindo recursão em três partes

A - Repetição, a recursão é uma repetição infinita. Como um loop, mas por debaixo dos panos a implementação é diferente.

B - Endpoint, a recursão precisa de uma resolução chamada geralmente de caso base para que o algoritmo se resolva e a repetição termine.

C -Operações, aplicando a recursão sem nenhuma operação ele é inútil então é necessário algum tipo de lógica que defina a recursão para que durante a repetição das chamadas essa lógica se aplique e o algoritmo chegue ao caso base.

Caverna do Dragão

Hank, Erick, Diana, Sheila, Presto e Bobby conversam com o mestre dos magos.

“Para achar o caminho de casa vocês terão que descobrir qual destas cinco chaves é a chave encantada que abre o portal para o seu mundo, se usarem a chave errada o portal nunca mais se abrirá” — diz o Mestre dos Magos

“Ta legal e como é que a gente vai saber qual é a chave que abre o portal?” — Pergunta Sheila.

“Para isso vocês devem ir ao cemitério dos dragões onde vive a deusa Tiamat e ela os ensinará recursividade” — Explica o Mestre dos Magos

“Eu é que não vou, até o vingador tem medo desse dragão!” — Reclama Erick

“Mas o que é recursividade e como isso ajuda a descobrir qual das chaves é a chave do portal?” — Pergunta Diana

O mestre dos magos não está mais lá.

Os jovens então se encaminham até o cemitério dos dragões para convencer Tiamat a ajudá-los. Logo na entrada a visão do dragão de cinco cabeças amedronta o grupo, mas curiosamente o dragão fala na linguagem humana e pergunta. — “Quem ousa invadir meu território?”

Então Tiamat se aproxima e desce uma de suas cabeças a altura dos jovens, agora impressionados com o tamanho da criatura.

“Tiamat, o mestre dos magos nos enviou e nos disse que só você pode dizer qual das chaves é a chave do portal para o nosso mundo” — diz Hank apresentando uma caixa de 5 chaves enfileiradas.

[]string{“chave1”, “chave2”, “chave3”, “chave4”, “chave5”}

“Entendo, eu geralmente não aceito pedidos, mas como o mestre dos magos os enviou direi apenas se a primeira chave dessa caixa é a chave do portal” — diz o Dragão.

O grupo reage assustado.

“Mesmo se houver a mínima chance ainda vale a pena, sinto saudade de casa” — diz Sheila triste.

“Mas se errarmos nunca mais sairemos daqui!” —responde Bobby nervoso.

“Acho que tive uma ideia” — diz Presto

Ele pega a caixa das mãos de Hank e pergunta a Tiamat, “A primeira chave é a chave do portal para casa?”.

“Não” — Responde Tiamat

Presto joga fora a primeira chave e reagrupa as chaves restantes.

[]string{“chave2”, “chave3”, “chave4”, “chave5”}

“A primeira chave é a chave do portal para casa?” — pergunta Presto novamente.

“Não” — Responde Tiamat

Presto joga mais uma chave fora e começa a reagrupar novamente as chaves restantes.

“Entendi, Tiamat disse que responderia apenas se a primeira chave da sequencia é a chave do portal, então ele vai responder a todas as chaves que estiverem na primeira posição!” — diz Diana.

“Ainda bem que ele não precisou usar o chapéu mágico” — diz Erick agora rindo.

Então Presto repetiu por mais três vezes o processo até que não restasse mais nenhuma chave

[]string{“chave3”, “chave4”, “chave5”}
[]string{“chave4”, “chave5”}
[]string{“chave5”}
[]string{}

“Parece que vocês conseguiram descobrir a recursão” — diz Tiamat

“Sim, mas não funcionou porque nenhuma das chaves é a chave do portal” — diz Hank decepcionado.

“Realmente, todas as chaves eram encantadas e todas elas levavam a uma armadilha do Vingador, ele se disfarçou para enganar vocês” — responde Tiamat.

E mais uma vez os jovens não voltam para a sua dimensão, mas pelo menos agora eles sabem recursão.

Esse exemplo inclui bem as três definições usadas anteriormente, temos uma repetição, o caso base onde seria encontrar a chave e ai encontrada ou terminado o numero de itens a repetição termina, e a operação que nesse caso poderia ser um slicing no Golang, (chaves[1:]) ou a função (pop) que retira os itens de um array no Javascript.

Ainda faltam mais exemplos, mas aguenta que a gente chega lá.

Call Stack

O que acontece por detrás das cortinas quando funções são chamadas?

Existe uma estrutura de dados que armazena as chamadas de funções, elas não são chamadas aleatoriamente. Assim como nosso código é lido de cima para baixo em uma certa ordem as funções também são organizadas nessa estrutura.

Podemos ver como a Stack recebe itens com a operação de Push e todos eles entram empilhados como pratos, e quando usamos a operação Pop para remover itens da estrutura, os itens são retirados do último para o primeiro assim como faríamos se fossem pratos, pra que a pilha não quebre.

Vamos implementar ela futuramente então não vamos mergulhar assim tão fundo pois não é o assunto principal.

package main

import  "fmt"

func  main() {
    acorda()
}

func  tomarBanho() string {
    return  "xuaxua"
}

func  tomarCafeDaManha() string {
    refeicao  :=  fazComida()
    return refeicao
}

func  fazComida() string {
    return  "ovo frito e café"
}

func  acorda() {
    tomarBanho()
    tomarCafeDaManha()
    fmt.Println("Ok bora trabalhar")
}

Aqui existem alguns exemplos de funções e algumas funções compostas de outras funções. Como seria a pilha das chamadas dessas funções?

push acorda (Primeira call na stack)
push acorda > tomarBanho (Agora temos duas calls na stack)
log(“xuaxua”)
pop tomarBanho (Depois de executada tomarBanho sai da stack)
push acorda > tomarCafeDaManha (Temos duas call na stack de novo )
push acorda > tomarCafeDaManha > fazComida (Terceira call)
log(“ovo frito e café”)
pop fazComida (Terceira call retirada)
pop tomarCafeDaManha (Segunda call retirada)
log(“Ok bora trabalhar”)
pop acorda() (A primeira call é a última a sair da stack)

Essa são calls de funções comuns, agora entender como se comporta a chamada de uma função recursiva parece mais simples.

Partindo do ponto de que elas funcionam como repetições uma função recursiva em uma stack se parece com isso:

push funcaoRecursiva()

push funcaoRecursiva()

push funcaoRecursiva()

push funcaoRecursiva()

push funcaoRecursiva()

push funcaoRecursiva()

…

E ela continua assim até que o caso base se resolva, caso não haja um caso base podemos ter um problema com estouro de pilha que é quando o numero de chamadas é muito alto e excede a quantidade suportada pela pilha. Também conhecido como stackOverFlow.

Exemplos

func  sumRange(num int) int {
    if num == 1 {
    return 1
}
    return num + sumRange(num-1)
}

O caso base de sumRange é “se num for igual a 1”, simples. Como temos certeza de que essa recursão não vai ficar rodando infinitamente?

A partir da operação sumRange(num -1), em toda chamada num será subtraído até que em algum momento num será igual a 1 é onde a repetição termina. Temos o caso base, operação e repetição.

Se a chamada for sumRange(4)

Será algo como isso:

4  +  sumRange(3) push
3  +  sumRange(2) push
2  +  sumRange(1) push
1 (caso base) push

na ida
na volta

return  1 pop
return  2  +  1 pop
return  3  +  3 pop
return  4  +  6 pop

valor final de num  =  10

Vamos a mais um exemplo.

func  fact(n int) int {
    if n == 1 {
    return 1
}
    return n * fact(n-1)
}

Esse é clássico, o exemplo do fatorial. O caso base fica óbvio “quando o input for 0” a repetição termina. Temos duas operações, multiplicação e subtração.

Se o nosso input for 3 fact(3)

Teremos 3 repetições onde a primeira chmada de fact(n) é 3 que é o valor do input: push — fact(3)

A próxima é a primeira chamada recursiva onde fact(n-1), isso transforam n em 2: push — fact(2)

Ultima chamada onde n vale 2 passando pela chamada recursiva fact(n-1) temos 1: push — fact(1)

Agora que n é igual a 1 ele atende ao caso base e terminamos as repetições, a stack começa a esvaziar e fazemos as operações de fora da recursividade.

3 * fact(2) = 6 pop

6 * fact(1) = 6 pop

fact(6) pop

Essa ultima a sair da stack ela não tem uma operação de multiplicação pois ela não é uma chamada recursiva ela é a chamada principal.

São exemplos bem básicos mas que servem pra vc ter uma boa ideia do comportamento de uma recursão e como criar sua própria função recursiva.

Exemplos de Recursão

Recursão Direta: Exemplo que você acabou de ver. A recursão direta chama a a si mesma sem assistência de outras funções.

Recursão Indireta: O tipo de recursão em que a função A chama outra função B e esta função, por sua vez, chama a função A. Este tipo de recursão requer o auxílio de outra função. A função chama a si mesma, mas indiretamente, ou seja, por meio de outra função. O exemplo a seguir explica o conceito de recursão indireta:

package main

import (
"fmt"
)

func  printaUm(n int) {
    if n >=  0 {
    fmt.Println("Na primeira func:", n)
    printaDois(n -  1)
    }
}

func  printaDois(n int) {
    if n >=  0 {
    fmt.Println("Na segunda func:", n)
    printaUm(n -  1)
    }
}

func  main() {
    printaUm(10)
    printaUm(-1)
}

No caso essa função printa a contagem regressiva de 10 a 0 alternativamente. O output:

Na primeira func: 10
Na segunda func: 9
Na primeira func: 8
Na segunda func: 7
Na primeira func: 6
Na segunda func: 5
Na primeira func: 4
Na segunda func: 3
Na primeira func: 2
Na segunda func: 1
Na primeira func: 0

Tail Call Recursion

Uma recursão em calda é uma chamada de sub-rotina que é a última chamada da função. Aqui, a chamada recursiva é a última coisa executada pela função.

package main

import (
"fmt"
)

func  printaInt(n int) {
    if n >  0 {
    fmt.Println(n)
    printaInt(n -  1)
    }
}

func  main() {
    printaInt(5)
}

Output:

Head Recursion

Em uma head recursion, a chamada recursiva é a primeira instrução na função. Não há nenhuma outra instrução ou operação antes da chamada. A função não precisa processar nada no momento da chamada e todas as operações são feitas no momento do retorno.

package main

import (
"fmt"
)

func  printaNum(n int) {
    if n >  0 {
    printaNum(n -  1)
    fmt.Println(n)
    }
}

func  main() {
    printaNum(5)
}

Output:

O exemplo inverso contando de 1 a N.

Além desses ainda existe a recursão de função anonima e a recursão infinita que é uma recursão que não tem caso base atendido e fica se repetindo até o seu notebook fica assim:

Porque usar recursão?

Recursão é muito utilizada apesar de ser frequentemente ignorada ou abordada superficialmente em cursos introdutórios de programação.

Quase todo algoritmo usado em estrutura de dados tem uma abordagem recursiva além da iterativa (for, while) e em alguns casos pode ser que a complexidade entre as duas abordagens seja completamente diferente.

É bastante provável que se você for iniciante você ainda não sabe resolver problemas recursivamente. Esse tópico se faz necessário devido as estruturas como arvores binárias que virão, esse é um dos motivos.

A recursão aparece em diversos lugares não apenas em algoritmos de estruturas de dados. A linguagem que você utiliza pode ter funções recursivas na própria stdlib.

No final mesmo que você não use, vocẽ vai acabar lendo então é necessário pelo menos entender para ler e pensar talvez em uma mesma solução iterativa caso prefira.

Recursivo x Iterativo

Tudo que se faz recursivamente pode ser feito iterativamente, então qual o ponto? A questão é que em alguns casos é muito mais fácil resolver os problemas recursivamente, ou a recursividade trará uma melhoria em performance em relação a uma solução iterativa para o mesmo problema.

Como a maior parte dos problemas em computação, depende. Porém saber diferenciar caso a caso qual é a melhor opção é o que faz de você um programador melhor. Você agora tem um segundo modo de resolver problemas repetitivos em programação e isso é ótimo.

Algumas das vantagens que que a recursividade pode trazer ao seu código é a legibilidade, a recursividade diminui a repetitividade no código, fazendo com que ele atenda o principio DRY “dont repeat yourself” encunhado por Andy Hunt e Dave Thomas no livro “The Pragmatic Programmer”.

“DRY é um princípio de desenvolvimento de software que visa reduzir a repetição de padrões de software substituindo-o por abstrações ou usando a normalização de dados para evitar redundância.” — Wikipedia

E aí entra um outro “depende”, a recursão vista como um meio de se resolver problemas na programação é usada por uma certa parcela de desenvolvedores não são todos os devs que compreendem ou preferem e isso depende mais da sua equipe. Impor isso a uma equipe que está acostumada a resolver as coisas iterativamente só vai atrapalhar a produtividade.

Devs que utilizam o paradigma funcional sempre preferem recursividade ou simplesmente não tem escolha devido a linguagens onde o paradigma é imposto. Recursão é um pattern empregado para contornar o uso de loops. Como os loops sempre mantêm um estado interno para saber em qual rodada eles estão, não podemos usá-los sob o paradigma de programação funcional.

Mais tarde…

Complexidade Quadrática O(N²)

Wagner Abrantes — Thu, 15 Oct 2020 20:40:12 +0000



package main

import (
    "fmt"
)

func printaTodosOsPares(n int) {
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            fmt.Println(i, j)
        }
    }
}

Acabamos de falar sobre um caso onde temos dois for e a complexidade era O(n) mas esse caso é diferente pois o for é aninhado e não é como se fosse um caso de N * 2 é N ao quadrado, se N fosse 10 o retorno seria 100 a proporção em que o tempo de execução cresce é muito maior.

Enquanto a complexidade linear sobe em uma linha reta, a complexidade quadrática sobre em uma curva, chamada de parábola, em relação ao eixo de tempo, para cada vez que N aumenta.

Nesse caso a regra de pensar quem domina quem também é válida, se vc tiver dois for aninhado e um solto dentro da função vc não tem um O(n + n²) porque o N linear é insignificante perto do quanto N² cresce. Então no final conte apenas com a maior função, O(n²). Lembrando novamente que big O é sobre o comportamento quando a entrada cresce muito. Um algoritmo linear pode ser pior que um quadrático até certo ponto, justamente por causa das constantes. Em algum momento o quadrático vai ficar mais lento, mas e se o ponto que isso acontece for lá quando a entrada tiver mais de 500 terabytes? Vale a pena usar o linear? Mas não se preocupe, para algoritmos simples e na maior parte dos casos que se usa no mercado de software, o ponto onde o O(n²) fica mais lento é bem cedo. Mas conhecimento nunca é demais =)

Output:

Com um parâmetro de 2 esse seria o output, porque o índice i varia de 0 a n para cada um dos valores de j. O número de cálculos vai ser uma multiplicação deles, ao invés da soma, ou seja, vai ser bem mais coisa pra parâmetros maiores.

Existem também a Complexidade Cúbica O(n³) seriam três loops aninhados a lógica é a mesma, não pretendo abordar sobre ele por aqui mas aqui vai um exemplo:



package main

import (
    "fmt"
)

func main() {
    var k, l, m int

    var arr [10][10][10]int

    for k = 0; k < 10; k++ {
        for l = 0; l < 10; l++ {
            for m = 0; m < 10; m++ {
                arr[k][l][m] = 1
                fmt.Println("Valor do elemento", k, l, m, " é", arr[k][l][m])
            }
        }
    }
}

Temos três loops percorrendo um array multidimensional a complexidade aumenta tanto que pra percorrer esse array com três loops são precisas mil operações pois 10 x 10 x 10 = 1000. Se o tamanho do array aumenta, o número de operações aumenta muito, mas muito mais.

Agora dá pra ter uma ideia da perspectiva, veja como a linha vermelha de uma complexidade quadrática sobre em relação as outras e também como a complexidade linear parece plana em relação a quadrática. De repente aqueles 18 segundos não são nada comparados a mais de 1 minuto isso com um input de 10kb. Então se eu tivesse no mesmo algoritmo essas três complexidades pouco importa se o O(n) vai receber 1tb de input o que ta te ferrando é essa O(n³), por isso nos preocupamos apenas com a maior função em relação a Big O Notation, aquela que domina as outras à medida que a entrada vai crescendo, e fazem elas parecerem insignificantes.

Algumas ideias pra você calcular as operações com Big O

Operações aritméticas são sempre constant time (os algoritmos de aritmética em si não são, mas nós consideramos que sim)
Atribuições de variáveis são constant time
Acessar elementos de array por index ou objetos por chave é constant time, enquanto acessar elementos de linked lists (como a do python) é linear time.
Em um loop a complexidade é o tamanho do loop * a complexidade do que tiver dentro do loop

Não precisa decorar mas é bom saber. As complexidades quadrática e cúbica são chamadas de polinomial. Todo algoritmo com complexidade n elevado a uma constante (2, 3, 4, 5, 6, etc) é polinomial. Se o algoritmo tiver complexidade n elevado à alguma variável que também cresce com a entrada (por exemplo, uma força bruta para o algoritmo do caixeiro-viajante ou quebrar senhas), então é o algoritmo é exponencial, a pior e mais lenta das complexidades.

Complexidade Logarítmica O(log n)

Wagner Abrantes — Thu, 15 Oct 2020 20:39:06 +0000

Back to school, vamos falar de matemática mas é algo tão simples que nem vai da tempo de você fica chateado.

É necessário entender um pouco sobre Logaritmos para entender a próxima notação, basicamente o que você precisa ter em mente é que logaritmos são o inverso de exponenciais.

E talvez você esteja lendo isso e “eu já vi isso na faculdade e etc”, eu não vi isso na faculdade porque eu não fiz faculdade eu tenho estudado isso por conta própria.

Se você também tá estudando por conta própria e acha que saber sobre complexidade, estrutura de dados não vai fazer diferença eu tomaria mais cuidado ou pelo menos investiria em soft skills para compensar o débito acadêmico. Quando você fizer um teste possivelmente alguém que faz ciências da computação vai disputar a vaga com você e ela já conhece isso por padrão.

Isso é um logaritmo:

log2(8) = 3

Leia-se, log na base 2 de 8 é igual a 3 e porque é igual a 3?

Porque a pergunta desse logaritmo é “qual numero eu uso na exponenciação para 2 que resulta em 8?”.

Então será 3 porque 2³ (dois ao cubo) é 2 * 2 * 2 = 8 fim do mistério.

E porque logaritmos são o inverso da exponenciação? Pois através do logaritmo de N temos o numero de operações.

O numero de operações é:

log 2(n) = x

Onde x é o numero de operações realizadas durante a execução do algoritmo.

Infelizmente nem tudo são flores e nem todo logaritmo é na base de 2 mas esse calculo não é a parte mais importante, repare que até aqui falamos sobre as complexidades e elas tem exemplos matemáticos como a exponenciação mas não fazemos contas realmente pra chegar na notação do algoritmo.

Então, para uma lista de 8 números, você teria que verificar 3 números no máximo. Para uma lista de 1.024 elementos, log 1.024 = 10, porque 2 elevado a 10 == 1.024. Então, para uma lista de 1.024 números, você tem que verificar 10 números no máximo.

Um exemplo de algoritmo com complexidade O(log n) é uma busca binária em uma lista já ordenada.



package main

import "fmt"

func main() {
    arr := []int{2, 3, 4, 10, 40}
    item := 9
    busca := buscaBinaria(arr, 0, len(arr), item)
    fmt.Println(busca)
}

func buscaBinaria(arr []int, esquerda, direita, item int) bool {
    for esquerda <= direita {
        meio := esquerda + (direita-esquerda)/2

        if arr[meio] == item {
            return true
        }

        if arr[meio] < item {
            esquerda = meio + 1
        } else {
            direita = meio - 1
        }
    }
    return false
}

Esse tipo de algoritmo é bem simples você parte o input ao meio e ai compara pra verificar se o item a ser buscado é menor ou maior que o item no meio do array. Quando isso acontece você joga fora metade da lista ficando com uma parte menor e esse processo é repetido até que se encontre o item da busca diminuindo cada vez mais o processamento, por isso ele é o inverso do exponencial você diminui o N toda vez que um processamento é feito.

Nesse exemplo do gráfico da pra verificar que o numero varia muito porém o tempo é irrelevante em relação a outras complexidades ali em baixo o input é de 1pb e o tempo de 3 milésimos. O gŕafico mostra como N aumenta e logo em seguida se torna quase uma constante, isso acontece porque mesmo que N duplique o algoritmo sempre vai estar fatiando N pela metade várias vezes até encontrar o resultado.

Como um rapaz disse no tweet que em que perguntei sobre log n esses dias “como você explicaria log n para um Júnior/Sandy”, ele disse:

Vou deixar aqui o link do Tweet pra quem quiser ver mais sobre Log N pois tiveram diversos pontos de vista sobre e podem ajudar mais pessoas.

Esse exemplo da busca binária só funciona quando se tem uma lista ordenada caso contrário o algoritmo não poderia garantir que o elemento procurado está de fato em uma metade ou outra da lista, sendo necessária outra abordagem.