Estrutura de dados

Uma árvore binária é uma estrutura de dados.

Uma estrutura de dados (ED), em ciência da computação, é uma coleção tanto de valores (e seus relacionamentos) quanto de operações (sobre os valores e estruturas decorrentes). É uma implementação concreta de um tipo abstrato de dado (TAD) ou um tipo de dado (TD) básico ou primitivo. Assim, o termo ED pode ser considerado sinônimo de TD, se considerado TAD um hipônimo de TD, isto é, se um TAD for um TD.

Critérios para escolha e estudo de uma estrutura de dados incluem eficiência para buscas e padrões específicos de acesso, necessidades especiais para manejo de grandes volumes (veja big data), ou a simplicidade de implementação e uso (talvez o motivo mais comum da escolha). Ou seja, EDs eficientes são cruciais para a elaboração de algoritmos, diversas linguagens possuem ênfase nas EDs, como evidenciado pela POO, e aplicações distintas usufruem de ou requerem EDs específicas (e.g. um compilador usa uma tabela de dispersão para identificadores e namespaces, enquanto uma Árvore B ou Árvore AA [en] é apropriada para acessos randômicos).

Em termos de EDs, os TDs e TADs são definidos indiretamente pelas operações e usos, e propriedades destas operações e usos: e.g. o custo computacional e o espaço que pode representar e ocupa na memória.

Relevância para a Ciência da Computação

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. 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.

Conceito-chave: ponteiro

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 implictamente (como em um vetor homogêneo), evidencia suas propriedades, usos e operações. 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 estruturas arbitrariamente 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, engenharia e matemática aplicada em geral.

Mesmo quando ponteiros não são usados diretamente, como em linguagens que não utilizam distinçã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. Pode-se argumentar que mais fiel aos fatos é considerar que, ao menos em Python, os ponteiros são utilizados por padrão:

int a = 1;
int *b = *a;
a = 2
count << *b << endl; # 2

# Python 3.5.2:
a = 1
b = a
b = 2
print(b)  # 2

# além disso:
l = [3, 4, 5]
m = l
l[1] = 8
print(m)  # [3, 8, 5]

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

EDs para a Web, computação científica e scripting em geral

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 como Javascript, Python, ou Ruby, há ênfase em padrões simples, reutilização de 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) em que os dados são representados basicamente como arquivos: 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.04
 
In [1]: ll = list(range(int(10e5)))

In [2]: timeit for i in ll: (i**3) + (i+2)*i**2
1 loops, best of 3: 575 ms per loop

In [3]: aa = n.array(ll)

In [4]: timeit for i in aa: (i**3) + (i+2)*i**2
1 loops, best of 3: 545 ms per loop

In [5]: timeit aa**3 + (aa+2)*aa**2
10 loops, best of 3: 80.1 ms per loop

Já para a modelagem e otimização (e.g. através de métodos de aprendizagem 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 e engenharias, por exemplo, a POO está associada ao uso de técnicas e modelos através dos TADs, ao passo que as EDs homogêneas e os TDs primitivos estão associados ao processamento eficiente de dados advindos de sistemas reais ou complexos.

Para um exemplo de programação natural [en] (o termo programação natural é também usado para se referir à intersecção entre ciências naturais, biológicas e computacionais: algoritmos bio-inspirados, simulação e emulação da natureza, computação por materiais alternativos ao silício), considere a otimização bio-inspirada de um algoritmo ACO: as classes de formigas e solução são potencialmente TADs, instanciam-se em objetos inspirados em conceitos reais e encapsulam os dados em consonância com a POO. Estes objetos terão de lidar com o processamento de dados multidimensionais (como no problema do caixeiro viajante e outros problemas NP-completos ou NP-duros, por exemplo), e para isso provavelmente recorrerão a TDs homogêneos para 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, message passing, basicamente para processamento assíncrono [en]).

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 de objetos para a POO. A impedância neste contexto se 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 utilizada de forma genérica, JSON quer dizer Javascript Object Notation, e é um padrão formalmente definido de representação de dados, ao qual e.g. Python, VimL, e o próprio Javascript, com frequência se adequam para transferir ou armazenar dados.

Aspectos de visualização de dados

Para dados em lista, são apropriados mé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 hanoi ou 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ção de EDs e os vídeos em que operações, como de ordenação, são dançadas ao acompanhamento musical.

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 para que as estruturas possam ser audiovisualizadas informativamente. 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 20Hz a 20kHz, enxergamos sob espectros igualmente generosos de intensidade e frequência).

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 conhecimentos é a utilização de dados ligados, representados em RDF e integrados à web semântica via ontologias OWL ou RDF's e vocabulários SKOS [en]. Suponha que haja um cliente que é um navegador/browser de arquivos HTML via HTTP, a exemplo do Firefox, Chrome, ou Chromium. Suponha também que haja e um servidor no software Web em uso ou desenvolvimento, este serve o HTML para o navegador carregar quando recebe uma URL que especifica qual HTML deve entregar.

Neste contexto, descrito favorecendo protocolos e em detrimento à jargões da teoria, é raoável supor que as rotinas a serem executadas pelo navegador, no cliente, e.g. para poupar processamento no servidor ou para fins de interatividade, serão escritas em Javascript com bibliotecas como D3.js [en]. Já as rotinas a serem executadas no servidor, e.g. para 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 podem dar preferência à utilização de Node.js 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, Virtuoso, 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, do Jena, Virtuoso e rdflib..
  • 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), mas 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 subsequênte. O HTML será muito provavelmente gerado em parte pelo servidor (em Python, e.g. usando Flask ou Django) e em parte pelo cliente (em Javascrit, 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)
  • 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

Exemplo de questão a ser investigada e para a qual provavelmente há diferentes soluções em uso dada a dependência da aplicação: como prevenir que o usuário faça queries que sobrecarreguem os servidores com 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

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

Estruturas de dados canônicas

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 é desaconselhada quando 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: 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 implementado atravé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ém os 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 (os ciclos são encontrados imediatamente quando 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 compacta de 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,1kHz amostras por segundo), e é processada com bastante eficiência por processadores massivamente paralelos como os utilizados nas placas gráficas usuais.

Dados relacionais é um termo ambíguo: pode se referir a dados representados 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, 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 TDs canônicos

Cuidado: As definições a seguir são encontradas na literatura com variações. Idealmente, 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 carregados de polissemia e sinonímia.

Um array (também vetor) é uma ED linear e usualmente homogênea. Os ponteiros ficam então implícitos e representados como inteiros, índices para recuperação randômica de valores na ED em 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).

Tópicos avançados

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

Referências

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

Ver também

• 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
• Técnicas de aprendizagem
• Técnicas de otimização