DEV Community: Pedro Victor

[Boost]

Pedro Victor — Tue, 07 Jan 2025 14:39:24 +0000

Bem-vindo ao desenvolvimento Web: Um guia prático para quem está começando do zero

Cinthia Andrade ・ Jan 6 '25

#webdev #web #javascript #html

Como funcionam as Tries

Pedro Victor — Tue, 21 Dec 2021 16:38:48 +0000

Sumário

TL;DR
O problema inicial
Como comparamos strings
Uma ideia alternativa
Idealizando um "autocomplete"
Algumas otimizações
Conclusão

TL;DR

Tries são estruturas de dados que assumem a forma de árvore de busca, podendo um nó ter diversos filhos, mas nunca mais de um pai. A chave de cada nó geralmente é composta por um único caractere, o caminho a partir da raiz até um determinado nó forma uma palavra, ou parte de uma, inserida na Trie.

Problema inicial

Imagine que estamos desenvolvendo um jogo cuja meta do jogador é escrever todas as palavras que conhece, ganha quem souber mais palavras! Uma forma de contabilizarmos as palavras inseridas pode ser: a cada inserção verificamos se a palavra já foi inserida em uma lista, caso não tenha sido então adicionamos.
De fato essa solução funciona, mas será que essa é realmente a mais interessante?

Um método geral para comparar strings

Antes de tudo, vamos entender como geralmente comparamos strings. Para isso, utilizando como linguagem o JavaScript e este link como fonte temos uma forma geral de comparar strings:

Compare o primeiro caractere de cada string
Caso o valor de Unicode da primeira string seja maior ou menos que o da segunda, sabemos que são strings diferentes e terminamos
Caso sejam iguais, continue com o segundo caractere
Efetue a mesma etapa incrementando o índice do caractere analisado até finalizar a string
Caso cheguemos ao final da string e seus caracteres sejam iguais, sabemos com certeza que ambas as cadeias de caracteres são iguais

Uma ideia alternativa

A essa altura entendemos então que ao tentar adicionar uma palavra na lista que comentamos anteriormente não iremos apenas comparar ela N vezes, com N sendo a quantidade de palavras inseridas anteriormente na lista, mas por baixo dos panos também iremos comparar letras, palavra por palavra, de todos os elementos da lista.

Temos então uma ideia! E se montarmos um conjunto com as palavras que começam com a letra "C"? Nesse caso, quando quisermos adicionar a palavra "Car" apenas temos que comparar com as palavras dentro deste conjunto, reduzindo as comparações com palavras que começam com outras letras. Podemos aplicar o mesmo raciocínio e, dessa vez, construir o conjunto das palavras que começa com "Ca", e assim caso este esteja vazio sabemos que a palavra "Car" não foi inserida anteriormente e, por tanto, basta adicionar!

Note que o conjunto anterior continha então as palavras "Com" e "Cor", agora, inserimos "Car".

Um caso de uso mais complexo

Imagine que um programador esteja digitando em seu editor de texto e você deseja fornecer uma opção de "autocomplete" que mostra as palavras-chave que o usuário pode estar querendo digitar. Nesse caso, temos C, um conjunto de palavras-chave da linguagem, S um "armazém" de Tries que contém essas palavras-chave e W, a palavra que o programador começou a digitar. Podemos, portanto, selecionar em S (nosso "armazém") a Trie cuja raiz tem chave igual à primeira letra de W (palavra que o programador digitou), chamaremos esta de T (entenda apenas como sendo a Trie que usaremos), e então percorremos a cada letra de W um nó em T e, ao fim de W, percorremos essa sub-árvore com raiz na última letra da palavra digitada e mostramos todas as palavras que podem ser formadas a partir dela!

Parece complicado né? Mas na verdade não é! Entenda que nosso armazém é na verdade a raiz de uma Trie! Estranho né? Mas apenas pense que seria o equivalente de termos como chave nada mais nada menos que a string vazia, afinal, ela é prefixo de toda palavra!

Sobre o restante, nada mais é do que percorrer uma árvore a partir de um certo nó, o que podemos facilmente fazer com um pouquinho de conhecimento sobre a estrutura de dados árvore!

Nesse exemplo, suponha que o programador digitou apenas "L", dessa forma podemos percorrer recursivamente a Trie e obter para o nosso "autocomplete" as palavras-chave "Let", "List", "Length". Suponha agora que a entrada seja "Le", nesse caso teremos como retorno para "autocomplete" as palavras-chave "Let" e "Length". Com esse exemplo fica fácil saber como implementar, né?

Algumas otimizações

Suponha que no exemplo da imagem anterior tínhamos a palavra "Como", ao invés de "Com", dessa forma, naturalmente, poderíamos ter nossa Trie se adicionássemos um novo nó com a letra "o" como chave, correto? Sim!

Mas será que isso realmente é necessário? Algumas implementações utilizam uma breve otimização no quesito memória, como o nó de chave "m" não tem mais de um filho, poderíamos concatenar ambas as chaves e ter um nó de chave "mo". Isso traz alguma complexidade para a implementação, entretanto, representa um nó a menos na memória.

Tries podem ser implementadas de diversas formas, com diversos nomes, como: Árvore Prefixo, Árvore Sufixo e Árvore Patricia, cada um com seus detalhes de implementação e otimizações, é aconselhável ler o que cada uma tem a oferecer antes de implementar!

Conclusão

Com isso vemos uma nova forma de comparar strings, sem precisarmos percorrer repetidamente uma lista inteira, ou utilizar "índices únicos" em bancos de dados. Obviamente temos casos específicos para seu uso, o intuito deste artigo é apontar para uma nova abordagem, bem como uma nova estrutura de dados, caso algo não tenha ficado claro ou notou algum erro, não deixe de avisar!

Filtrando campos retornados em buscas com MongoDB

Pedro Victor — Sat, 11 Apr 2020 20:58:33 +0000

Filtrando campos em SQL

Se você já usou bancos relacionais, com certeza já se deparou com as famosas querys de busca, coisas como:

select nome, idade from usuario

Muito comuns e úteis, já que nem sempre queremos todas as colunas de uma tabela.

Mas e no MongoDB ?

Bom, geralmente aprendemos em vários eventos e cursos as funções básicas para fazer o famoso CRUD (Create, read, update, delete), com mongoose, que são ótimos para dar uma base prática a quem acaba de conhecer a tecnologia e dar ideias de desafios para quem já domina a tecnologia, nesses cursos aprendemos a fazer buscar com condições como essa:

const user = await User.find({name: "Nome do alvo"})

E como sabemos, isso retorna todo o Schema (modelo especificado por nós do documento) do usuário, cujo nome seja "Nome do alvo". Vamos supor que esse seja o Schema do User:

const UserSchema = new mongoose.Schema({
    name: {
        required: true,
        type: String,
        unique: false
    },
    githubUser: {
        required: true,
        type: String, 
        unique: true
    },
    bio: {
        required: false,
        type: String,
        unique: false
    },
    avatar_url: {
        required: true,
        type: String,
        unique: true
    },
    techs: [String]
    githubFollowers: [UserSchema],
    githubFollowing: [UserSchema]
});

Suponha que em dado momento da nossa aplicação, somente nos importe buscar os dados { name, githubUser, avatar_url }, não faz sentido buscarmos todos os dados se apenas queremos estes!

O segundo parâmetro do método find

Para resolvermos esse problema da requisição desnecessária de campos, podemos usar o segundo parâmetro do métodos find, chamado Projection, um JSON em que podemos filtrar quais campos queremos que sejam retornados, ou não, exemplo:

/*
  O 1 indica a inclusão do campo no retorno da query
  os demais campos não serão inclusos
*/
{
 name: 1,
 githubUser: 1,
 avatar_url: 1
}
/*
  O 0 indica a exclusão do campo no retorno da query
  os demais campos serão inclusos
*/
{
 bio: 0,
 techs: 0,
 githubFollowers: 0,
 githubFollowing: 0
}

IMPORTANTE: NÃO SE PODE MISTURAR 1s E 0s NA MESMA PROJEÇÃO!

Assim, temos o mesmo resultado nos dois casos! Filtramos então os campos para recebermos { name, githubUser, avatar_url }!

Mas como ficaria isso no código? Como se parece a resposta dessa query?

//Query
const result = await Dev.find({name: "Algum nome"},{name:1, githubUser: 1, avatar_url: 1})

//Resposta
 {
    "_id": "Array do ID",
    "name": "Pedro Victor",
    "githubUser": "stormsamurai1",
    "avatar_url": "https://avatars2.githubusercontent.com/u/37453874?v=4"
  }

PROBLEMA DE VIRTUALS!!!

Se você usa algum campo virtual no seu modelo, provavelmente vai se deparar com um problema: Os campos virtuais não são afetados.
Bem, isso ocorre por eles não persistirem no banco de dados, e, por isso, não temos tanto controle, mas isso não será um problema, podemos adicionar uma função a mais para remover esses campos e resolver o empecilho. Trata-se da função lean()

//Antes do lean
{
    "_id": "Array do ID",
    "name": "Pedro Victor",
    "githubUser": "stormsamurai1",
    "avatar_url": "https://avatars2.githubusercontent.com/u/37453874?v=4",
    "virtual_field": "virtual result",
    "id": "5e7aa3fc0cf9ea14d47fa461"
}

//Query atualizada
const result = await Dev.find({},{name:1, githubUser:1, avatar_url:1}).lean()

//Resultado atualizado
{
    "_id": "Array do ID",
    "name": "Pedro Victor",
    "githubUser": "stormsamurai1",
    "avatar_url": "https://avatars2.githubusercontent.com/u/37453874?v=4",
}

Conclusão

Apesar de ser um tema básico, é algo que senti vontade de escrever, via poucas pessoas utilizando essas funções e vi uma boa oportunidade de explorar o tema, pesquisar e começar com um projeto de escrita sobre coisas que aprendi. Qualquer dúvida que tenha, entre em contato! Críticas construtivas? Por favor, diga! É isto, obrigado a quem leu!