Estrutura de dados
Uma estrutura de dados (ED), em ciência da computação, é uma coleção tanto de valores quanto de operações. É 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.
Imagem: Manuel Jorge Marques · BY-NC-ND · Openverse
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.
Imagem: Jessica Aquino · BY-NC-SA · Openverse
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. 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: 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 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: 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.
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.
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 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 20 Hz a 20 kHz, 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 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, serão escritas em Javascript com bibliotecas como D3.js. 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.
Imagem: Felipe_Borges · BY-NC-ND · Openverse
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: 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).
Template para formalização de conhecimento sobre uma ED
Observada a literatura, um vocabulário sobre EDs pode seguir o seguinte padrão: Passível de formalização como vocabulário SKOS.
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. 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.
