Arrays [ORGANIZING]

Olá, sejam bem-vindos a mais uma aula do nosso curso! Na aula de hoje teremos nossa primeira estrutura, a estrutura fundamental, que vai servir de base para muitas outras. Hoje falaremos de arrays, estrutura de dados que usamos para lidar com sequências. Hoje entenderemos seu funcionamento, sua facetas e discutiremos seu funcionamento interno.

Array Abstract Data Type

O array é essa região contígua de memória que usamos para guardar a nossa sequência de itens. Você provavelmente já trabalhou com arrays e deve lembrar que em arrays podemos, em geral, fazer as seguintes operações:

indexação (get_at) - com um índice podemos encontrar um item específico dentro da nossa lista; arrays começam pelo índice zero;
exclusão (delete_at) - quando um item não é mais necessário podemos removê-lo;
atualização (set_at) - podemos definir o valor que cada índice do array vai conter;
busca (find) - podemos buscar um item, por seu valor, em um array;

Arrays Estáticos

A forma mais simples de um array, é um array estático, para começar mais simples vamos começar por ela. Um array estático encaixa perfeitamente na descrição que vimos durante a definição da ADT. um array estático vai ser criado a partir da alocação de uma região contígua da memória. Uma vez definido, suas dimensões não mudam, por isso o estático. Em C, a definição de um array é tal qual

int main() {
    int primes[4] = {1, 3, 5, 7}

    return 0;
}

Esta é a sintaxe em C para definir um array que pode possuir até 4 inteiros. É legal vermos que isso é de fato uma sequencia contígua de memória. C nos permite fazer isso uma vez que temos acesso aos endereços das variáveis que estamos utilizando.

Adicionando o seguinte trecho logo após a criação de primes:

for(int i=0; i < 4; i++) {
    printf("Index %d is at address: %p\n", &primes[i]);
}

esse código printa o endereço de cada posição. Perceba que é os endereços são parecidos variandos os últimos digitos da esquerda para a direita.

eles vao basicamente incrementando de quatro em quatro. isso acontece porque um inteiro ocupa 4 bytes, logo cada item vai ocupar um slot de 4 bytes na memoria.

Vejamos agora algumas operacoes com esse array.

Indexacao

Uma vez que o array está definido em com dados, é últil que possamos ler informações dessa lista. As vezes queremos ler de posições específicas, as vezes queremos percorrer inteira, digamos que voce deseja somar os itens de um array.

Para recuperar/ler um valor de um array, basta que você informe o índice desejado começando de 0 até o tamanho do array menos 1.

Então, em nosso array de primos temos 4 items. Temos os valores 1, 3, 5, 7 que ficam nos índices, 0, 1, 2 e 3 respectivamente.

printf("Primeiro item do array: %d\n", primes[0]);
printf("Segundo item do array: %d\n", primes[1]);
printf("Terceiro item do array: %d\n", primes[2]);
printf("Quarto item do array: %d\n", primes[3]);

Busca

Para buscarmos um item em um array precisamos percorre-lo e comparar item a item.

Definição

No código nós já incializamos o array na criação. Isso não precisa ser feito na verdade. Poderíamos também telo-inicializado como vazio - algo parecido com vazio

int primes[4];

Mas o que queremos ver aqui é como definir item, como por coisas em um array. Fazemos isso com indexação. Que determina em que lugar o valor desejado será colocado. Por exemplo, para colocar algo na primeira posição usamos o índice zero, fazendo algo como

primes[0] = 11;

Podemos seguir assim até o fim do array

primes[1] = 17;
primes[2] = 19;
primes[3] = 23;

Exclusao

Exclusoes nao sao possíveis em arrays estáticos. Uma vez que você definiu um array de 4 posições, como fizemos, ele vai ter 4 posições.

Podemos, naturalmente setar o valor de um índice como 0 ou -1 no caso desse arry de primos. Essa abordagem, no entanto, essa abordagem deixa buracos.

Idealmente você não quer ter esses buracos, o que faz com que você precise mover elementos, dependendo de onde o item removido se encontra.

Em nosso array de primos, se removermos o item no índice 0, precisamos mover os elementos de índice 1, 2 e 3 para a esquerda.

Para um controle melhor vamos ter uma variável size

void delete_at(int index, int primes[], int *size);
void print_array(int primes[], int *size);

int main() {
    int primes[] = {1, 2, 3, 5};
    int capacity = 4;
    int size = 4;

    delete_at(0, primes, &size);
    print_array(primes, size);

    printf("Capcity: %d\nSize: %d\n", capacity, size);

    return 0;
}

void print_array(int primes[], int size) {
    for(int i = 0; i < size; i++) {
        printf("primes[%d] is %d\n", i, primes[i]);
    }
}

void delete_at(int index, int primes[], int *size) {
    if (index < 0 || index > *size) {
        fprintf(stderr, "Index out of bounds\n");
        return;
    }

    for (int i = index; i < *size - 1; i++) {
        primes[i] = primes[i + 1];
    }

    *(size)--;
}

Isso faz com que tenhamos dois valores diferentes referentes a um array: capacidade e tamanho. Capacidade diz respeito a quantos items aquele array pode ter. Em nosso exemplo são quatro.

Tamaho é diz respeito à quantidade de itens no array naquele momento.

Em Go podemos encontrar isso em Slices com a definição de length e capacity.

Nos tópicos avançados faremos algo um pouco mais dinamico com malloc e free. Mas isso já adiciona um dinamismo maior ao array, que é o nosso próximo tópico.

Arrays Dinamicos

Arrays dinâmicos são tal quais arrays estáticos, com a diferença de que não são estáticos. Em um array dinâmico, a quantidade de items é arbitrária. O array pode (virtualmente) crescer indefinidamente.

As operações mostradas anteriormente são iguais em sua maioria. A mudança acontece na exclusão onde não precisamos nós mesmos lidar com o dinamismo dos itens.

Ao deletar o array, ele se ajusta em si mesmo. Arrays dinamicos são largamente utilizados em linguagens mais de alto nível e de tipagem dinâmica como Ruby e JavaScript.

arr = [1, 2, 3, 5]

arr.delete_at(0)

# [2, 3, 5]

Nota de eficiencia: como arrays dinamicos funcionam por debaixo dos panos?

Os conceitos de length e capacity não necessariamente se aplicam aqui. Pelo menos não em Ruby que é a linguagem que utilizaremos. Isso fica a cargo da runtime que vai sim lidar com isso.

Alocação inicial

A alocação inicial de um array é feita com um tamanho definido. Em ruby, na versao em que estou, usando o módulo objspace o array vazio inicializa com 40bytes de memória alocados. Isso acontece por conta que um espaço mínimo precisa ser alocado.

Na implementação do MRI, o endereço incialmente alocado para o array se mantém o mesmo. Internamente é feita uma realocação do array, aumentando seu tamanho. O endereço pode mudar, embora não tenha sido esse o caso. Podemos averiguara isso na quantidade de memória alocada.

A medida que o array cresce

Quanto mais items são adicionados ao array, mais memória é necessária. Quando está ficando sem espaço uma nova alocação maior em algum fator é feita para acomodar os itens do array. Essa nova alocação recebe todos os itens do espaço antigo. Uma cópia é feita.

É difícil ver o endereço mudar, pelo menos nessa máquina. Mas é fácil de ver esse comportamento pela quantidade de memória alocada.

Topico avançado: Um dia na vida de um array dinâmico

Arrays [DRAFT]

nota pra mim -> quando for organizar por na seguinte ordem: 1. o adt de um array estático; 2. cada operacao em um array estático, mostrando exemplos em C; 3. ADT de um array dinamico; 4. passar por cada operacao do array dinamico mostrando exemplos em ruby;

ADT de um array estático

get
set
delete_at
search

ADT de um array dinamico

get
set
delete_at
search

Como um array funciona

Olá, sejam bem-vindos a nossa primeira aula realmente vendo as estruturas de dados. Começaremos hoje pela estrutura fundalmental. Um array é uma sequência de itens, que é um bloco de memória alocado por aquele processo. Em essencia, arrays sao estagicos.

na aula anterior vimos como a memória funciona; quando o array é criado, uma região de memória contígua é alocada. então, aquela regiao é associada a esse array e com isso conseguimos trabalhar nossos itens com indexacao.

[mostra uma regiao de memoria e discorre sobre como a associacao é feita pelos indices, calculando com base no endereco inicial]

Voce provavelmente já trabalhou com arrays em algum momento. Se você trabalha em uma linguagem de mais alto nível como Ruby, vai ver que os arrays são dinamicos. Diferentes desse que acabamos de ver.

Em ruby voce cria um array

fruits = Array.new
fruits = []

Para esse array não foi definido tamanho e voce nem se preocupa com isso. Ele vai crescendo a medida que for necessário. Além disso você consegue ter items de diferentes tipos no mesmo array. Isso acontece graças ao runtime do Ruby, nesse caso, que lida com isso pra você.

Por debaixo dos panos

Ao inicializar um array eu ruby ou linguagens de mais alto nível, há de fato uma alocação de região contígua de memória. É definida uma capacidade para aquele array. A medida que itens vao sendo adicionados e a capacidade máxima é atingida o que acontece é:

uma nova região de memória com capacidade maior é alocada;
os itens são transferidos da regiao de memória anterior para a nova
libera a regiao de memoria anterior

Para casos em que o array cresce ainda mais, runtimes como NodeJs por exemplo, converte isso internamente em um hashmap.

Indexação (get)

Para buscarmos um item em específico usamos o índice. Índices, no geral são zero-based devido a forma que calculamos.

#include <stdio.h>
#include <stdlib.h>

int main() {
  int *ptr;
  int size = 5;

  int total_bytes = size * sizeof(int);

  ptr = (int*)malloc(total_bytes);

  printf("%d bytes allocated\n", total_bytes);

  for (int i=0; i < size; i++) {
    printf("O índice %d do array inicia em: %p (aritmetica de ponteiro: %p)\n", i, &ptr[i],&(ptr[i]) + 1);
  }

  free(ptr);

  return 0;
}

Delete

Deletar um item de um array estático diz respeito a remover o valor de um índice em específico uma vez que não é possível remover um slot.

Em C, indexamos aquele item que queremos “remover” e setamos como NULL. Essa é uma operação de tempo constante.

Search

Buscar em um array é uma operação linear. Em uma lista de frutas, encontrar a fruta pera envolve percorrer o array e ir checando se o valor desejado já foi encontrado.

Perceba nesse código em C que a partir do início simplesmente calculamos o próximo endereço.

Array Dinamico

Um array dinamico tem características muito semelhantes com a diferença que ele é dinamico e pode crescer a medida que items são adicionados. As operações mudam também.

Indexação

Funciona normalmente, uma vez definido o array, os itens podem ser indexados normalmente.

Search

Também continua igual.

Delete

Aqui muda. A exclusao de um item de um array dinamico faz com que todos os items sejam movidos. Se você tem um array de 5 items e remove o primeiro, acontece que todos os outros items da direita serão movidos para a esquerda para preencher aquele espaço deixado.

Remover é contante, porém mover os itens é linear. Em um array dinamico não temos “buracos deixados” por uma remoção.

Referencias

https://medium.com/dailyjs/how-do-i-get-started-with-v8-development-17e976ebe4af https://itnext.io/v8-deep-dives-understanding-array-internals-5b17d7a28ecc - entendendo aspectos internos de array em javascript https://embarcados.com.br/ponteiro-em-c-aritmetica-de-ponteiro/ https://gist.github.com/totherik/3a4432f26eea1224ceeb https://ivoanjo.me/blog/2021/02/11/looking-into-array-memory-usage/