Estruturas de dados, Gerenciamento de memória e Algoritmos em C#
O trabalho de qualquer programa pressupõe uma mudança com os dados armazenados na memória, ou seja, no caso de dados de entrada específicos, receber dados de saída específicos. Obviamente, o conteúdo da memória deve sempre ser alterado conforme o esperado. Embora com o valor de saída o resultado de mudanças na memória deva ser sempre o mesmo, ainda há um debate acadêmico sobre a sequência de ações a serem realizadas com partes diferentes da memória. Isso também se chama de trabalho determinístico do programa. Acontece que memória, dados e ações com eles são de importância fundamental. As linguagens de programação e matemática definem o kit de ferramentas apropriado para tudo isso. Como resultado, para trabalhar com informações, primeiro separamos condicionalmente 2 grupos, que se seguem. Eles são:
1 ․ A interface ou definições teóricas que indicam os tipos de dados a serem armazenados, as ações possíveis a serem tomadas com eles e problemas.
2 ․ A estrutura dos dados ou a representação prática da interface que define a forma como os dados são armazenados, representados e os algoritmos de resolução de problemas.
As interfaces, por sua vez, têm 2 grupos principais (página 86). Eles são:
1 ․ Conjunto ou série em que elementos devem ser únicos e diferentes entre si, por exemplo {a, b, a}, em que existem apenas 2 tipos de elementos, não havendo necessidade de repetições e ter duas coleções. As séries {a, b, c } a {a, c, b ] são iguais, ou seja, a disposição dos elementos não importa e as séries são desordenadas. Em C# os conjuntos são geralmente classificados, ou seja, classificados em ordem crescente. A ciência da computação definiu a árvore Hash para este grupo. Uma versão mais avançada é a Tabela de dispersão ou estrutura de mapa de hash.
2 ․ Sequência ou lista, uma sequência em que os elementos podem ser repetidos, mas ao mesmo tempo teremos conjuntos diferentes, por exemplo: (a, b, c) և (a, c, b) as sequências são diferentes e têm 3 elementos, ou seja, são regulares, ordenadas.
Na sequência estática, o número de elementos é constante, mas o valor de um elemento específico pode mudar. Um exemplo típico é um arranjo ou array, em que valor de um membro arbitrário pode ser lido ou alterado a qualquer momento e aleatoriamente. A RAM, Memória de acesso aleatório funciona segundo este princípio. No caso de coleções com índices, os itens são armazenados na memória diretamente próximos uns dos outros, contíguos.
Em Sequência Dinâmica você pode não só obter o valor dos elementos, mas também adicionar um novo elemento em qualquer parte, ou seja, alterar o comprimento. Um exemplo típico é a Lista ligada. No caso de coleções de referência, os elementos são armazenados nos partes diferentes da memória. Isso tem um efeito negativo na performance.
O iten recém-adicionado pode ser registrado fisicamente após os outros, e somente os ponteiros mudarão de valor que mostram outro membro. Excluir um elemento encurta a lista com o mesmo princípio. No caso de um conjunto dinâmico, é difícil aplicar um elemento arbitrário, pois antes de chegar a esse elemento é necessário aplicar o primeiro elemento, ler as referências uma a uma.
Deve ser entendido que estes são antes de tudo conceitos, então cada linguagem estabelece suas próprias regras de jogo. Portanto, qualquer coleção tem suas vantagens e desvantagens. Não é possível alterar o comprimento do Arranjo, mas seu conteúdo pode ser obtido rapidamente em Θ (1). No caso da lista, o oposto é verdadeiro: o comprimento pode ser alterado, mas é difícil obter o conteúdo que requer Θ(n) tempo. Existe também o conceito de Arranjo Dinâmico, implementado como ArrayList en C#, que está na faixa desses dois, qualquer elemento pode ser lido em Θ (1), mas só pode ser adicionado ào parte final. A tabela mostra a desempenho de operações possíveis com estruturas.
Com a implementação da estrutura de dados na prática, fica claro que um explícito pode ser usado explicitamente ou implicitamente, especialmente quando ele precisa ser capaz de alterar seu comprimento. Um ponteiro foi usado no código explicitamente.
Cada vez que partes diferentes da memória são alocadas para trás, depois de terminar o trabalho o programa tem que limpar a memória com a ajuda do Garbage Collector. Este é um processo não determinístico, que é especialmente evidente quando se tem uma Rreferência fraca. Pressupõe que o objeto pode ser usado, mas pode ser apagado da memória também, o que, simplesmente, implica a existência de coincidências. Algumas linguagens, incluindo C # e seu CLR, fazem isso automaticamente, embora possam ser usadas obviamente. Conheceremos exemplo assim na próxima parte. O resultado é o seguinte:
No nível físico, os dados podem ser gravados sequencialmente, mas de acordo com a representação gráfica, as estruturas de dados são Lineares e Não Lineares. Os conceitos de Array, Stack, Queue, List e Linked List, suas modificações, são lineares. List é baseado em Array, e Linked List com sua vária Doubly Linked List funciona com um ponteiro. Não lineares são Graph e Tree, cuja ideologia se aproxima das estruturas Hash Table, Dictionary e cujos elementos se caracterizam por serem diferentes de zero e têm um valor único, ou seja, Sets. A árvore binária é composta de células ou Nodes, cada um dos quais tem no máximo 2 sub-células. No caso da árvore binária de busca, o subtipo esquerdo deve ser menor do que o um no destro, e a árvore de busca binária AVL também tem um fator de equilíbrio, que é a diferença no número de células da esquerda para a destra. É claro que, no caso de árvores, a duplicação do elemento não é incentivada, pois por definição as células podem ser organizadas em ordem crescente, como no caso da Árvore de Busca Binária.
É necessário distinguir os conceitos de “Arranja” e “Estrutura de Dados”. Para entender melhor, vamos examinar o trabalho do código a seguir.
Usando os comandos “Person[]” e “«int[]” declaramos um arranjo de tipos Person e Int cujos elementos são acessados por indexação quando digitamos “arrayOfPerson[0] = new Person(){};“ e “ arrayOfInt[1] = 10;”.
Com os mesmos tipos temos as coleções “LinkedList<Person>” e “«int[]”, cujas commando “listOfPerson.AddFirst(new Person { });” ou “arrayOfInt[1] = 10;” adiciona um elemento novo. (XXX)
Usando o comando “LinkedList<Person>[]” ou “LinkedList<int>[]” criamos um Arranjo de Listos, cujos elementos são coleções de listas vinculadas quem inicialmente têm referências nulas, portanto antes de adicionar um iten à lista “arrayOfLinkedListOfPerson[0].AddFirst(new Person() { });” a instrução é para alocar espaço da memória. Então “arrayOfLinkedListOfPerson[0].AddFirst(new Person() { });»” comando, adiciona um valor ao primeiro elemento do array, que é uma lista.
Com o comando “«LinkedList<Person[]>” e “LinkedList<int[]>” anunciamos uma lista de arrays Person[] e int[]. Com “linkedListOfArrayOfPerson.AddLast(new Person[]{new Person { }, new Person { } });” e “linkedListOfArrayOfInt.AddLast(new int[] { 1,1});” adicionamos um array à lista. Cada elemento de array pode ser de tipo Person [] e conter nome, sobrenome e correio eletrónico ou ser do tipo int [] e conter números inteiros.
Em C #, o espaço de nomes System.Collections oferece ArrayList, BitArray, Hashtable, Queue, SortedList, Stack e etc., o espaço de nomes System.Collections.Specialized oferece HybridDictionary, ListDictionary, StringCollection, BitVector3 e etc., a o espaço de nomes System.Collections.Generic é para Dictionary<TKey, TValue> , LinkedList <T>, List <T>, Queue <T>, SortedDictionary <TKey, TValue>, SortedSet <T> e Stack<T> (Pro C# 9 with .NET 5, Foundational Principles and Practices in Programming, Página 371).
Todos os elementos de ArrayList podem ser acessados igual e arbitrariamente com Random Access. Ele pode conter tipos diferentes de dados ao mesmo tempo. Por ser um arranjo, permite que seu conteúdo seja indexado no tempo Θ (1). Um iten novo é adicionado a partir do final e todo o conteúdo é armazenado na memória contíguo. Depois de consumir o volume de memória alocado, todos os elementos da arranjo são copiados para outra seção maior da memória. Este processo sobrecarregarão da memória.
Um exemplo de estrutura de dados usando um ponteiro é LinkedList. Cada célula, Nó, pode ser fisicamente posicionada longe das outras células. A célula contém 2 peças, uma é para o valor e outra para a referência de próxima célula. Leva tempo Θ (n) para obter o valor, ou seja, 198 etapas são executadas para obter a 198ª célula. Excluir ou adicionar o primeiro e último elemento leva tempo Θ (1), e excluir ou ler os elementos restantes acontece em Θ(n) + Θ(1). A célula da Lista duplamente ligada contém 3 partes, um para valor original, outro para se referir à próxima e para célula anterior, portanto, requer mais memória. O primeiro e ultimo element estão disponível imediatamente, no tempo O (1). Como as células não precisam ser contíguo na memória, elas podem ser armazenadas em áreas da memória arbitrárias, possivelmente distantes. Por esse motivo, registrar uma célula nova é rápido, mas obter uma célula específica é relativamente lento, pois você tem que ler todas as células que existiam antes. Ter um link duplicado resolve os problemas de segurança, pois se uma célula de LinkedList normal for danificada, a conexão com a próxima será perdida e, no caso de links duplicados, teremos um “Plano B”. No caso de Unrolled Linked List, cada célula pode ter mais do que um valor. Vamos escrever o seguinte código.
Na cadeia intLinkedList, o número 40 é inserido, depois adicionamos 41 antes dela e econtinuamos adicionar números até և 50. De 40, que é o fim da cadeia, 30, 31, etc. são adicionados. Como resultado da operação deste código, o seguinte é impresso:
List se assemelha a um array, portanto, permite que seus elementos específicos sejam indexados. Implementado com base em LinkedList ou Array dinâmico.
Um novo número é adicionado à lista de números gerados aleatoriamente com Insert (), excluído com RemoveAt () e invertido com Reverse (). O resultado é o seguinte:
O Stack é como uma pilha de pedras, então fica claro que o topo está disponível primeiro. Funciona segundo o princípio “Last in, First Out” ou “Último a entrar, Primeiro a sair”. A ação realizada em um momento concreto refere-se ao último elemento adicionado.
Os comandos Push para adição e Pop para remoção aplicam-se apenas à parte superior. Stack funciona com base em LinkedList ou array. O programador parece estar lidando com uma lista ou array, mas é limitado em suas ações e só pode agregar valor num lado único. A pilha pode ter um volume fixado, se está implementada numa base de arranjo. Como abstração, Stack se refere aos princípios de alocação de memória no hardware. Um trecho da memória é fornecido para cada thread. Esta memória é usada para armazenar variáveis de comprimento fixo — “Tipos de valor”. O código é o seguinte:
Os números são adicionados ordem aumentada(XXX), mas como a pilha opera com um principio UEPS, a ação realizada num momento concreto se refere ao último elemento adicionado.
Queue ou a fila é uma coleção na qual os dados são adicionados no lado e as operações são realizadas no lado oposto. É como uma fila de pessoas. Funciona com o princípio de “First In, First Out” ou “Primeiro a entrar, Último a sair”
O tipo subjacente do Queue é a Lista duplamente ligada, porque nesse caso a adição e subtração do valor nos pontos finais é feita em tempo O(1), o que é muito eficaz. Fila Duplamente Terminada é uma abstração mais geral, caso em que a mesma ação pode ser executada tanto no fim como ao início. Ou seja, que Queue e Stack são casos especiais de Fila Duplamente Terminada. Outro caso é a Fila de prioridades, que em seu conceito é semelhante à Lista e, podendo ser implementada com um arranjo desordenado. A fila de prioridades duplamente Terminada permite excluir os elementos maiores e menores facilmente, pois possui configurações predefinidas. É implementado com um tipo subjacente Árvore binária de busca balanceada.
Como resultado do trabalho de código, temos o seguinte resultado.
Existem estruturas de dados cujos elementos não podem ser duplicados ou nulos. Estas são as coleções que operam com par “Chave — valor”. A principal abstração desse grupo é o Vetor associative, que é realizado com uma tabela hash ou árvores binárias. Função hash é o método convencional para obtenção estruturas tais e processar com os chaves, que por sua vez requere lugares na memória imprevisivelmente, tornando-as uma arranjo separada de elementos indexados que toma lugar fixado na memória. Ou seja, o método converte a chave para o campo de valor original ao “código Hash”, que por sua vez é usado como um índice. Mas, ao contrário dos arrays, no caso de estruturas hash, ao adicionar um novo elemento, os elementos existentes não são duplicados de uma parte da memória para outra. Blockchain pode ser obtido com criptografia e Hashing. As representações práticas da arranjo associativo são Dictionary, SortedDictionary e SortedList. SortedSet também contém valores únicos, mas não possui uma chave. Funciona da seguinte maneira:
No Dicionário declarado, Add() adiciona números inteiros e dados de tipo de Person. O comando Remove(2) exclui a linha cuja chave é 2. Como resultado, temos o seguinte.
SortedDictionary é outro tipo de estrutura de dados que opera com base no “Chave-valor”. Mas, neste caso, os elementos são organizados em ordem crescente da chave, embora os elementos sejam adicionados de forma irregular. No SortedSet, os itens também são classificados em ordem crescente, independentemente dos valores inseridos.
Como resultado, temos linhas classificadas em ordem de chaves .
SortedList և SortedDictionary difere apenas na performance. Em ambos os casos, o recebimento de um elemento leva tempo O (log n). Para deletar uma extensão de valor em SortedDictionary é O (log n), em SortedList é geralmente O (n). O código compara a adição, remoção e localização de um elemento.
O desempenho do mesmo cálculo varia dependendo da arquitetura do computador e do sistema operacional․ Por esse motivo, determinar a velocidade do algoritmo por tempo ou pelo número de instruções do processador não é uma opção eficaz. Portanto, a eficiência dos algoritmos é medida pelo número de etapas realizadas. A tabela a seguir mostra as estimativas de velocidade das operações realizadas nas estruturas de dados.
Por exemplo, encontrar o elemento maior ou o menor em uma arranjo ordenado classificada é feito em uma etapa, pois os valores já estão classificados em ordem crescente ou decrescente. No caso de arranjo não-ordenado, todos os valores devem ser verificados, ou seja, 500 comparações serão realizadas em um coleção contendo n = 500 elementos. É denotado por “O (n)”.
A forma mais comumente usada de estruturas de dados não lineares é a Árvore binária de busca balanceada. Os elementos pequenos são mantidos à esquerda, os grandes à destra. Neste exemplo, adicionamos o número 1 à estrutura initial. Comparamos a raiz com 25, depois com 20 e assim por diante. Adicionar o número 4 move-o com 1. 8 novamente se encaixa entre 9 e 4. Conforme os números 45 e 42 se acrescenta , eles são transferidos para outras células quando necessário.
Neste exemplo, a altura da árvore é de 4 pontos. O número máximo de elementos da última árvore com altura de 7 é 72 ou 128. Para encontrar a posição de 1, só 7 etapas são necessárias, o que corresponde à equação “Log2 (128) = 7”.
O Grafo também é uma coleção de células interconectadas, os vértices. É muito conveniente para modelar redes de computadores e fazer cálculos logísticos.
Um exemplo de grafo são os objetos usados no programa, que podem ser armazenados na memória ou vinculados uns aos outros de forma irregular. Quando o processo é iniciado, o CLR aloca espaço para todos os objetos no heap gerenciado sempre que encontra a palavra-chave “new”, até que a quantidade de memória virtual alocada para o processo se esgote. Mas quando a memória virtual se esgota, torna-se necessário limpar a memória. Durante esse tempo, o CLR congela todas os Threads no processo e começa a verificar os objetos.
Gerações de objetos são usadas para melhorar Garbage Collector. O objeto recém-criado é da geração 0 e da mais probabilidade de ser limpo. Se não forem limpos, todos os objetos são desfragmentados e são copiados na memória sequencialmente, resultando em 1 geração. Depois de sobreviver ao Garbage Collector, os objetos se tornam 2 gerações. Objetos com um volume de mais de 85.000 bytes podem ter apenas 2 gerações, mas são chamados de 3 gerações às vezes.
Os objetos têm 3 status durante o processo:
1․ Root, que são diretamente acessíveis ao aplicativo, são o ponto inicial de referência para objetos armazenados no heap gerenciado, como variáveis globais, embora não presentes em C#, variáveis locais, campos estáticos uo “Static Fields” e Fila de finalização.
2. Objeto vivo, objetos ativos ainda em uso e são acessíveis pelo root;
3. Objetos mortos, objetos inacessíveis e não são usados pelo programa.
No exemplo a seguir, temos objetos que contêm links entre si, para cada um dos quais tem o número de links entrados.
Um dos objetos não é usado em algum momento! Como resultado, a variável que indica o número de links torna-se 0.
GarbageCollector limpa as partes da memória ocupadas por objetos que não estão usando.
Mas essa abordagem não funciona para objetos com referências cíclicas, pois cada objeto sempre será relatado com outro objeto. Um dos algoritmos que resolve esse problema se chama “Mark and Sweep”. Nestes casos, é formada uma Queue para cada vértice da raiz, que indica seus vizinhos, ou seja, os elementos a que se refere.
Os vizinhos de R são B e C. B tem 1 caso, C, que já está registrado. Os vizinhos de C são D e E. D não tem vizinho. Adjacente de E está F e um de F é G. G não tem referências mais, então você pode deletar os vértices que não contêm links da curva raiz. Este algoritmo não se fragmenta, objetos registrados em diferentes partes da memória permanecem espalhados. No caso do algoritmo “Stop and Copy”, são os objetos que são registrados em queue, não os referências deles. Esse algoritmo pode funcionar lentamente, mas garante que a coleção seja usada rapidamente.
Em geral, todos os elementos de dados de estrutura são diretamente ou indiretamente exclusivos. Mesmo no caso de array, existe um valor único, o índice. A diferença é que a definição do índice depende da linguagem de programação, é definido implicitamente e no caso de chaves definidas explicitamente, cabe ao programador evitar as duplicações.
Você pode encontrar o código completo no GitHub: AdvancedConcepts, DataStructures
Referências de informação completa usada
Introduction to Algorithms
https://youtube.com/playlist?list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY
Advanced Data Structures
2) https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/
https://youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf
Performance Engineering of Software Systems
4) Pro C # 9 with .NET 5, Foundational Principles and Practices in Programming, Andrew Troelsen
5) CLR via C#, Developer Reference, Jeffrey Richter, 4th Ed., página 505
Para aprednder mais visita https://docs.google.com/document/d/1qaFg7lVacBkBEAeicetvihny10VO-_HV/
