Estrutura de dados

Origem: Wikipédia, a enciclopédia livre.


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. 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[editar | editar código-fonte]

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.

Principais Estruturas de Dados (clássicas)[editar | editar código-fonte]

Conceito-chave: ponteiro[editar | editar código-fonte]

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 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[editar | editar código-fonte]

É 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 = 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[editar | editar código-fonte]

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[7]: onde está o ponteiro? o processamento é sequencial?

EDs na computação científica[editar | editar código-fonte]

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 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 dados em 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ê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[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 e nas escolhas de trajetórias de cada Formiga instanciada.[8]

JSON-compatível[editar | editar código-fonte]

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, Vim language (VimL), e o próprio Javascript, com frequência se adequam para transferir ou armazenar dados.

Aspectos de visualização de dados[editar | editar código-fonte]

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[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[editar | editar código-fonte]

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 via ontologias 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:

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[21]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 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 (e.g. 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,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 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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

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

Tópicos avançados[editar | editar código-fonte]

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

Referências

  1. Paul E. Black (ed.), Data structure. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology, 2004. Versão online .
  2. Data structure. Encyclopædia Britannica (2009) Online
  3. a b c CORMEN, T. H.; LEISERSON, C.E.; RIVEST, R.L.; Algoritmos: Teoria e Prática. Editora Campus, Tradução da 2ª edição americana, 2002.
  4. a b Dasgupta, Sanjoy, Christos H. Papadimitriou, and Umesh Vazirani. Algorithms. McGraw-Hill, Inc., 2006.
  5. a b ZIVIANI, N.; Projeto de Algoritmos com implementação em Java e C++. Editora Thomson, 1ª edição, 2006.
  6. https://stackoverflow.com/questions/13530998/python-variables-are-pointers
  7. The art of Unix Programming
  8. CASTRO, L. N. Fundamentals of Natural Computing: Basic Concepts, Algorithms, and Applications, CRC Press, 2006.
  9. https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
  10. https://www.youtube.com/watch?v=lyZQPjUT5B4
  11. https://www.youtube.com/watch?v=Xw2D9aJRBY4
  12. https://www.youtube.com/watch?v=nK_o13c-0lk
  13. Fabbri, R. Oliveira, O. N. O, "A simple model that explains why inequality is ubiquitous", 2017, disponível em: https://github.com/ttm/ubiquitousInequality/blob/master/plosOne/plos_latex_template.pdf
  14. Fabbri, R., Oliveira, M. C. F., Audiovisual Analytics of Social Linked Data", 2017, disponível em: https://github.com/ttm/aavo/raw/master/latex/nuvem/nuvem2.pdf
  15. Physics and psychophysics of music. Roederer
  16. a b artigo sobre o AAVVO
  17. Fabbri, Renato. "Enhancements of linked data expressiveness for ontologies." arXiv preprint arXiv:1710.09952 (2017).
  18. https://www.w3.org/TR/rdf-sparql-query/
  19. lista jena
  20. link para figura
  21. colocar o artigo certo do Ben
  22. Tom Heath and Christian Bizer (2011) Linked Data: Evolving the Web into a Global Data Space (1st edition). Synthesis Lectures on the Semantic Web: Theory and Technology, 1:1, 1-136. Morgan & Claypool.
  23. Allemang, D., & Hendler, J. (2011). Semantic web for the working ontologist: effective modeling in RDFS and OWL. Elsevier.
  24. https://arxiv.org/abs/1710.09952
  25. https://www.quora.com/Is-there-a-theory-of-data-structures
  26. http://www.cs.cornell.edu/people/kopylov/papers/thesis/thesis.pdf


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[editar | editar código-fonte]