right|192|thumb|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 é 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.Paul E. Black (ed.), Data structure. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology, 2004. Versão online .Data structure. Encyclopædia Britannica (2009) Online
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) VETOR LISTA PILHA FILA ÁRVORE
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 implicitamente (como em um vetor homogêneo), evidencia suas propriedades, usos e operações.CORMEN, T. H.; LEISERSON, C.E.; RIVEST, R.L.; Algoritmos: Teoria e Prática. Editora Campus, Tradução da 2ª edição americana, 2002.Dasgupta, Sanjoy, Christos H. Papadimitriou, and Umesh Vazirani. Algorithms. McGraw-Hill, Inc., 2006.ZIVIANI, N.; Projeto de Algoritmos com implementação em Java e C++. Editora Thomson, 1ª edição, 2006. 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. No entanto, pode-se argumentar que mais fiel aos fatos é considerar que, ao menos em Python, os ponteiros são utilizados por padrão:
// C++ int a = 1; int *b = &a; a = 2; cout << *b << endl; // 2
# Python 3.5.2: l = [3, 4, 5] m = l l = 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.
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 : ll = list(range(int(10e5)))
In : timeit for i in ll: (i**3) + (i+2)*i**2 1 loops, best of 3: 575 ms per loop
In : aa = n.array(ll)
In : timeit for i in aa: (i**3) + (i+2)*i**2 1 loops, best of 3: 545 ms per loop
In : 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 , e ) e massivamente paralelos (utilizando técnicas como thread, serviços/jobs, message passing, basicamente para ).
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.CASTRO, L. N. Fundamentals of Natural Computing: Basic Concepts, Algorithms, and Applications, CRC Press, 2006.
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 ) 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 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 escrutinação de EDshttps://www.cs.usfca.edu/~galles/visualization/Algorithms.html 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ênciaFabbri, 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 para que as estruturas possam ser audiovisualizadas informativamente.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 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).Physics and psychophysics of music. Roederer
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 via ontologias OWL ou RDF's e .
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,Fabbri, Renato. "Enhancements of linked data expressiveness for ontologies." arXiv preprint arXiv:1710.09952 (2017). serão escritas em Javascript com bibliotecas como . 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 , , NumPy, , . Os casos que não dependem dos processamentos matriciais e massivamente paralelos poderão ser escritos usando o (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 (e.g. , , ) 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,https://www.w3.org/TR/rdf-sparql-query/ do Jena, Virtuoso e rdflib.lista jena 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.