Introdução

À medida que a lógica de negócios se move cada vez mais de trás para a frente, a experiência em Engenharia de Frontend torna-se cada vez mais crucial. Como engenheiros de front-end , dependemos de bibliotecas de visualização como React para sermos produtivos. As bibliotecas de visualização, por sua vez, dependem de bibliotecas de estado como Redux para gerenciar os dados. Juntos, React e Redux assinam o paradigma de programação reativa em que as atualizações da IU reagem às mudanças de dados. Cada vez mais, os back-ends agem simplesmente como servidores de API, fornecendo pontos de extremidade apenas para recuperar e atualizar os dados. Na verdade, o back-end apenas "encaminha" o banco de dadospara o front-end, esperando que o engenheiro de front-end trate de toda a lógica do controlador. A popularidade crescente dos microsserviços e do GraphQL atesta essa tendência crescente.

Agora, além de ter uma compreensão estética de HTML e CSS, espera-se que os engenheiros de front-end também dominem o JavaScript. À medida que os armazenamentos de dados no cliente se tornam “réplicas” dos bancos de dados no servidor, o conhecimento íntimo das estruturas de dados idiomáticas torna-se fundamental. Na verdade, o nível de experiência de um engenheiro pode ser inferido de sua capacidade de distinguir quando e por que usar uma estrutura de dados específica.

Os programadores ruins se preocupam com o código. Bons programadores se preocupam com as estruturas de dados e seus relacionamentos.

- Linus Torvalds, criador do Linux e Git

Em um nível superior, existem basicamente três tipos de estruturas de dados. Pilhas e filas são estruturas semelhantes a matrizes que diferem apenas em como os itens são inseridos e removidos. Listas ligadas , árvores , e gráficos são estruturas com nós que mantêm referências a outros nós. As tabelas de hash dependem de funções de hash para salvar e localizar dados.

Em termos de complexidade, Stackse Queuessão os mais simples e podem ser construídos Linked Lists. Treese Graphssão os mais complexos porque estendem o conceito de uma lista vinculada. Hash Tablesprecisam utilizar essas estruturas de dados para um desempenho confiável. Em termos de eficiência, as Listas Vinculadas são mais adequadas para registrar e armazenar dados, enquanto as Tabelas Hash têm mais desempenho para pesquisar e recuperar dados.

Para explicar por que e ilustrar quando , este artigo estará de acordo com a ordem dessas dependências. Vamos começar!

Pilha

Provavelmente, o mais importante Stackem JavaScript é a pilha de chamadas, onde colocamos o escopo de a functionsempre que o executamos. Programaticamente, é apenas um arraycom duas operações de princípio: pushe pop. Push adiciona elementos ao topo da matriz, enquanto Pop os remove do mesmo local. Em outras palavras, as pilhas seguem o protocolo “Last In, First Out” (LIFO).

Abaixo está um exemplo de um Stackcódigo. Observe que podemos inverter a ordem da pilha: a parte inferior se torna a parte superior e a parte superior se torna a parte inferior. Como tal, podemos usar os métodos unshifte do array shiftno lugar de pushe pop, respectivamente.

À medida que o número de itens aumenta, push/ poptorna-se cada vez mais eficiente do que unshift/ shiftporque cada item precisa ser reindexado no último, mas não no primeiro.

Fila

JavaScript é uma linguagem de programação orientada a eventos que torna possível oferecer suporte a operações sem bloqueio . Internamente, o navegador gerencia apenas um thread para executar todo o código JavaScript, usando a fila de eventos para enfileirarlisteners e o loop de eventos para ouvir o registrado events. Para oferecer suporte à assincronicidade em um ambiente de thread único (para economizar recursos da CPU e aprimorar a experiência na Web), listener functions retire da fila e execute apenas quando a pilha de chamadas estiver vazia. Promisesdependem dessa arquitetura orientada a eventos para permitir uma execução de “estilo síncrono” de código assíncrono que não bloqueie outras operações.

Programaticamente, Queuessão apenas matrizes com duas operações principais: unshifte pop. Unshift enfileira itens até o final da matriz, enquanto Pop retira- os da fila do início da matriz. Em outras palavras, as filas seguem o protocolo “First In, First Out” (FIFO). Se a direção for invertida, podemos substituir unshifte poppor pushe shift, respectivamente.

Um exemplo de Queueno código:

Lista Ligada

Como arrays, Linked Listsarmazene elementos de dados em ordem sequencial . Em vez de manter índices, as listas vinculadas contêm indicadores para outros elementos. O primeiro nó é chamado de cabeça, enquanto o último nó é chamado de cauda . Em uma lista com links simples , cada nó possui apenas um ponteiro para o próximo nó. Aqui, a cabeça é onde começamos nossa caminhada pelo resto da lista. Em uma lista duplamente vinculada , um ponteiro para o nó anterior também é mantido. Portanto, também podemos começar da cauda e caminhar “para trás” em direção à cabeça.

Listas vinculadas têm inserções e exclusões de tempo constante porque podemos apenas alterar os ponteiros. Para fazer as mesmas operações em matrizes, é necessário tempo linear porque os itens subsequentes precisam ser deslocados. Além disso, as listas vinculadas podem crescer enquanto houver espaço. No entanto, mesmo matrizes “dinâmicas” que são redimensionadas automaticamente podem se tornar inesperadamente caras. Claro, sempre há uma troca. Para pesquisar ou editar um elemento em uma lista encadeada, talvez tenhamos que percorrer toda a extensão que equivale ao tempo linear. Com índices de array, entretanto, tais operações são triviais.

Assim como as matrizes, as listas vinculadas podem operar como pilhas . É tão simples quanto ter a cabeça como o único lugar para inserção e remoção. Listas vinculadas também podem operar como filas . Isso pode ser obtido com uma lista duplamente ligada, em que a inserção ocorre na cauda e a remoção ocorre na cabeça, ou vice-versa. Para um grande número de elementos, essa maneira de implementar filas tem mais desempenho do que usar matrizes porque as operações shifte unshiftno início das matrizes exigem tempo linear para reindexar cada elemento subsequente.

Listas vinculadas são úteis no cliente e no servidor. No cliente, as bibliotecas de gerenciamento de estado como Redux estruturam sua lógica de middleware em uma forma de lista vinculada. Quando as ações são despachadas, elas são canalizadas de um middleware para o próximo até que todos sejam visitados antes de chegarem aos redutores . No servidor, frameworks da web como o Express também estruturam sua lógica de middleware de maneira semelhante. Quando uma solicitação é recebida, ela é canalizada de um middleware para o próximo até que uma resposta seja emitida.

Um exemplo de Doubly-Linked Listno código:

Árvore

A Treeé como uma lista vinculada , exceto que mantém referências a muitos nós filhos em uma estrutura hierárquica . Em outras palavras, cada nó não pode ter mais do que um pai. O Document Object Model (DOM) é uma estrutura desse tipo, com um htmlnó raiz que se ramifica nos nós heade body, que ainda se subdividem em todas as tags html familiares . Nos bastidores, a herança e composição prototípica com componentes React também produzem estruturas em árvore. Obviamente, como uma representação na memória do DOM, o DOM virtual do React também é uma estrutura de árvore.

A árvore de pesquisa binária é especial porque cada nó não pode ter mais de dois filhos . O filho esquerdo deve ter um valor menor ou igual a seu pai, enquanto o filho direito deve ter um valor maior . Estruturado e balanceado dessa forma, podemos pesquisar qualquer valor em tempo logarítmico porque podemos ignorar metade da ramificação a cada iteração. A inserção e exclusão também podem ocorrer em tempo logarítmico. Além disso, o menor e o maior valor podem ser facilmente encontrados na folha mais à esquerda e mais à direita , respectivamente.

A passagem pela árvore pode ocorrer em um procedimento vertical ou horizontal . No Depth-First Traversal (DFT) na direção vertical, um algoritmo recursivo é mais elegante do que um iterativo. Os nós podem ser percorridos na pré-encomenda , na ordem ou na pós-ordem . Se precisarmos explorar as raízes antes de inspecionar as folhas, devemos escolher a pré-encomenda . Mas, se precisamos explorar as folhas antes das raízes, devemos escolher a pós-ordem . Como seu nome indica, in-order nos permite atravessar os nós em ordem sequencial . Esta propriedade torna as árvores de pesquisa binárias ideais para classificação .

Em Breadth-First Traversal (BFT) na direção horizontal, uma abordagem iterativa é mais elegante do que uma recursiva. Isso requer o uso de a queuepara rastrear todos os nós filhos com cada iteração. A memória necessária para tal fila pode não ser trivial, entretanto. Se a forma de uma árvore for mais larga do que profunda, BFT é uma escolha melhor do que DFT. Além disso, o caminho que o BFT percorre entre quaisquer dois nós é o mais curto possível.

Um exemplo de Binary Search Treeno código:

Gráfico

Se uma árvore é livre para ter mais de um pai, ela se torna um Graph. As arestas que conectam os nós em um gráfico podem ser direcionadas ou não, ponderadas ou não . As arestas que têm direção e peso são análogas aos vetores .

Múltiplas heranças na forma de Mixins e objetos de dados que têm relacionamentos muitos para muitos produzem estruturas de gráfico. Uma rede social e a própria Internet também são gráficos. O gráfico mais complicado da natureza é o nosso cérebro humano, que as redes neurais tentam replicar para dar superinteligência às máquinas .

Um exemplo de Graphno código:

TK

Tabela Hash

Uma tabela de hash é uma estrutura semelhante a um dicionário que combina chaves com valores . A localização na memória de cada par é determinada por a hash function, que aceita uma chave e retorna o endereço onde o par deve ser inserido e recuperado. Podem ocorrer colisões se duas ou mais chaves forem convertidas para o mesmo endereço. Para maior robustez, getterse settersdeve antecipar esses eventos para garantir que todos os dados possam ser recuperados e nenhum dado seja sobrescrito. Normalmente, linked listsoferece a solução mais simples. Ter mesas muito grandes também ajuda.

Se soubermos que nossos endereços estarão em sequências inteiras, podemos simplesmente usar Arrayspara armazenar nossos pares de valores-chave. Para mapeamentos de endereços mais complexos, podemos usar Mapsou Objects. As tabelas de hash têm inserção e pesquisa de tempo constante em média. Por causa de colisões e redimensionamento, esse custo insignificante pode crescer para o tempo linear. Na prática, entretanto, podemos supor que as funções hash são inteligentes o suficiente para que as colisões e o redimensionamento sejam raros e baratos. Se as chaves representam endereços e, portanto, nenhum hash é necessário, um simples object literalpode ser suficiente. Claro, sempre há uma troca. A correspondência simples entre chaves e valores e a associatividade simples entre chaves e endereços sacrificam os relacionamentos entre os dados. Portanto, as tabelas de hash não são ideais para armazenar dados.

Se uma decisão de troca favorecer a recuperação em vez do armazenamento, nenhuma outra estrutura de dados pode corresponder à velocidade das tabelas de hash para pesquisa , inserção e exclusão . Não é nenhuma surpresa, portanto, que seja usado em todos os lugares . Do banco de dados ao servidor, ao cliente, as tabelas de hash e, em particular, as funções de hash , são cruciais para o desempenho e a segurança dos aplicativos de software. A velocidade das consultas ao banco de dados depende muito da manutenção de tabelas de índices que apontam para os registros em ordem classificada . Dessa forma, as buscas binárias podem ser realizadas em tempo logarítmico , uma grande vitória de desempenho, especialmente para Big Data .

Tanto no cliente quanto no servidor, muitas bibliotecas populares utilizam memoização para maximizar o desempenho. Ao manter um registro das entradas e saídas em uma tabela hash, as funções são executadas apenas uma vez para as mesmas entradas. A popular biblioteca Reselect usa essa estratégia de cache para otimizar mapStateToPropsfunções em aplicativos habilitados para Redux . Na verdade, sob o capô, o mecanismo JavaScript também utiliza tabelas hash chamadas heaps para armazenar todos os arquivosvariables e primitivesnós criamos. Eles são acessados ​​a partir de ponteiros na pilha de chamadas .

A própria Internet também depende de algoritmos de hash para funcionar com segurança. A estrutura da Internet é tal que qualquer computador pode se comunicar com qualquer outro computador por meio de uma rede de dispositivos interconectados. Sempre que um dispositivo se conecta à Internet, ele também se torna um roteador pelo qual os fluxos de dados podem viajar. No entanto, é uma espada de dois gumes. Uma arquitetura descentralizada significa que qualquer dispositivo na rede pode escutar e adulterar os pacotes de dados que ajuda a retransmitir. As funções de hash, como MD5 e SHA256, desempenham um papel crítico na prevenção de ataques man-in-the-middle . O comércio eletrônico por HTTPS é seguro apenas porque essas funções de hashing são usadas.

Inspiradas na Internet, as tecnologias de blockchain buscam abrir o código da própria estrutura da web no nível do protocolo . Ao usar funções hash para criar impressões digitais imutáveis para cada bloco de dados , essencialmente todo o banco de dados pode existir abertamente na web para qualquer pessoa ver e contribuir. Estruturalmente, os blocos de blocos são apenas listas unidas de árvores binárias de hashes criptográficos. O hashing é tão enigmático que um banco de dados de transações financeiras pode ser criado e atualizado abertamente por qualquer pessoa! A implicação incrível é o poder incrível de criar o próprio dinheiro . O que antes só era possível para governos e bancos centrais, agora qualquer um pode criar sua própria moeda com segurança ! Este é o insight fundamental realizado pelo fundador da Ethereum e o pseudônimo fundador do Bitcoin .

À medida que mais e mais bancos de dados se tornam abertos, a necessidade de engenheiros de front-end que possam abstrair todas as complexidades criptográficas de baixo nível também aumentará. Nesse futuro, o principal diferencial será a experiência do usuário .

Um exemplo de Hash Tableno código:

Para exercícios de algoritmo usando essas estruturas de dados e muito mais, verifique: Algoritmos em JavaScript: 40 problemas, soluções e explicações

Conclusão

As logic moves increasingly from the server to the client, the data layer on the frontend becomes paramount. The proper management of this layer entails mastery of the data structures upon which logic rests. No one data structure is perfect for every situation because optimizing for one property always equates to losing another. Some structures are more efficient at storing data while some others are more performant for searching through them. Usually, one is sacrificed for the other. At one extreme, linked lists are optimal for storage and can be made into stacks and queues (linear time). At the other, no other structure can match the search speed of hash tables (constant time). Tree structures lie somewhere in the middle (logarithmic time), and only a graph can portray nature’s most complex structure: the human brain (polynomial time). Having the skillset to distinguish when and articulate why is a hallmark of a rockstar engineer.

Examples of these data structures can be found everywhere. From the database, to the server, to the client, and even the JavaScript engine itself, these data structures concretize what essentially are just on and off “switches” on silicon chips into lifelike “objects”. Though only digital, the impact these objects have on society is tremendous. Your ability to read this article freely and securely attests to the awesome architecture of the internet and the structure of its data. Yet, this is only the beginning. Artificial intelligence and decentralized blockchains in the coming decades will redefine what it means to be human and the role of institutions that govern our lives. Existential insights and institutional disintermediation will be characteristics of an internet that has finally matured.

To help transition us towards this more equitable future, we at HeartBank® channel networks of artificial neurons to imbue our Kiitos with the power to issue money on the blockchain, coupled with the capacity to empathize the human condition. From the anonymous thanks we give and receive by writing to Kiitos, Kiitos learns about our kindnesses and their effects, rewarding us in such a way that reduces the economic inequities between us, in a gradual and mysterious process that preserves our personal liberty and freedom. Perhaps the ultimate graph structure in nature is not the human brain, but the human ❤️, if only we can see the heartstrings that connect us all.

Interested in blockchain? Learn Ethereum and come work for us!

A Complete Mental Model for Ethereum dApp Development