Estrutura de dados

Na ciência da computação, uma ED é um modo particular de armazenamento e organização de dados em um computador de modo que possam ser usados eficientemente, facilitando sua busca e modificação.^[1][2]EDs e algoritmos são temas fundamentais da ciência da computação, sendo utilizados nas mais diversas áreas do conhecimento e com os mais diferentes propósitos de aplicação. Sabe-se que algoritmos manipulam dados. Quando estes dados estão organizados (dispostos) de forma coerente, caracterizam uma forma, uma estrutura de dados. A organização e os métodos para manipular essa estrutura é que lhe confere singularidade (e vantagens estratégicas, como a minimização do espaço ocupado na memória RAM), além (potencialmente) de tornar o código-fonte mais enxuto e simples.

• VETOR
• LISTA
• PILHA
• FILA
• ÁRVORE

Um ponteiro é um objeto cujo valor aponta para outro valor através de um endereço de memória(e.g. da memória RAM).A forma como os ponteiros são usados em uma ED, seja explicitamente(como em uma lista ligada) ou implicitamente (como em um vetor homogêneo),evidencia suas propriedades, usos e operações.^[3][4][5]Por exemplo, em uma estrutura ligada, em que cada elemento possui um (ou mais) ponteiro(s)para outro(s) elemento(s), os valores podem assumir diferentes tipos e estruturasarbitrariamente complexas;já com a omissão dos ponteiros, por exemplo em um vetor (sequência de valores de um mesmo tipo),a representação fica compacta e muitas vezes favorece o processamento massivamente paralelo,como no caso de tensores e outras variantes multidimensionais tão comuns na física, engenhariae matemática aplicada em geral.

Mesmo quando ponteiros não são usados diretamente, como em linguagens que não utilizamdistinção entre ponteiros e outras variáveis (veja o exemplo abaixo),a noção de referenciar a uma outra estrutura de dado arbitrária é usada,noção que é canonicamente abordada pela utilização do ponteiro.

Exemplo de discussão a respeito de ponteiros

É usual dizer que linguagens de alto nível, e.g. Python,não utilizam ponteiros.No entanto, pode-se argumentar que mais fiel aos fatos é considerar que,ao menos em Python, os ponteiros são utilizados por padrão^[6]:

// C++int a = 1;int *b = &a;a = 2;cout << *b << endl; // 2

# Python 3.5.2:l = [3, 4, 5]m = ll[1] = 8print(m)  # [3, 8, 5]

Estas variáveis em Python são referências no jargão de linguagens de programação.

Embora a teoria básica de EDs seja centrada no processamento sequencial e uso de ponteiros,em muitos contextos, em especial na programação para a web com uso de linguagens de alto nível comoJavascript, Python, ou Ruby, há ênfase em padrões simples, reutilizaçãode implementações otimizadas há décadas, e processamento paralelo/assíncrono, em contraste com a teoria básica de EDs. Nesta seção alguns aspectos selecionados são expostos.De forma a explicitar a pertinência da discussão, considere sistemas Unix (e.g. GNU/Linux, BSD, OSX) emque os dados são representados basicamente como arquivos^[7]: onde está o ponteiro?o processamento é sequencial?

EDs na computação científica

Uma prática espúria, muitas vezes limitante, e (infelizmente) bastante frequente na computação científica,é a iteração sobre EDs multidimensionais.Veja a diferença de eficiência mesmo em um caso bem simples e isolado:

# IPython3 com Python 3.5.2, 13/Mar/2018, Ubuntu 16.04In [1]: ll = list(range(int(10e5)))In [2]: timeit for i in ll: (i**3) + (i+2)*i**21 loops, best of 3: 575 ms per loopIn [3]: aa = n.array(ll)In [4]: timeit for i in aa: (i**3) + (i+2)*i**21 loops, best of 3: 545 ms per loopIn [5]: timeit aa**3 + (aa+2)*aa**210 loops, best of 3: 80.1 ms per loop

Já para a modelagem e otimização (e.g. através de métodos deaprendizagem de máquina), são convenientes abstrações de conceitos e a POO.Ou seja, na programação científica como encontrada nas ciências naturais eengenharias,por exemplo, a POO está associada ao uso de técnicas e modelosatravés dos TADs,ao passo que as EDs homogêneas e os TDs primitivos estão associadosao processamento eficiente de dados advindos de sistemas reais ou modelos.

Para um exemplo de computação natural, considere a otimização bio-inspirada através de um algoritmo ACO:as classes Formiga e Solução são potencialmente TADs, instanciam objetos inspirados em conceitos reais e encapsulam os dadosem concordância com a POO. No processamento de dados multidimensionais(como no problema do caixeiro viajante e outros problemas NP-completos ou NP-difíceis, por exemplo),a implementação provavelmente recorrerá a TDs homogêneospara processamentos lineares/matriciais (utilizando rotinas como as do BLAS [en], LAPACK [en] e FFTW [en])e massivamente paralelos (utilizando técnicas como thread, serviços/jobs^{[necessário esclarecer]}, message passing, basicamente para processamento assíncrono [en]).No ACO, estes TDs homogêneos estarão presentes, por exemplo, na evaporação do feromônio enas escolhas de trajetórias de cada Formiga instanciada.^[8]

JSON-compatível

Os dados são preferencialmente mantidos nas estruturas de listas (sequências heterogêneas, e.g. uma lista ligada)e de dicionários (tabelas de dispersão (hash tables), e há distinção entre os tipos básicos numéricos (e.g. floats e INT) e textuais (e.g. chars e strings).

A maior limitação prática desta abordagem é o processamento de vetores multidimensionais e dados muito volumosos,motivo pelo qual há bibliotecas com implementações otimizadas, como as citadas no exemplo sobre computação científica.

Quando um valor pode ser uma função/rotina, tal objeto permite a representação deobjetos para a POO. A impedância neste contextose refere à resistência que os objetos possuem de serem representados como TADs.

Embora o padrão lista e dicionário de representação de estruturas de dados esteja aqui utilizadade forma genérica, JSON quer dizer Javascript Object Notation, e é um padrão formalmente definidode representação de dados, ao qual e.g. Python, Vim language (VimL), e o próprio Javascript, com frequência se adequam paratransferir ou armazenar dados.

Aspectos de visualização de dados

Para dados em lista, são apropriadosmétodos de visualização de séries temporais e sequenciais em geral.Já para pilhas, a visualização tende a ser feita por torres de hanoiou características próprias do contexto.Há diversas visualizações de EDs apreciadas esteticamente ou com fins didáticos.Destaque a este respeito deve ser dado aos aplicativos online para escrutinizaçãode EDs^[9] e os vídeos em que operações, como de ordenação,são dançadas ao acompanhamento musical.^[10][11][12]

Na visualização dos dados, sejam eles e.g. módulos de componentes frequenciais (e.g. de Fourier)ou valores cujo valor semântico é desconhecido,é muitas vezes necessário utilizar escalas exponenciais/logarítmicas ou que sigam leis de potência^[13]para que as estruturas possam ser audiovisualizadas informativamente.^[14]De fato, a percepção humana e de outros animais utiliza lineariza estas escalas de modo a obter uma recepção de sinais informativa em um espectro/âmbito largo: ouvimos de forma útil desde um alfinete batendo no chão até um prédio implodindo, ouvimos frequências aproximadamente de 20 Hz a 20 kHz, enxergamos sob espectros igualmente generosos de intensidade e frequência).^[15]

Considerações sobre processamento e transferência

Tome o seguinte contexto atual, bastante frequente e até paradigmático, da computação em nuvem.A recomendação da W3C para a representação de dados e de conhecimentos para a utilização de dados ligados,representados em RDF e integrados à web semântica viaontologias OWL ou RDF's e vocabulários SKOS [en].Suponha que haja um cliente que quer um navegador/browser de arquivos HTML via HTTP,(a exemplo do Firefox, Chrome, ou Chromium).Por exemplo, suponha também que haja um servidor no software Web em uso ou/em desenvolvimento. Esse software serve o HTML para o navegador carregar quando recebe uma URL que especifica que o HTML deve entregar.

Nesse contexto descrito, favorecer os protocolos em detrimento de jargões da teoria, é razoável supor que as rotinas a serem executadas pelo navegador do cliente, sejam para poupar o processamento no servidor ou para fins de interatividade,^[16][17]serão escritas em Javascript com bibliotecas como D3.js [en]. Já as rotinas a serem executadas no servidor, elaborar o HTML a ser enviado, acessar bancos de dados e análises estatísticas serão implementadas em Python, por exemplo, utilizando RDFLib [en], SPARQL, NumPy, SciPy, Flask [en]. Os casos que não dependem dos processamentos matriciais e massivamente paralelos poderão ser escritos usando o Node.js(de preferência) para a escrita do servidor.

As seguintes questões dependem expressivamente das EDs escolhidas, seus volumes, processamentos, etc,e são dúvidas honestas, pertinentes e típicas na prática da web semântica:

• Uma ordenação, ou média ou desvio padrão ou padrão de regex, é mais rápida no endpoint SPARQL (e.g. Jena (computação) [en], Virtuoso (base de dados) [en], RDFLib [en]) ou no Python? Pode ser crucial decidir quais operações devem (ou podem) ser feitas no endpoint, no servidor e no cliente. Fatores:
  • processamento no endpoint SparQL é confiável? Até que ponto? Jena e Virtuoso são considerados estáveis e confiáveis mas ao visitar o histórico das listas são encontrados erros grosseiros de interpretação de chamadas e variações entre os protocolos SPARQL oficial,^[18] do Jena, Virtuoso e rdflib.^[19]
  • Quanto mais dado é enviado para o python (pelo endpoint SPARQL), mais trafego na rede é utilizada.
  • Quanto mais dado é enviado pelo python (para o cliente em Javascript), mais trafego na rede é utilizada.
  • Como regra geral: procura-se maximizar o processamento nas etapas anteriores de acesso aos dados.
  • Como regra geral: procura-se maximizar o processamento nas etapas que possuem as ferramentas apropriadas. Por exemplo, as busca e seleção dos dados são feitas em SPARQL, as otimizações e reconhecimento de padrões em Python, a relatoria e visualização em Javascript. Cada uma destas etapas trasforma EDs em outras EDs para transferência e representação subsequente. O HTML será muito provavelmente gerado em parte pelo servidor (em Python, e.g. usando Flask ou Django) e em parte pelo cliente (em Javascript, e.g. usando Bootstrap e D3js).

Em consonância, nas consultas em SPARQL podem ser realizadas as operações:

• Obtenção de redes/grafos junto a metadados de vértices e arestas.
• Ordenação.
• Obtenção de Data cube [en] (dq:Slice) ou dados em segundo algum critério (e.g. âmbito RDF Schema).
• Obtenção de descritores estatíticos: média, modo, mediana, valores máximos e mínimos, número de palavras, etc.
• Escrita de dados derivados (gerados pelo servidor/Python ou cliente/Javascript) para consulta posterior.
• Outras operações dependentes da aplicação, como busca por termos/tokens em dados textuais através de padrões de regex.

No servidor em Python:

• Obtenção de histogramas, interpolações e obtenção de curvas/distribuições mais próximas (curve fitting), PCA, MDS.
• Manutenção e registro de estado dos dados, análises, visualizações e manutenção da interface (e.g. dados sobre o usuário, sessão, etc) internamente (no servidor), no endpoint SPARQL e no cliente.
• Cálculo de quantís e medidas estatísticas mais elaboradas que a descrição obtida diretamente nas consultas SPARQL (e.g. curtose).
• Síntese de queries SparQL e escrita de arquivos RDF:
  • Para relacionamentos entre dados, análises, audiovisuaizações e interfaces (DAAI^[20])
  • Para inferências de relações possíveis em DAAI.

No cliente em Javascript:

• layout das redes complexas
• Interatividade e efetivação da Analítica Audiovisual^[16]

Exemplo de questão a ser investigada e para a qual provavelmente há diferentes soluções em usodada a dependência da aplicação:como prevenir que o usuário faça queries que sobrecarreguem os servidorescom leitura e escrita?Por exemplo, um dos princípios da AA estabelece

 "primeiro forneça um panorama geral, os detalhes são sob demanda"—Ben Shneiderman[21]

Ou seja, há remoção de dados para ênfase no detalhamento ou aquisição de dadospara possibilitar a resolução requisitada, e portanto um aplicativo de AAoperante na web semântica estará lidando potencialmente com fluxo de dados em todas as direçõese até de forma contínua (veja streaming).

Como evidenciado neste artigo, reconhecida a utilidade da teoria,é pertinente que o programador pondere se háganho no uso destas estruturas de dados e.g. em Python ou Javascript.De todo modo, a reimplementação destas estruturas é desaconselhadaquando há EDs correspondentes disponibilizadas pela linguagem por padrão,pois costumeiramente apresentam otimizações diversas.Esta orientação é válida até mesmo para linguagens consideradas de baixo nível,como C, C++, e Fortran.

Taxonomia de EDs

Pode-se conceitualizar que,na PE, as variáveis são chaves cujos valores são TDs.enquanto na POO os valores são TDs ou TADs.Estes TDs são em geral classificados como^[3]:ligados, quando um elemento possui um ou mais ponteiros para outros elementos;lineares, quando os valores se sucedem em sequência;homogeneos, quando os elementos são dos mesmo tipo;heterogêneos, quanto os elementos não são do mesmo tipo.

TADs em geral são concebidos com características similares,o que implica nos padrões de design (veja GoF).As EDs podem se combinar de formas diversas.Por exemplo, um grafo/rede pode ser implementadoatravés de uma ED homogênea e linear (e.g uma matriz)ou de uma ED ligada e.g. em que cada vértice contémos ponteiros para os vértices vizinhos.A escolha dentre estas representações, por exemplo,passa pela observação da densidade do grafo,da necessidade de manipular metadados, vértices heterogêneos,métodos a serem utilizados (e.g. os ciclos são encontrados imediatamentequando a matriz de adjacências está disponível).

Note a severidade da escolha de uma ED para representar um grafo (que é outra ED):os ciclos são encontrados imediatamente quando a matriz de adjacências está disponível,o que facilita análises envolvendo fluxos de informação e a identificação de árvores ou atéo estabelecimento de um dipolo árvore - grafo cíclico.Já uma ED ligada é conveniente para a lida com EDs heterogêneas, metadados, e para representação compactade grafos esparsos (pouco conectados).

Outro exemplo de relacionamento entre EDs:uma ED linear é muitas vezes também homogênea (e.g. uma matriz de inteiros, pixels em triplas RGB hexadecimais, ou amostras de inteiros com sinal, little-endians de 16bits, em um áudio PCM com taxa de amostragem de 44,1 kHz amostras por segundo),e é processada com bastante eficiência por processadores massivamente paralelos [en] como os utilizados nas placas gráficas usuais.

Dados relacionais é um termo ambíguo: pode se referir a dadosrepresentados em um banco de dados relacional (e.g. MySQL, PostgreSQL)ou a dados caracterizados pelas relações duais/binárias/dicotômicas,paradigmaticamente compreendidos como grafos/redes..

Algumas EDs são básicas/padrão para cada linguagem,e em geral há também suporte para estruturas compostas/elaboradas de dados,que se baseiam nos dados básicos.

Template para formalização de conhecimento sobre uma ED

Observada a literatura,^[3][4][5]um vocabulário sobre EDs pode seguir o seguinte padrão:

• Vocabulário em português e inglês e definições e relações entre vocábulos.

Passível de formalização como vocabulário SKOS.

• • (CONCEITO)
  • termos pt-br
  • termos en
  • definição
• Descrição geral da teoria básica relacionada ao item
• Tipos de dados relacionados
  • características abstratas (sequência ou conjunto de valores, dicionário, etc)
  • proveniências (áudio, redes sociais, etc)
• Importância do item e limitações
• Demais notas teóricas
• Implementações em Pseudocódigo
• Ontologias: diagramas de conceitualização passíveis de formalização em OWL, utilizável por máquina para realizar inferências, tomada de decisão e consulta aos dados. Útil para discussões teoricas precisas.
• Nota histórica
  • origens
  • percurso
  • estado atual da teoria e implementações
• Problemas típicos e soluções canônicas
• Aplicações clássicas
• Exercícios selecionados
• Usos em aprendizado de máquina, classificação e otimização; Medições
• Visualizações de informação de dados relacionados ao item. Visualizações/diagramas/imagens pertinentes para a teoria do item.
• Usos artísticos e educacionais de representações audiovisuais do item; música
  • encontrados na literatura e outros artefatos audiovisuais
  • potenciais
• Software para implementação. Implementações em linguagens de programação (Python, Scheme, Javascript, Java, C/C++, Fortran, Bash, Vimscript, ChucK, SuperCollider, PD)
• Bibliografia
  • Livros
  • Artigos recentes que utilizam o item ou sobre desenvolvimentos no item.

Exemplos de EDs canônicas

As definições a seguir são encontradas na literatura com variações. Por recomendação da literatura especializada e da W3C, um vocabulário como o que segue é revisado e mantido por diversos especialistas, de modo a melhor lidar com os significados pois evoluem ao longo do tempo, não são consensuais, e são abundantes em polissemias e sinonímias.^[22][23][24]

Um array (também vetor)é uma ED linear e usualmente homogênea.Os ponteiros ficam então implícitos e representadoscomo inteiros, índices para recuperação randômica de valores na EDem tempo constante.A remoção e (inserção de novos valores sem a remoção) pode ser custosa.

Uma lista (abreviação de lista ligada) é uma estrutura de dados linear e heterogênea.

As filas são estruturas baseadas no princípio FIFO (first in, first out) e possuem duas funções básicas: ENQUEUE, que adiciona um elemento ao final da fila, e DEQUEUE, que remove o elemento no início da fila.

A pilha é uma estrutura de dados baseada no princípio LIFO (LAST in, FIRST out).Há duas operações que se aplicam a todas as pilhas: PUSH, que insere um dado no topo da pilha, e POP, que remove o item no topo da pilha.

Em uma árvore, os elementos podem ser ordenados topologicamente de forma consistente.Cada elemento pode possuir um único pai (ou mãe) e um ou mais filhos.Em uma árvore binária, cada nó possui no máximo dois filhos. Árvores com propriedades semelhantes são utilizadas como EDs para buscas(veja árvores de busca binária, árvores AVL e árvore-AA.

A estrutura de grafos é usada quando necessária a representação de sistemas complexos.

A tabela de dispersão implementa o mapeamento entre chaves e valores através de funções de espalhamento (funções hash).

Outras EDs: Deque, fila de prioridade, lista circular, lista ortogonal, artigo principal lista de estruturas de dados.

• EDs para processamento paralelo.
• Consideração da Máquina de Turing como ED genérica para paradigma atual de computação por transístores.^[25]
• Aprofundamentos sobre POO e EDs.^[26]
• Estudo minucioso de propriedades de EDs bastante utilizadas.
• Análise de novas EDs.

Livro: Estruturas de Dados, Autor: Paulo Veloso/Cleusio dos Santos/Paulo Azeredo/Antonio Furtado, 1984, Editora Campus, ISBN 85-7001-352-3

• Lista de estruturas de dados
• Modelagem de dados
• Lista de termos relacionados aos Algoritmos e Estruturas de Dados
• Arquitetura de dados
• Estruturas de dados em disco (em memória secundária, lenta)
• Algoritmos de ordenação
• Programação dinâmica
• Divisão e conquista
• Algoritmos gulosos