Aprenda Programação: Vetores, Cadeias de Caracteres, Coleções e Estruturas de Dados

Créditos para a imagem: Imagem criada pelo autor usando o programa Spectacle.

Aprenda Programação: Vetores, Cadeias de Caracteres, Coleções e Estruturas de Dados

Publicado por Franco Eusébio Garcia

Publicado em 16/12/2021

Última atualização em 08/01/2022

Descrição

Programação permite processar e analisar grandes quantidades de dados (por exemplo, centenas ou milhões de amostras). Contudo, declarar uma variável por valor não é algo conveniente. Como alternativa, pode-se usar estruturas de dados e coleções, que permitem armazenar, acessar e manipular múltiplos valores usando por meio uma única variável que abstrai a memória necessárias para todas as amostras. Aprenda a usar vetores, cadeias de caracteres e coleções. Exemplos em Python, Lua, JavaScript, GDScript (para Godot Engine), Scratch e Flowgorithm.

Esta página está disponível nos seguintes idiomas:

Compartilhar

#AprendaProgramação
#FrancoGarciaCom

Sumário

Pré-Requisitos

Na introdução sobre ambientes de desenvolvimento, indiquei Python, Lua e JavaScript como boas escolhas de linguagens de programação para iniciantes. Posteriormente, comentei sobre GDScript como opção para pessoas que tenham interesse em programar jogos digitais ou simulações. Para as atividades de introdução a programação, você precisará de, no mínimo, um ambiente de desenvolvimento configurado em uma das linguagens anteriores.

Caso queira experimentar programação sem configurar um ambiente, você pode usar um dos editores online que criei:

Contudo, eles não possuem todos os recursos dos interpretadores para as linguagens. Assim, cedo ou tarde, você precisará configurar um ambiente de desenvolvimento. Caso precise configurar um, confira os recursos a seguir.

Assim, se você tem um Ambiente Integrado de Desenvolvimento (em inglês, Integrated Development Environment ou IDE) ou a combinação de editor de texto com interpretador, você está pronto para começar. Os exemplos assumem que você saiba executar código em sua linguagem escolhida, como apresentado nas páginas de configuração.

Caso queira usar outra linguagem, a introdução provê links para configuração de ambientes para as linguagens C, C++, Java, LISP, Prolog e SQL (com SQLite). Em muitas linguagens, basta seguir os modelos da seção de experimentação para adaptar sintaxe, comandos e funções dos trechos de código. C e C++ são exceções, por requerem o uso de ponteiros para acesso à memória.

Tipos de Dados Compostos e o Fim de Uma Era

Em Tipos de Dados, antecipou-se a existência de tipos de dados compostos, que incluem, dentre outros, cadeias de caracteres (strings), vetores (arrays), conjuntos (sets), uniões (unions) e registros (records). Este é um bom momento para introduzi-los com mais detalhes.

Este tópico apresenta tipos de dados compostos que permitam armazenar múltiplos valores que sejam acessíveis por meio de uma única variável. Muitos deles são, a rigor, implementados como registros. De forma genérica, eles podem ser pensados como coleções de dados.

Assim como uma bolsa permite armazenar vários objetos, e adições, remoções, ou obtenção de itens de interesse armazenados, coleções permitem armazenar, recuperar e acessar dados. O acesso é feito por meio de uma chave (key) ou identificador (identifier, id ou ID arbitrário definido pela programadora ou programador), usado para identificar unicamente um elemento armazenado. A chave ou identificador pode ser implícita (por exemplo, uma ordem) ou explícita (por exemplo, um valor arbitrário definido como uma chave sintética ou surrogate key); o tipo de dado usado também pode variar.

Qualquer que seja o caso, coleções permitem manipular múltiplos valores de forma conveniente e eficiente. Combinando-se coleções com estruturas de repetição, pode-se processar e manipular valores de sucintamente, em poucas linhas de código.

Deste tópico em diante, você poderá processar milhões de dados, caso assim desejar ou precisar. Para isso, conceitos como inserção, remoção, busca e ordenação tornar-se-ão parte de seu vocabulário de programação. O objetivo é apresentar como usar as operações em coleções. Para evoluir em programação, é interessante aprender a criar algumas das principais coleções; contudo, como implementar estruturas de dados está fora do escopo deste tópico em particular.

Ademais, a partir deste tópico, algumas linguagens também estarão fora de escopo desta introdução à programação. Aproxima-se, pois, o fim de uma era, pois suas habilidades ultrapassarão os recursos de duas linguagens de programação. O tópico sobre vetores será o último com suporte para Scratch e Flowgorithm, pois nenhuma das duas linguagens fornece implementações para dicionários, registros e arquivos. Embora seja possível criar um dicionário nas linguagens, isso não será feito neste tópico. Scratch e Flowgorithm são ferramentas para aprendizagem; após vetores, os recursos finais explorados serão comuns em linguagens de programação de propósito general, mas incomuns em linguagens para aprendizagem.

De fato, após estes últimos tópicos, você poderá usar a maioria dos recursos essenciais que linguagens de programação fornecem para a resolução de problemas. Coleções permitiram trabalhar com dados em larga escala; registros permitirão a construção de seus próprios tipos de dados; arquivos permitirão usar memória secundária para armazenar e recuperar dados permanentemente (isto é, exceto em caso de falha de hardware).

Quase todo o potencial de programação está ao seu alcance. Embora existam outros tópicos para explorar e muito a aprender, muitos conceitos serão incrementais para aprimoramento de técnicas. A base está quase toda formada.

Vetores (Arranjos ou Arrays) e Listas (Lists)

Praticamente toda linguagem de programação moderna fornece um tipo de dados para vetores (arranjos ou arrays) e/ou listas (listas). Algumas linguagens definem vetores e/ou listas com mais operações e recursos avançados; outras apresentam o mínimo necessário para o funcionamento. A rigor, listas são estruturas de dados mais complexas e práticas que vetores, fornecendo recursos e conveniências adicionais. Contudo, o uso é semelhante e muitas linguagens de programação permitem usá-las como vetores (na falta de um tipo para arrays). Exceto caso mencionado o contrário, este tópico tratará listas como vetores, pois elas, de fato, serão similares em linguagens como Python e GDScript.

Em geral, um vetor abstrai uma seqüencia contígua de posições de memória em uma única variável. Pode-se pensar em um vetor como se fosse uma caixa com repartições, na qual a próxima repartição está ao lado da anterior. Também pode-se pensar em um vetor como se fossem colunas de uma tabela com uma única linha.

Por exemplo, um vetor que armazenasse nomes de linguagens de programação pode ser pensado da seguinte forma:

|-----+--------+------------+----------+---+-----+------+------+--------+-----|
| Lua | Python | JavaScript | GDScript | C | C++ | Java | Lisp | Prolog | SQL |
|-----+--------+------------+----------+---+-----+------+------+--------+-----|

Um vetor representa um bloco de memória. O exemplo da tabela de linguagens de programação retrata um vetor de cadeias de caracteres. Normalmente, pode-se criar vetores de quaisquer tipos de dados (sejam eles primitivos ou compostos). Inclusive, pode-se criar vetores de vetores, para, por exemplo, criar matrizes. Vetores de vetores serão discutidos em uma subseção desta página. Antes do mais complexo, convém aprender o mais simples.

Existem dois conceitos para o tamanho de um vetor. Pode-se pensar no tamanho total do vetor (em bytes) e no tamanho como a capacidade do vetor (o número de valores que se pode armazenar no vetor, também chamado de comprimento). Ambos os tamanhos podem ser fixos ou variáveis.

O tamanho total do vetor em bytes depende do tipo de dados que será armazenado. Dependendo da linguagem de programação, cada repartição pode ter um tamanho fixo (mesmo tamanho em bytes para toda repartição do array) ou um tamanho variável. Linguagens de nível mais baixo, como C e C++, costumam possibilitar a definição de tamanhos fixos, pois elas permitem que programadores e programadores manipulem e gerenciem a memória de um programa. Nesse caso, o vetor é um bloco de memória contínuo dividido em uma certa quantidade de blocos menores de tamanhos iguais (matematicamente, o comprimento é o tamanho total em bytes dividido pelo tamanho do tipo de dados a ser armazenado). Linguagens de nível mais alto, como Lua, Python, JavaScript e GDScript podem gerenciar a memória automaticamente (com limites), facilitando o uso de repartições de tamanho variável. Em particular, é possível que um mesmo vetor inclusive armazene valores de diferentes tipos de dados.

Na prática, contudo, é mais usual referir-se a tamanho como capacidade do vetor. O bloco de memória é repartido em um número de repartições que define o tamanho (ou comprimento) do vetor. O exemplo fornecido anteriormente armazena dez cadeias de caracteres em um vetor. O tamanho de um vetor pode ser fixo ou variável, algo que depende da implementação. Alguns autores chamam vetores de tamanho fixo como arrays e vetores de tamanhos variáveis como vetores. Neste material, os termos array e vetor são considerados sinônimos.

Linguagens de programação de alto nível costumam fornecer vetores com comprimento variável (variable size arrays ou variable length arrays). Esse é o caso de Lua, Python, JavaScript e GDScript. Em vetores de tamanho variável, a implementação (ao invés da programador ou do programador) é responsável por gerenciar a memória necessária, ajustando o tamanho conforme o número de elementos armazenados no vetor. Caso se adicione um novo elemento, o vetor pode aumentar de tamanho automaticamente para acomodá-lo. Para se remova um elemento, o vetor pode reduzir de tamanho para evitar desperdícios de memória. Por questões de eficiência, é comum que implementações possam utilizar vetores maiores que o número de elementos ao invés do tamanho exato, para amortizar custos de alocação e desalocação dinâmica de memória em múltiplas operações (ao invés de cada uma delas).

Linguagens de programação de baixo nível tendem a fornecer vetores com comprimento fixo (fixed size arrays ou fixed length arrays), declarado estaticamente (via alocação estática de memória). Vetores com tamanho fixo podem possuir melhor desempenho, mas menor flexibilidade. Deve-se conhecer o número de valores que será armazenado em tempo de desenvolvimento (programação). Caso contrário, corre-se o risco de desperdiçar memória com vetores maiores que o necessário, ou faltar memória caso se declare um vetor muito pequeno. Para se criar um vetor de tamanho variável em tempo de uso, pode-se usar alocação dinâmica de memória.

Independentemente do caso, cada repartição de um vetor está em um endereço de memória específico. Contudo, para facilitar a operação com vetores, linguagens abstraem o endereço na forma de um índice ou deslocamento (offset) baseado no endereço inicial do vetor. Em linguagens de programação, o índice costuma ser um número inteiro. A indexação costuma ser feita na forma nome_vetor[numero_indice], sendo nome_vetor um vetor de um determinado tipo de dados e indice um número inteiro. Assim, o uso de um vetor é similar ao de uma variável convencional para tipos primitivos; a diferença é a necessidade de especificar-se o índice desejado para uma posição de memória específica. Por exemplo, o vetor de nomes de linguagens de programação poderia chamar nomes_linguagem e ser do tipo vetor de cadeia de caracteres. A sintaxe pode variar, assim como o critério utilizado para indexação. Para indexação, cada linguagem de programação define um critério, sendo duas escolhas mais comuns.

A primeira é iniciar a indexação em zero, como feito em JavaScript, Python, GDScript e Flowgorithm. Na indexação iniciada em zero, índices variam de 0 até tamanho - 1. Por exemplo, para o vetor de nomes de linguagens de programação, nomes_linguagem[0] corresponderia ao valor Lua, nomes_linguagem[3] corresponderia ao valor GDScript e nomes_linguagem[9] corresponderia ao valor SQL. nomes_linguagem[10] não existe no vetor; tentar acessá-lo resultaria em um erro, com dois resultados prováveis: falha de segmentação (segmentation fault) que travaria o programa (com sorte), ou acesso à uma posição de memória indevida (com azar). Portanto, é necessário tomar cuidado para não usar índices incorretos para posições de memória que não sejam definidas pelo vetor.

Endereço de Memória	E₁	E₂	E₃	E₄	E₅	E₆	E₇	E₈	E₉	E₁₀
Índice	0	1	2	3	4	5	6	7	8	9
Valor	Lua	Python	JavaScript	GDScript	C	C++	Java	Lisp	Prolog	SQL

A segunda abordagem é iniciar a indexação em um, como feito em Lua e Scratch. Na indexação iniciada em um, índices variam de 1 até tamanho. Por exemplo, para o vetor de nomes de linguagens de programação, nomes_linguagem[1] corresponderia ao valor Lua, nomes_linguagem[3] corresponderia ao valor JavaScript e nomes_linguagem[10] corresponderia ao valor SQL. nomes_linguagem[0] não existe no vetor; tentar acessá-lo resultaria em um erro.

Endereço de Memória	E₁	E₂	E₃	E₄	E₅	E₆	E₇	E₈	E₉	E₁₀
Índice	1	2	3	4	5	6	7	8	9	10
Valor	Lua	Python	JavaScript	GDScript	C	C++	Java	Lisp	Prolog	SQL

Pode-se observar que a indexação corresponde à forma idiomática de iteração em uma estrutura de repetição. Isso não é coincidência, mas uma praticidade para operação com índices de vetores.

Além disso, algumas linguagens de programação ou implementações permitem usar números negativos como índices. Em Python e GDScript, índices negativos acessam os índices positivos em ordem reversa. Por exemplo, -1 corresponde à última posição do vetor, -2 à penúltima e assim por diante. Em C e C++, a linguagem assume que índices sejam inteiros sem sinal. Tentar usar um número como -1 como índice do vetor faria com o que o número fosse interpretado como o maior número inteiro positivo possível para o número de bytes considerado para o tipo do índice. Em outras palavras, o acesso muito provavelmente resultaria em erro.

Vetores Versus Listas

Antes de começar a apresentar exemplos, convém destacar que listas não são, necessariamente, equivalentes a vetores. Ao contrário do que comumente ocorre com vetores, os valores de uma lista sequer precisam estar em posições contíguas de memória. De fato, nem toda implementação de lista permite acessar um elemento usando um índice. Algumas implementações de listas definem operações para acessar o próximo elemento e o elemento anterior de uma lista baseando-se no elemento atualmente considerado. Como resultado, a navegação em elementos de listas pode ser significativamente mais lenta que em vetores propriamente ditos (pois pode ser necessário percorrer todos os elementos anteriores até se chegar no desejado). Algumas implementações amenizam o problema usando um alternativa chamada lista duplamente encadeada (doubly linked list ou deque).

Contudo, existem implementações que permite operar com listas como se elas fossem vetores. Isso comumente ocorre caso a implementação utilize um vetor com memória contígua para definição da lista (array list). Esse é o caso de linguagens como Python e GDScript, que são adotadas nesta introdução. Para o caso de Python, pode-se consultar custos de operações na wiki oficial.

Além disso, é comum que listas forneçam operações que nem sempre está disponível para arrays. Um dos principais exemplos é o reajuste automático de tamanho para adaptar o tamanho disponível ao número de elementos armazenados. Isso pode ser feito, por exemplo, usando-se listas encadeadas (listas ligadas ou linked lists) ou realocando-se o array quando necessário.

Fluxogramas: Flowgorithm

A declaração de vetores em Flowgorithm segue os mesmos passos da declaração de uma variável. Após criar um bloco Definição (Declare), escolha um nome para o vetor. Antes de confirmar a criação, marque a opção Arranjo? (Array?). Após marcar a opção, deve-se escolher um tamanho para o vetor. O tamanho escolhido corresponderá ao número máximo de valores que o vetor poderá armazenar (vetores, portanto, tem tamanho fixo em Flowgorithm).

A indexação de vetores em Flowgorithm inicia-se em 0. Para atribuir um valor a um vetor, crie um bloco Atribuição (Assign). No bloco, escolha o nome do vetor em variável, seguido do índice entre colchetes (por exemplo, vetor[0] para a primeira posição).

Pode-se usar o vetor em qualquer campo que permitir o uso de uma variável. Para isso, basta escrever o nome do vetor seguido do índice entre colchetes.

O trecho de código a seguir contém a transcrição do texto da imagem.

Principal

Caracteres Arranjo vetor[10]
vetor[0] = "Olá"
vetor[1] = "meu"
vetor[2] = "nome"
vetor[3] = "é"
vetor[4] = "Franco"
vetor[5] = "!"

Saída vetor[0]
Saída vetor[4]
Saída vetor[5]

vetor[0] = "Oi"

Saída vetor[0]
Saída vetor[4]
Saída vetor[5]

Fim

Como o vetor tem tamanho fixo, é importante não ultrapassar o tamanho máximo declarado. No exemplo, vetor declarou 10 posições de memória para armazenar dados do tipo cadeia de caracteres, mas usou 6. Assim, as posições de memória 6, 7, 8 e 9 ainda poderiam ser usadas para armazenar dados. Entretanto, posições a partir de 10 não podem ser usadas; usá-las seria um erro de lógica.

Alternativamente, caso não se quisesse desperdiçar nenhuma posição declarada, poder-se-ia declara vetor com tamanho 6. Declarar um tamanho com vetor 1 possa parecer semelhante a declarar uma variável, o resultado não é, exatamente, equivalente. Regras para uso de vetor continuam valendo para o tamanho unitário. Por exemplo, ainda será necessário usar o índice e, em muitas linguagens de programação, a passagem do vetor como parâmetro será por referência. Caso seja necessário diferenciar ambos, variáveis que não sejam vetores podem ser ditas escalares. Escalar é, de certa forma, o termo contrário à vetorial. Por exemplo, em Física, existem grandezas escalares (como tempo e posição) e vetoriais (como velocidade).

Linguagens de Programação Visual: Scratch

Para criar vetores em Scratch, deve-se acessar Variáveis (Variables), depois escolher Criar uma Lista (Make a List). Após escolher um nome para a lista (vetor), surgirão novos blocos para manipulá-lo.

Para executar um programa várias vezes, é útil começar o código com um bloco apague todos os itens de vetor (Delete all of array). Isso deve ser feito para cada vetor declarado; caso contrário, a próxima execução poderá manter os itens da última execução no vetor. Para exibir todos os valores armazenados, pode-se adicionar, também, mostre a lista vetor (show list vetor).

Para adicionar um valor ao vetor, pode-se usar o bloco adicione coisa a vetor (add thing to vetor). Para acessar o valor de uma posição no vetor, pode-se usar o bloco item 1 de vetor (item 1 of vetor). Para modificar o valor de uma posição do vetor, pode-se usar o bloco substitua o item 1 de vetor por thing (replace item 1 of array with thing). Vetores em Scratch iniciam a indexação em 1 (assim como em Lua).

Existem blocos para algumas outras operações que serão discutidas neste tópico. Assim, caso você queira, você pode usar Scratch para o aprendizado de vetores.

Linguagens de Programação Textual: JavaScript, Python, Lua e GDScript

O uso de vetores em JavaScript, Python, Lua e GDScript é bastante similar. Todas as linguagens são de alto nível e fornecem implementações convenientes para vetores. A rigor, apenas JavaScript e GDScript definem arrays. Python define listas que podem ser usadas como arrays, enquanto Lua utiliza tabelas (tables) indexadas por valores inteiros.

//           0      1      2       3    4         5
let vetor = ["Olá", "meu", "nome", "é", "Franco", "!"]
console.log(vetor[0])
console.log(vetor[4])
console.log(vetor[5])

vetor[0] = "Oi"
console.log(vetor[0])
console.log(vetor[4])
console.log(vetor[5])

#        0      1      2       3    4         5
vetor = ["Olá", "meu", "nome", "é", "Franco", "!"]
print(vetor[0])
print(vetor[4])
print(vetor[5])
print(vetor[-1])
print(vetor[-2])
print(vetor[-6])

vetor[0] = "Oi"
print(vetor[0])
print(vetor[4])
print(vetor[5])

--             1      2      3       4    5         6
local vetor = {"Olá", "meu", "nome", "é", "Franco", "!"}
print(vetor[1])
print(vetor[5])
print(vetor[6])

vetor[1] = "Oi"
print(vetor[1])
print(vetor[5])
print(vetor[6])

extends Node

func _ready():
    #            0      1      2       3    4         5
    var vetor = ["Olá", "meu", "nome", "é", "Franco", "!"]
    print(vetor[0])
    print(vetor[4])
    print(vetor[5])
    print(vetor[-1])
    print(vetor[-2])
    print(vetor[-6])

    vetor[0] = "Oi"
    print(vetor[0])
    print(vetor[4])
    print(vetor[5])

O comentário antes de declaração do vetor relaciona o índice com o valor armazenado no vetor. Os exemplos em Python e GDScript também ilustram o uso de índices negativos. Tente usá-los em Lua ou JavaScript para observar os erros resultantes.

Muitas linguagens de programação definem um par de colchetes como operador para acessar um valor armazenado em um índice de um vetor. Linguagens que não forneçam um operador tendem a disponibilizar subrotinas para as operações.

Para iterar sobre valores de um vetor, pode-se usar estruturas de repetição (laços ou loops). Algumas linguagens de programação também fornecem funcionalidades mais práticas, como iteradores. Um exemplo é a estrutura de repetição para cada (for each), que simplifica a escrita de código para iterar sobre todos os elementos de uma coleção. Sempre que possível, este tópico utilizará iteradores.

//           0      1      2       3    4         5
let vetor = ["Olá", "meu", "nome", "é", "Franco", "!"]
for (let indice = 0; indice < vetor.length; ++indice) {
    console.log(vetor[indice])
}

for (const indice in vetor) {
    console.log(vetor[indice])
}

// Caso não se pretenda modificar o valor, pode-se usar const ao invés de let.
for (let valor of vetor) {
    console.log(valor)
}

#        0      1      2       3    4         5
vetor = ["Olá", "meu", "nome", "é", "Franco", "!"]
for indice in range(len(vetor)):
    print(vetor[indice])

for valor in vetor:
    print(valor)

--             1      2      3       4    5         6
local vetor = {"Olá", "meu", "nome", "é", "Franco", "!"}
for indice = 1, #vetor do
    print(vetor[indice])
end

for indice, valor in ipairs(vetor) do
    print(indice, valor)
end

extends Node

func _ready():
    #            0      1      2       3    4         5
    var vetor = ["Olá", "meu", "nome", "é", "Franco", "!"]
    for indice in range(len(vetor)):
        print(vetor[indice])

    for valor in vetor:
        print(valor)

Nos exemplos usando a estrutura de repetição para tradicional, utiliza-se o tamanho (comprimento) do vetor como limite superior. Para obter-se o tamanho do vetor, pode-se usar:

Em JavaScript, a propriedade length (documentação);
Em Python, a função len() (documentação);
Em Lua, o operador de comprimento # (documentação);
Em GDScript, a função len() (documentação).

Em linguagens de programação que não forneçam uma função ou método para obter o tamanho, uma boa alternativa é criar uma variável ou constante para armazenar o valor (ao invés de digitá-lo sempre que necessário). Assim, caso se queira alterá-lo posteriormente, a refatoração será mais simples e rápida.

Nos exemplos usando para cada, duas variações são comuns:

O iterador retorna cada valor armazenado em uma coleção;
O iterador retorna a chave ou índice que permite acesso ao valor armazenado. Neste caso, pode-se acessar o valor usando valor = nome_vetor[chave].

Lua, em particular, define ipairs() (documentação), que retorna o índice numérico e o valor armazenado. Caso não se queira utilizar um dos valores (índice ou valor), é comum nomear a variável com um underscore (_). No caso do valor, também é possível omiti-lo (for indice in ipairs(vetor) do).

Além disso, JavaScript, Python, Lua e GDScript permitem misturar valores de diferentes tipos em um mesmo vetor. Isso significa que é possível criar um vetor com [1, "Franco", -1.23, Verdadeiro]. Embora seja possível, eu recomendaria evitar esse tipo de uso, pois ele requer que se conheça o tipo esperado para cada índice. Ou seja, é fácil cometer erros. Portanto, é preferível usar vetores que armazenem dados de um mesmo tipo ao invés de misturá-los em um único vetor.

Operações e Técnicas Usando Vetores

Além de acessar um valor usando ou índice ou iterar sobre todos os valores, existem algumas operações comuns para manipulação de vetores:

Obtenção do tamanho (size ou length): obtenção do tamanho atual do vetor, como apresentado anteriormente;
Verificação de lista vazia (empty): verifica se o tamanho é igual a zero. Implementações com tamanho máximo também podem fornecer funções ou métodos para verificar se uma lista está cheia (full). O tamanho máximo é, por vezes, chamado de capacidade (capacity) do vetor ou da lista. Na prática, mesmo em listas sem limites, sempre existirá uma capacidade máxima ditada pela quantidade de memória livre disponível no computador. Tentar alocar memória quando não há memória suficiente disponível não é possível (o programa travará, ou emitirá uma exceção ou outro erro);
Inicialização: atribuição de um valor inicial para todas as posições do vetor;
Escrita ou impressão (write, print ou dump): escrita de todos os valores no vetor. Em linguagens de programação de alto nível, é comum que comandos ou procedimentos como escreva() imprimam todos os valores. Isso pode ser feito, por exemplo, em JavaScript, Python e GDScript. A alternativa é iterar por todo o vetor e escrever cada um dos valores. Isso deve ser feito, por exemplo, em C, C++ e Lua. É conveniente definir um procedimento para escrita de vetores nessas linguagens para evitar repetir código, como será feito em todos os exemplos para Lua desta seção.
Acumulação de valores (reduce): como em estruturas de repetição, acumulação de resultado em uma variável durante iteração em elementos de um vetor;
Seleção ou filtro de valores (filter): criação de um novo vetor com valores iterados de outro vetor que satisfaçam a um determinado critério;
Busca seqüencial (find ou search): tentativa de encontrar se um valor existe (ou não) no vetor;
Ordenação (sort) e busca binária (binary search): ordenação de valores segundo uma regra (por exemplo, ordem crescente ou ordem decrescente).
Cópia (duplicação ou clone): geração de um novo vetor idêntico ao original.

Bibliotecas de linguagens de programação costumam fornecer implementações pré-definidas para muitas das operações anteriores.

Em linguagens de programação que implementam vetores com tamanho variável ou como listas, existem três operações adicionais:

Inserir (add, insert, append, push) novo elemento (potencialmente aumentando o tamanho do vetor ou lista);
Remover (remove, delete, pop) elemento existente (potencialmente reduzindo o tamanho do vetor ou lista);
Limpar (empty, clear) o vetor, isto é, remover todos os valores armazenados.

Com estruturas condicionais e estruturas de repetição, é possível implementar as operações anteriores, cada uma linguagem não as forneça.

Em muitas linguagens de programação, é importante notar que vetores são comumente passados por referência para subrotinas. Em outras palavras, alterações de dados dentro de subrotinas normalmente são persistentes, pois alteram valores usando o endereço da variável original ao invés de uma cópia. Isso permite criar subrotinas para inicializar e alterar valores de vetores.

Nos exemplos a seguir, a versão em Lua do código será freqüentemente maior que as demais porque inclui algumas subrotinas úteis para manipulação de vetores. Além disso, é importante notar que vetores em Lua começam no índice 1 e terminam em tamanho. Em JavaScript, Python e GDScript, vetores começam em 0 e terminam em tamanho -1.

Declaração e Inicialização

Linguagens de programação nas quais vetores são estáticos (com tamanho fixo) definem o tamanho do vetor durante a declaração. Linguagens de programação com vetores dinâmicos ou listas permitem redimensionar o vetor de acordo com os elementos armazenados.

JavaScript, Python, Lua e GDScript enquadram-se no segundo caso. JavaScript, Python e GDScript permitem especificar o tamanho de um vetor na declaração ou com uma subrotina apropriada. Em Lua (e também nas outras linguagens), é possível criar um vetor vazio e adicionar novos elementos até atingir-se o tamanho desejado.

let vetor = new Array(100)
console.log(vetor.length)
// Valores iniciam-se como undefined.
console.log(vetor[0])

// Alternativa:
vetor = []
for (let i = 0; i < 100; ++i) {
    vetor.push(0)
}

console.log(vetor.length)
console.log(vetor)

vetor = 100 * [0] # 0: valor inicial; poderia ser qualquer outro.
print(len(vetor))
# Valores iniciam-se com o valor inicial escolhido.
print(vetor[0])

# Alternativa:
vetor = []
for i in range(100):
    vetor.append(0)

print(len(vetor))
print(vetor)

-- Procedimento para escrita de vetores (como nas outras linguagens).
-- Uma implementação melhor seria recursiva, para permitir a escrita de vetores
-- armazenados dentro de vetores.
-- Um exemplo será fornecido posteriormente para dicionários em
-- `escreva_tabela()` (que poderá ser usado tanto para vetores quanto para
-- dicionários -- ambos são tabelas em Lua).
function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write(vetor[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

-- Exemplo começa aqui.
local vetor = {}for i = 1, 100 do
    -- Alternativa: table.insert(vetor, 0)
    vetor[#vetor + 1] = 0
end

print(#vetor)
escreva_vetor(vetor)

extends Node

func _ready():
    var vetor = []
    vetor.resize(100)
    print(len(vetor))
    # Valores iniciam-se com null.
    print(vetor[0])

    # Alternativa:
    vetor = []
    for i in range(100):
        vetor.append(0)

    print(len(vetor))
    print(vetor)

Para a inserção de valores, usou-se:

JavaScript: push() (documentação);
Python: append() (documentação);
Lua: table.insert() (documentação). Também usou-se io.write() (documentação) para se escrever uma mensagem sem uma quebra de linha;
GDScript: append() (documentação). Em GDScript, também usou-se resize() (documentação) para definir um tamanho inicial.

Caso se quisesse criar um vetor com 1000 posições de memória ao invés de 100, bastaria trocar o número. Também é possível definir o tamanho com uma constante (por exemplo, TAMANHO_VETOR ou COMPRIMENTO_VETOR).

A forma alternativa é válida para as quatro linguagens e permite escolher um valor inicial para cada posição de memória. No exemplo, todos as posições foram inicializadas com 0. Pode-se alterar o valor conforme as necessidades do problema (por exemplo, "", Falso, 0.0, "Franco").

Deve-se notar que nem toda linguagem define um valor inicial para pré-alocações baseadas em tamanho. Por exemplo, C e C++ não o fazem para arrays (exceto caso inicializados explicitamente com algo como {}); o valor inicial será indeterminado, pois terá quaisquer valores que estivessem nos endereços de memória antes da declaração. Esses valores são, por vezes, chamados de lixo. Não se deve, pois, assumir valor inicial para vetores recém-criados caso a linguagem não forneça garantias de inicialização.

JavaScript, Python e GDScript permitem escrever valores armazenados em vetores usando console.log() ou print(), mas Lua escreve o endereço do vetor. Assim, os exemplos em Lua definem um procedimento chamado escreva_vetor() para escrever valores de um vetor de forma simplificada. Uma implementação mais robusta seria recursiva e consideraria outros possíveis valores armazenados em tabelas (como dicionários). Outra alternativa para a escrita de vetores simples consiste em usar table.unpack() (ou apenas unpack(), dependendo da versão de Lua, como 5.1; documentação).

print(table.unpack({1, 2, 3}))
local vetor = {1, 2, 3}
print(table.unpack(vetor))

Contudo, table.unpack() também não escreve os elementos recursivamente. Por exemplo, table.unpack({{1, 1}, 2, 3}) escreverá um endereço ao invés de 1 1 para o primeiro vetor.

Inicialização para Poucos Valores

Para poucos valores ou valores conhecidos de antemão (em tempo de programação), muitas linguagens de programam permitem realizar a inicialização diretamente na declaração de um vetor.

let vetor = [1.1, 2.2, 3.3, 4 * 1.1, 1.1 + 1.1 + 1.1 + 1.1 + 1.1]
console.log(vetor)

vetor = [1.1, 2.2, 3.3, 4 * 1.1, 1.1 + 1.1 + 1.1 + 1.1 + 1.1]
print(vetor)

function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write(vetor[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

local vetor = {1.1, 2.2, 3.3, 4 * 1.1, 1.1 + 1.1 + 1.1 + 1.1 + 1.1}
escreva_vetor(vetor)

extends Node

func _ready():
    var vetor = [1.1, 2.2, 3.3, 4 * 1.1, 1.1 + 1.1 + 1.1 + 1.1 + 1.1]
    print(vetor)

Em linguagens de programação com vetores de tamanho fixo, o compilador ou interpretador comumente é capaz de inferir o tamanho correto do vetor a partir dos elementos definidos.

Algumas linguagens de programação requerem que o último valor não seja separada por vírgula (por exemplo, [1, 2, 3]). Entretanto, linguagens modernas ou versões mais recentes podem permitir (por exemplo, [1, 2, 3,]). O uso da vírgula após o último valor pode ser prático para uso com sistemas de controle de versões, como git, e comandos para destacar diferenças em arquivos, como diff.

O comando diff permite realçar diferenças entre dois arquivos diferentes, algo bastante usado em sistemas de versões para destacar alterações entre a versão anterior e a nova versão de um arquivo. Com isso, pode-se montar um histórico de diferenças. Por exemplo, a modificação de um código em um arquivo chamado 1.js, definido como a seguir:

let v = [
    1,
    2,
    3,
]

Para um arquivo 2.js, definido como a seguir:

let v = [
    1,
    2,
    3,
    4,
]

Realçaria apenas a inclusão da nova linha, ao invés de realçar a deleção da linha 3 e a inserção de duas linhas (3, e 4) em um comando como diff 1.js 2.js.

4a5
>     4,

Para a versão sem vírgula no último valor, o resultado da diferença seria como a seguir:

4c4,5
<     3
---
>     3,
>     4

Embora a diferença seja pequena, algumas pessoas preferem um histórico de diferenças de versões mais limpo (algo que pode ser útil para práticas como revisões de código ou code reviews). Assim, terminar o último valor com uma vírgula pode ser interessante para esse propósito, por reduzir ruído e permitir focar em diferenças mais significativas.

Versões recentes de JavaScript, Python, Lua e GDScript permitem o uso da vírgula no último elemento.

Lua e Vetores

Vetores em Lua são, na realidade, um caso especial do uso de uma estrutura de dados chamada table (tabela) na linguagem, otimizada para o uso de um índice numérico. Assim, a linguagem utiliza chaves tanto para a declaração de vetores, quanto para a declaração de dicionários (ambos são tabelas). Um par de colchetes em Lua, portanto, não declara um vetor vazio.

Uma decorrência da escolha é o fato de Lua permitir a inicialização valores para um vetor em qualquer índice, criando um vetor esparso. Em um vetor esparso, posições de memória são alocadas apenas para índices que armazenem valores que não sejam vazios, para evitar desperdícios de memória. Por exemplo, fazer local v = {} e, em seguida, v[123] = 123 é válido em Lua, enquanto resultaria em erro em muitas outras linguagens de programação. O vetor resultante teria apenas um elemento definido, no índice 123. Contudo, o operador de tamanho # não retornará o valor correto para tamanho. Em Lua 5.1, é possível usar table.maxn() para obter o maior índice numérico em uma tabela (documentação). Em versões mais recentes, é preciso implementar uma rotina para executar o mesmo processamento.

-- Para Lua 5.2 ou mais recente.
-- Para Lua 5.1, pode-se usar table.maxn().
function maxn(tabela)
    local resultado = 0
    for key in pairs(tabela) do
        if (type(key) == "number") then
            if (key > resultado) then
                resultado = key
            end
        end
    end

    return resultado
end

-- Caso queira adicionar maxn() para acessar via table.maxn():
-- table.maxn = table.maxn or maxn

local v = {}
v[123] = 123
print(v[123])
-- O operador de tamanho não informará o tamanho correto até adicionar-se
-- valores até o índice definido.
print(#v)
-- Como alternativa, pode-se usar `table.maxn()` (Lua 5.1).
-- A linha também é válida caso se tenha adicionado a implementção maxn() em
-- table.maxn.
-- print(table.maxn(v))
print(maxn(v))

v[1] = 1
v[2] = 1
v[3] = 1
print(#v, maxn(v))

Em geral, para fazer a mesma operação em outras linguagens de programação, seria necessário declarar um vetor com, ao menos, 123 posições de memória ou adicionar 123 elementos em uma lista antes de poder usar o índice. As demais 122 posições de memória não seriam utilizadas, mas requereriam memória. Como alternativa, poder-se-ia usar um dicionário para a criação de uma estrutura semelhante.

Inserções, Remoções e Limpeza

Em listas ou vetores dinâmicos, é possível modificar o número de elementos armazenados por meio de operações de inserção e remoção de valores. Pode-se começar com um vetor vazio (por exemplo, [] em JavaScript, Python e GDScript, ou {} em Lua) e adicionar-se valores conforme necessário, ou pode-se começar um vetor com alguns elementos.

Inserções e remoções podem ocorrer no início, no fim ou em uma posição arbitrária entre a primeira e a última.

Inserções em posição arbitrárias costumam ser chamadas de acrescentar (add), inserir (insert), ou empurrar (push). Inserções no fim comumente chamam-se anexar (append) ou empurrar para trás (push back). Inserções no início comumente chamam-se o prefixar (prepend) ou empurrar para frente (push front).

Remoções no fim são comumente chamadas de pop (algo como estourar) ou pop back. Em pilhas, o termo é traduzido como desempilhar. No início, remoções são comumente chamadas chamadas de pop front. A remoção de todos os valores é comumente chamado de limpeza, limpar (clear) ou esvaziar (empty).

Pode ser interessante reproduzir os exemplos a seguir linha a linha, para observar cada um dos resultados. Evidentemente, no caso de blocos de códigos em estruturas condicionais ou de repetição, e de subrotinas, pode-se usar o bloco todo de uma vez.

let vetor = [] // Também pode ser feito como vetor = new Array()
// Inserção no fim.
vetor.push(1)
vetor.push(2)
vetor.push(3)
// Escrita ou impressão.
console.log(vetor) // [1, 2, 3]

// Remoção do fim.
let valor_removido = vetor.pop() // 3
console.log(vetor) // [1, 2]

// Limpeza.
// JavaScript não possui uma função pré-definida para limpeza.
while (vetor.length > 0) {
    vetor.pop()
}
console.log(vetor) // []

// Inserções e remoções em posições arbitrárias.

// Vetor inicial.
vetor.push(1)
vetor.push(3)
console.log(vetor) // [1, 3]

// Inserção no início.
vetor.unshift(0)
console.log(vetor) // [0, 1, 3]
// Remoção no início.
valor_removido = vetor.shift()
console.log(vetor) // [1, 3]
// Inserção em posição arbitrária.
vetor.splice(1, 0, 2) // Índice, número de valores a remover, valor a inserir.
console.log(vetor) // [1, 2, 3]
// Remoção em posição arbitrária.
valor_removido = vetor.splice(2, 1) // 2 é o índice, 1 para remover um valor.
console.log(vetor) // [1, 2]

vetor = [] # Também pode ser feito como vetor = list()
# Inserção no fim.
vetor.append(1)
vetor.append(2)
vetor.append(3)
# Escrita ou impressão.
print(vetor) # [1, 2, 3]

# Remoção do fim.
valor_removido = vetor.pop() # 3
print(vetor) # [1, 2]

# Limpeza.
vetor.clear()
print(vetor) # []

# Inserções e remoções em posições arbitrárias.

# Vetor inicial.
vetor.append(1)
vetor.append(3)
print(vetor) # [1, 3]

# Inserção no início.
vetor.insert(0, 0) # Índice, valor.
print(vetor) # [0, 1, 3]
# Remoção no início.
valor_removido = vetor.pop(0) # Índice.
print(vetor) # [1, 3]
# Inserção em posição arbitrária.
vetor.insert(1, 2) # Índice, valor a se inserir.
print(vetor) # [1, 2, 3]
# Remoção em posição arbitrária.
valor_removido = vetor.pop(2) # 2 é o índice.
print(vetor) # [1, 2]

function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write(vetor[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

local vetor = {}
-- Inserção no fim.
table.insert(vetor, 1)
vetor[#vetor + 1] = 2 -- Forma alternativa.
table.insert(vetor, #vetor + 1, 3) -- Forma equivalente.
-- Escrita ou impressão.
escreva_vetor(vetor) -- [1, 2, 3]

-- Remoção do fim.
local valor_removido = table.remove(vetor) -- 3
escreva_vetor(vetor) -- [1, 2]

-- Limpeza.
-- Lua não possui uma função pré-definida para limpeza.
while (#vetor > 0) do
    table.remove(vetor)
end
escreva_vetor(vetor) -- []

-- Inserções e remoções em posições arbitrárias.

-- Vetor inicial.
table.insert(vetor, 1)
table.insert(vetor, 3)
escreva_vetor(vetor) -- [1, 3]

-- Inserção no início.
table.insert(vetor, 1, 0) -- Índice, valor.
escreva_vetor(vetor) -- [0, 1, 3]
-- Remoção no início.
valor_removido = table.remove(vetor, 1)
escreva_vetor(vetor) -- [1, 3]
-- Inserção em posição arbitrária.
table.insert(vetor, 2, 2) -- Índice, valor a se inserir.
escreva_vetor(vetor) -- [1, 2, 3]
-- Remoção em posição arbitrária.
valor_removido = table.remove(vetor, 3) -- 3 é o índice.
escreva_vetor(vetor) -- [1, 2]

extends Node

func _ready():
    var vetor = [] # Também pode ser feito como vetor = Array()
    # Inserção no fim.
    vetor.append(1)
    vetor.push_back(2) # Alternativa.
    vetor.append(3)
    # Escrita ou impressão.
    print(vetor) # [1, 2, 3]

    # Remoção do fim.
    var valor_removido = vetor.pop_back() # 3
    print(vetor) # [1, 2]

    # Limpeza.
    vetor.clear()
    print(vetor) # []

    # Inserções e remoções em posições arbitrárias.

    # Vetor inicial.
    vetor.append(1)
    vetor.append(3)
    print(vetor) # [1, 3]

    # Inserção no início.
    vetor.push_front(0) # Índice, valor.
    print(vetor) # [0, 1, 3]
    # Remoção no início.
    valor_removido = vetor.pop_front()
    print(vetor) # [1, 3]
    # Inserção em posição arbitrária.
    vetor.insert(1, 2) # Índice, valor a se inserir.
    print(vetor) # [1, 2, 3]
    # Remoção em posição arbitrária.
    valor_removido = vetor.pop_at(2) # 2 é o índice.
    print(vetor) # [1, 2]

O exemplo introduz várias subrotinas. Para comodidade do autor, os links para documentação serão da página com todas elas, ao invés de adicionar uma por uma. Minha recomendação é consultar também outras subrotinas listadas nas páginas, para conhecer outros recursos que a linguagem de programação de sua preferência forneça para manipulação de vetores. Algumas linguagens, como Python, fornecerão várias operações pré-definidas; outras, como Lua, fornecerão menos. Lua tem uma biblioteca padrão minimalista; para este material, pode-se entender o minimalismo como certa vantagem, pois ele permitirá ilustrar como implementar alguns recursos em linguagens que não ofereça algumas operações como parte da biblioteca padrão. Por sinal, a possibilidade de implementar recursos usando código é um diferencial importante entre software e hardware; por isso o início com soft (maleável, adaptável).

JavaScript: push(), pop(), unshift(), shift(), splice(): documentação;
Python: append(), pop(), clear(), insert(): documentação;
Lua: table.insert(), table.remove(): documentação;
GDScript: append(), push_back(), pop_back(), clear(), push_front(), pop_front(), insert() e pop_at(): documentação.

Em linguagens de programação que não forneçam uma subrotina para limpeza, pode-se repetir a operação de apagar um valor até que o vetor torne-se vazio (isto é, com tamanho zero).

Contudo, para a limpeza, por que não atribuir novamente um vetor vazio para a variável? A resposta depende de contexto. Algumas linguagens não permitem atribuir um novo vetor para uma variável que armazena o vetor.

Em particular, esse não é o caso para JavaScript, Python, Lua e GDScript, que permitem a atribuição de novo vetor vazio. Assim, deve-se considerar um segundo ponto: a memória do vetor é compartilhada?

Caso ela não seja, limpar o vetor existente ou atribuir um novo terão o mesmo resultado: um vetor vazio para a variável. Entretanto, caso o vetor fosse compartilhado, as outras variáveis continuariam com os valores do vetor original Isso ficará mais claro na subseção sobre cópias e memória compartilhada.

Busca Seqüencial

Algumas linguagens de programação fornecem subrotinas pré-definidas para busca seqüencial. Em linguagens que não as definem, como Lua, a implementação é simples: basta iterar pelo vetor e comparar o valor na posição atual com o valor procurado. Caso o valores sejam iguais, retorna-se o índice. Caso contrário, passa-se para o próximo valor. Caso o valor não seja encontrado até o fim, retorna-se um valor (por exemplo, -1) para indicar que o elemento não existe no vetor.

let vetor = [1, 2, 3, 4, 5]

// Busca seqüencial.
let indice_busca = vetor.indexOf(2)
console.log((indice_busca !== -1), indice_busca) // true 1

vetor = [1, 2, 3, 4, 5]

# Busca seqüencial.
try:
    indice_busca = vetor.index(2)
    print(indice_busca) # 1
except ValueError:
    print("Valor não encontrado.")

# Para verificar se um valor existe no vetor, pode-se usar:
# if (valor in vetor):
#     ...

function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write(vetor[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

function busca_sequencial(vetor, valor)
    for indice, valor_atual in ipairs(vetor) do
        if (valor == valor_atual) then
            return indice
        end
    end

    return -1
end

local vetor = {1, 2, 3, 4, 5}

-- Busca seqüencial.
-- Lua não possui uma função pré-definida para busca seqüencial.
local indice_busca = busca_sequencial(vetor, 2)
print((indice_busca ~= -1), indice_busca) -- true 2

extends Node

func _ready():
    var vetor = [1, 2, 3, 4, 5]

    # Busca seqüencial.
    var indice_busca = vetor.find(2)
    printt((indice_busca != -1), indice_busca) # true 1

JavaScript: indexOf() (documentação);
Python: index() (documentação);
Lua: não fornece uma subrotina;
GDScript: find() (documentação).

O exemplo em Lua ilustra a criação de uma subrotina para busca seqüencial. Como antecipado, exemplos em Lua normalmente serão mais longos devido a definição de subrotinas para implementar recursos presentes em outras linguagens de programação. Reunir todas as funções definidas em um arquivo como uma biblioteca pode ser uma boa idéia para uso futuro.

Acumuladores

O uso de acumuladores com vetores é semelhante ao uso com estruturas de repetição. A maior diferença é que os valores de interesse estão armazenados no vetor.

let vetor = [1, 2, 2, 3, 3, 3]

// Acumulação.
let acumulador = 0
for (const valor of vetor) {
    acumulador += valor
}
console.log(acumulador) // 14

let acumulador_string = ""
for (const valor of vetor) {
    acumulador_string += valor.toString()
    acumulador_string += " "
}
console.log(acumulador_string) // 1 2 2 3 3 3

vetor = [1, 2, 2, 3, 3, 3]

# Acumulação.
acumulador = 0
for valor in vetor:
    acumulador += valor

print(acumulador) # 14

acumulador_string = ""
for valor in vetor:
    acumulador_string += str(valor)
    acumulador_string += " "

print(acumulador_string) # 1 2 2 3 3 3

function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write(vetor[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

local vetor = {1, 2, 2, 3, 3, 3}

-- Acumulação.
local acumulador = 0
for _, valor in ipairs(vetor) do
    acumulador = acumulador + valor
end
print(acumulador) -- 14

local acumulador_string = ""
for _, valor in ipairs(vetor) do
    acumulador_string = acumulador_string .. valor .. " "
end
print(acumulador_string) -- 1 2 2 3 3 3

extends Node

func _ready():
    var vetor = [1, 2, 2, 3, 3, 3]

    # Acumulação.
    var acumulador = 0
    for valor in vetor:
        acumulador += valor

    print(acumulador) # 14

    var acumulador_string = ""
    for valor in vetor:
        acumulador_string += str(valor)
        acumulador_string += " "

    print(acumulador_string) # 1 2 2 3 3 3

Acumuladores podem ser de tipos não numéricos, como ilustrado com acumulador_string. No exemplo fornecido, a variável concatena todos os valores armazenados no vetor, utilizando um espaço como delimitador (seqüência de caracteres usada para separar itens) entre valores.

Em programação funcional, esta operação é comumente conhecida como reduce.

Seleção ou Filtro de Valores

Uma operação similar à acumulação é a seleção ou filtragem de valores de um vetor. A diferença é que, ao invés de combinar todos os itens de interesse em um único valor (normalmente escalar), cria-se um novo vetor armazenando valores de interesse.

Como exemplo, pode-se considerar a situação de filtrar valores ímpares de um vetor.

let numeros = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

// Seleção ou filtro.
let numeros_impares = []
for (const numero of numeros) {
    if (numero % 2 === 1) {
        numeros_impares.push(numero)
    }
}

console.log(numeros_impares)

numeros = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Seleção ou filtro.
numeros_impares = []
for numero in numeros:
    if (numero % 2 == 1):
        numeros_impares.append(numero)

print(numeros_impares)

function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write(vetor[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

local numeros = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

-- Seleção ou filtro.
numeros_impares = {}
for _, numero in ipairs(numeros) do
    if (numero % 2 == 1) then
        table.insert(numeros_impares, numero)
    end
end

escreva_vetor(numeros_impares)

extends Node

func _ready():
    var numeros = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

    # Seleção ou filtro.
    var numeros_impares = []
    for numero in numeros:
        if (numero % 2 == 1):
            numeros_impares.append(numero)

    print(numeros_impares)

Ao invés de apenas escrever os valores como feito até o tópico anterior, agora é possível selecionar e armazenar os valores de interesse em uma coleção. Isso permite manipulá-los posteriormente, sem necessitar repetir o laço e a seleção de dados. Uma vantagem da abordagem é a maior conveniência e potencial ganho de desempenho. Uma desvantagem é o maior consumo de memória, devido ao armazenamento dos valores no novo vetor.

Em programação funcional, esta operação é comumente conhecida como filter.

Ordenação e Busca Binária

Uma ordenação pode ser feita no próprio vetor (dita in-place) ou em uma cópia ordenada retornada como resultado (dita out-of-place). Para uma ordenação out-of-place, pode-se atribuir o resultado à variável original caso se queira salvar a versão ordenada.

A busca binária permite procurar por um valor de forma mais rápida e eficiente que a busca seqüencial, mas requer que o vetor esteja ordenado. A estratégia para busca binária foi apresentada intuitivamente para a adivinhação de números em estruturas de repetição (ou laços ou loops), no programa usando um gerador de números pseudoaleatórios.

Para referência, a complexidade em notação Big Oh para busca seqüencial é (linear), enquanto a notação para busca binária é (logarítmica). Para um vetor com 1 milhão de posições, o pior caso para a busca seqüencial requer 1 milhão de iterações. Na busca binária, o pior caso será , ou seja, cerca de 20 iterações.

A diferença sugere a importância de ordenação e busca binária em programação. Elas podem melhorar significativamente o desempenho de programas que precisem trabalhar com grandes quantidades de dados.

Também para referência, algoritmos de ordenação eficiente (como quicksort e mergesort) tem complexidade . Em outras palavras, nem sempre é mais rápido ordenar um vetor para, em seguida, procurar por um valor. Caso se queira buscar por apenas um único valor, por exemplo, pode ser mais rápido usar uma busca seqüencial. Por outro lado, caso o vetor já esteja ordenado, uma busca binária normalmente será significativamente mais rápida que uma seqüencial para vetores grandes. Da mesma forma, para problemas que requeiram múltiplas operações de busca, pode ser vantajoso ordenar o vetor primeiro para, em seguida, realizar buscas binárias.

É comum que bibliotecas em linguagens de programação forneçam uma implementação genérica de subrotina para ordenação de valores. Em geral, a subrotina padrão ordenará valores em ordem crescente (do menor para o maior), normalmente fornecendo algum recurso para modificar o critério de ordenação (algo particularmente útil para tipos compostos como registros). O recurso costuma ser uma função ordem(x, y) definida com os seguintes valores de retorno:

Se o valor for negativo, x deve aparecer antes de y;
Se o valor for positivo, x deve aparecer depois de y;
Se o valor for zero, pode-se manter a ordem.

Para valores numéricos, uma forma fácil de gerar um resultado para a expressão para ordenação em ordem crescente é retornar x - y. Para cadeias de caracteres, pode-se usar uma função que defina ordem alfabética. Deve-se decidir se letras minúsculas devam aparecer antes, depois ou na mesma ordem de letras maiúsculas. O critério usado habitualmente no cotidiano é chamado de natural sorting (ou natural sort order).

Em Python, Lua e GDScript, a implementação padrão para ordenação tende a ser o esperado. Em JavaScript, contudo, o uso da subrotina padrão resultará em surpresa caso um vetor tenha números negativos e positivos. Para evitar o problema, deve-se fornecer uma função definindo um critério para ordenação. A função pode ser pré-definida ou anônima (lambda).

function ordem_crescente(x, y) {
    // x > y -> x - y > 0 (x deve aparecer depois de y)
    // x < y -> x - y < 0 (x deve aparecer antes de y)
    // x === y -> x - y = 0 (ambos são iguais, pode-se manter a ordem)
    return (x - y)
}

let vetor = [7, 3, -3, -7, 9, 0]

// Ordenação.
console.log(vetor) // [7, 3, -3, -7, 9, 0]
vetor = vetor.sort() // Out-of-place.
// Errado:
console.log(vetor) // [-3, -7, 0, 3, 7, 9]
// Correto:
vetor = vetor.sort(ordem_crescente) // Out-of-place.
console.log(vetor) // [-7, -3, 0, 3, 7, 9]

// Alternativas:
// Função lambda.
vetor = [7, 3, -3, -7, 9, 0].sort(function(x, y) { // Out-of-place.
    return (x - y)
})
console.log(vetor) // [-7, -3, 0, 3, 7, 9]

// Função lambda com sintaxe moderna.
// (x, y) é a lista de parâmetros.
// => significa return
// (x - y) é a expressão com o valor de retorno.
vetor = [7, 3, -3, -7, 9, 0].sort((x, y) => (x - y)) // Out-of-place.
console.log(vetor) // [-7, -3, 0, 3, 7, 9]

// Busca binária.
// JavaScript não possui uma função pré-definida para busca binária.

vetor = [7, 3, -3, -7, 9, 0]

# Ordenação.
print(vetor) # [7, 3, -3, -7, 9, 0]
vetor.sort() # In-place
print(vetor) # [-7, -3, 0, 3, 7, 9]

# Busca binária.
# Python não possui uma função pré-definida para busca binária.

function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write(vetor[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

local vetor = {7, 3, -3, -7, 9, 0}

-- Ordenação.
escreva_vetor(vetor) -- [7, 3, -3, -7, 9, 0]
table.sort(vetor) -- In-place
escreva_vetor(vetor) -- [-7, -3, 0, 3, 7, 9]

-- Busca binária.
-- Lua não possui uma função pré-definida para busca binária.

extends Node

func _ready():
    var vetor = [7, 3, -3, -7, 9, 0]

    # Ordenação.
    print(vetor) # [7, 3, -3, -7, 9, 0]
    vetor.sort() # In-place
    print(vetor) # [-7, -3, 0, 3, 7, 9]

    # Busca binária.
    var tamanho_vetor = len(vetor)
    var valor_busca = 7
    var indice_busca = vetor.bsearch(valor_busca)
    printt((indice_busca < tamanho_vetor) and (vetor[indice_busca] == valor_busca), indice_busca)

    valor_busca = -4
    indice_busca = vetor.bsearch(valor_busca)
    printt((indice_busca < tamanho_vetor) and (vetor[indice_busca] == valor_busca), indice_busca)

    valor_busca = 77
    indice_busca = vetor.bsearch(valor_busca)
    printt((indice_busca < tamanho_vetor) and (vetor[indice_busca] == valor_busca), indice_busca)

Para a ordenação, os exemplos usaram:

JavaScript: sort() (documentação);
Python: sort() (documentação);
Lua: table.sort() (documentação);
GDScript: sort() (documentação).

Por outro lado, nem toda linguagem oferece uma implementação pré-definida para busca binária. JavaScript, Python e Lua não fornecem uma subrotina na biblioteca padrão. GDScript, por outro lado, fornece bsearch() (documentação). Deve-se atentar que, caso bsearch() não encontre o valor no vetor, ela retorna a posição para inserção que manteria o vetor ordenado. Assim, deve-se verificar o valor armazenado no índice antes para se certificar se ele realmente exista no vetor.

A busca binária é um algoritmo importante em programação. Convém, pois, saber como implementá-la.

Uma subrotina busca_binaria_recursiva() pode ter como parâmetros um vetor, um valor para se procurar, o indice_inicio e indice_fim para a busca. Ela pode retornar um valor inteiro com o índice do resultado (caso encontrado) ou um valor negativo caso o valor não conste no vetor. O vetor deve armazenar valores do mesmo tipo de valor. Para conveniência de uso, pode-se criar uma função para a chamada inicial da busca binária como busca_binaria(vetor, valor).

Para implementar uma busca binária, compara-se o valor da mediana (valor central de uma amostra) com o valor buscado. Caso o valor seja igual, retorna-se o índice da mediana (indice_meio). Caso contrário, existem três situações para se considerar:

Se o valor buscado for menor que o da mediana, sabe-se que ele deverá estar entre a posição inicial da busca e a posição da mediana. Em outras palavras, pode-se ignorar a busca em todos os índices da mediana para frente. Assim, pode-se realizar uma nova busca binária de indice_inicio até indice_meio - 1.
Se o valor buscado for maior que o da mediana, o valor buscado deverá estar entre a posição da mediana a posição final da busca. Assim, pode-se realizar uma nova busca binária de indice_meio + 1 até indice_fim.
Caso indice_inicio seja maior que indice_fim, o valor buscado não foi encontrado.

function busca_binaria_recursiva(vetor, valor, indice_inicio, indice_fim) {
    if (indice_inicio > indice_fim) {
        return -1
    }

    let indice_meio = Math.floor((indice_inicio + indice_fim) / 2)
    let valor_meio = vetor[indice_meio]
    if (valor === valor_meio) {
        return indice_meio
    } else if (valor < valor_meio) {
        return busca_binaria_recursiva(vetor, valor, indice_inicio, indice_meio - 1)
    } else {
        return busca_binaria_recursiva(vetor, valor, indice_meio + 1, indice_fim)
    }
}

function busca_binaria(vetor, valor) {
    return busca_binaria_recursiva(vetor, valor, 0, vetor.length - 1)
}

let vetor = [7, 3, -3, -7, 9, 0]

// Ordenação.
console.log(vetor) // [7, 3, -3, -7, 9, 0]
vetor = vetor.sort((x, y) => (x - y)) // Out-of-place.
console.log(vetor) // [-7, -3, 0, 3, 7, 9]

// Busca binária.
console.log(busca_binaria(vetor, -3))
console.log(busca_binaria(vetor, 0))
console.log(busca_binaria(vetor, 9))
console.log(busca_binaria(vetor, -4))
console.log(busca_binaria(vetor, 77))

def busca_binaria_recursiva(vetor, valor, indice_inicio, indice_fim):
    if (indice_inicio > indice_fim):
        return -1

    indice_meio = (indice_inicio + indice_fim) // 2
    valor_meio = vetor[indice_meio]
    if (valor == valor_meio):
        return indice_meio
    elif (valor < valor_meio):
        return busca_binaria_recursiva(vetor, valor, indice_inicio, indice_meio - 1)
    else:
        return busca_binaria_recursiva(vetor, valor, indice_meio + 1, indice_fim)

def busca_binaria(vetor, valor):
    return busca_binaria_recursiva(vetor, valor, 0, len(vetor) - 1)

vetor = [7, 3, -3, -7, 9, 0]

# Ordenação.
print(vetor) # [7, 3, -3, -7, 9, 0]
vetor.sort() # In-place
print(vetor) # [-7, -3, 0, 3, 7, 9]

# Busca binária.
print(busca_binaria(vetor, -3))
print(busca_binaria(vetor, 0))
print(busca_binaria(vetor, 9))
print(busca_binaria(vetor, -4))
print(busca_binaria(vetor, 77))

function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write(vetor[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

function busca_binaria_recursiva(vetor, valor, indice_inicio, indice_fim)
    if (indice_inicio > indice_fim) then
        return -1
    end

    -- Lua 5.3 ou mais recente.
    local indice_meio = (indice_inicio + indice_fim) // 2
    -- Versões mais antigas:
    -- local indice_meio = math.floor((indice_inicio + indice_fim) / 2)
    local valor_meio = vetor[indice_meio]
    if (valor == valor_meio) then
        return indice_meio
    elseif (valor < valor_meio) then
        return busca_binaria_recursiva(vetor, valor, indice_inicio, indice_meio - 1)
    else
        return busca_binaria_recursiva(vetor, valor, indice_meio + 1, indice_fim)
    end
end

function busca_binaria(vetor, valor)
    return busca_binaria_recursiva(vetor, valor, 1, #vetor)
end

local vetor = {7, 3, -3, -7, 9, 0}

-- Ordenação.
escreva_vetor(vetor) -- [7, 3, -3, -7, 9, 0]
table.sort(vetor) -- In-place
escreva_vetor(vetor) -- [-7, -3, 0, 3, 7, 9]

-- Busca binária.
print(busca_binaria(vetor, -3))
print(busca_binaria(vetor, 0))
print(busca_binaria(vetor, 9))
print(busca_binaria(vetor, -4))
print(busca_binaria(vetor, 77))

extends Node

func busca_binaria_recursiva(vetor, valor, indice_inicio, indice_fim):
    if (indice_inicio > indice_fim):
        return -1

    var indice_meio = (indice_inicio + indice_fim) / 2
    var valor_meio = vetor[indice_meio]
    if (valor == valor_meio):
        return indice_meio
    elif (valor < valor_meio):
        return busca_binaria_recursiva(vetor, valor, indice_inicio, indice_meio - 1)
    else:
        return busca_binaria_recursiva(vetor, valor, indice_meio + 1, indice_fim)

func busca_binaria(vetor, valor):
    return busca_binaria_recursiva(vetor, valor, 0, len(vetor) - 1)

func _ready():
    var vetor = [7, 3, -3, -7, 9, 0]

    # Ordenação.
    print(vetor) # [7, 3, -3, -7, 9, 0]
    vetor.sort() # In-place
    print(vetor) # [-7, -3, 0, 3, 7, 9]

    # Busca binária.
    print(busca_binaria(vetor, -3))
    print(busca_binaria(vetor, 0))
    print(busca_binaria(vetor, 9))
    print(busca_binaria(vetor, -4))
    print(busca_binaria(vetor, 77))

Antes de realizar a busca binária, deve-se ordenar o vetor (caso ele não esteja ordenado). Para entender melhor o algoritmo, pode ser interessante fazer uma execução manual com um teste de mesa.

A busca binária é eficiente porque ela efetivamente descarta a busca metade dos valores do vetor a cada chamada recursiva. Em outras palavras, divide-se o problema pela metade a cada recursão. Por isso a complexidade ser .

Novamente, ordenação e busca binária são recursos importantes para programação, pois elas permitem resolver problemas grandes de forma mais eficiente.

Cópia Rasa, Cópia Profunda e Memória Compartilhada

Cópias nem sempre são tão simples como se poderia pensar em linguagens de programação. Isso ocorre porque o operador de atribuição em algumas linguagens de programação não realiza cópias para tipos compostos de dados, diferentemente do que ocorre com tipos primitivos.

Uma cópia em programação pode ser uma cópia rasa (shallow copy), caso um ou mais valores compartilhem referências (endereço de memória), ou uma cópia profunda (deep copy), caso os valores sejam duplicados.

Uma cópia rasa normalmente duplica valores de tipos primitivos, mas compartilha valores de tipos compostos (como vetores ou registros). Assim, a alteração de um valor que seja de um tipo composto em uma cópia rasa afeta todas as cópias.

Uma cópia profunda efetivamente duplica todos os valores armazenados, independentemente do tipo. Ou seja, cada cópia profunda é única e independente das demais. Assim, a alteração de um valor em uma cópia profunda afeta apenas a cópia em que a operação foi realizada.

Existe ainda outra situação que requer atenção. Muitas linguagens de programação permitem compartilhar memória entre diversas variáveis quando se usa o operador de atribuição. Nesse caso, todas as variáveis são referências a um mesmo endereço de memória. Ou seja, a alteração de um valor em qualquer variável afeta todas as variáveis.

Em JavaScript, Python, Lua e GDScript, o operador de atribuição para vetores realiza compartilhamento de memória. Cópias rasas e cópias profundas requerem o uso de subrotinas especiais. Subrotinas para cópias rasas podem utilizar uma estrutura de repetição para copiar, índice a índice, todos os valores do vetor. Se um dos valores for de um tipo composto (por exemplo, um vetor de vetores), ele terá a memória compartilhada. Subrotinas para cópias profundas copiam recursivamente os valores. Em outras palavras, caso o valor armazenado em um índice seja de um tipo composto, a subrotina chama a própria subrotina para realizar uma nova cópia profunda do valor.

let vetor = [1, 2, 3, 4, 5]

console.log("Memória compartilhada")
let memoria_compartilhada = vetor
vetor[0] *= -10
memoria_compartilhada[1] *= -100
console.log("vetor", vetor)
console.log("memoria_comparilhada", memoria_compartilhada)

console.log("Cópia rasa")
let copia_rasa = Array.from(vetor)
// Alternativas:
// copia_rasa = [...vetor] // Operador spread.
// copia_rasa = vetor.slice()
copia_rasa[2] *= -1000
console.log("vetor", vetor)
console.log("memoria_comparilhada", memoria_compartilhada)
console.log("copia_rasa", copia_rasa)

console.log("Cópia profunda")
// ATENÇÃO: Possui limitações. Consultar notas.
let copia_profunda = JSON.parse(JSON.stringify(vetor))
copia_profunda[3] *= -10000
console.log("vetor", vetor)
console.log("memoria_comparilhada", memoria_compartilhada)
console.log("copia_rasa", copia_rasa)
console.log("copia_profunda", copia_profunda)

import copy # Para copy() e deepcopy().

vetor = [1, 2, 3, 4, 5]

print("Memória compartilhada")
memoria_compartilhada = vetor
vetor[0] *= -10
memoria_compartilhada[1] *= -100
print("vetor", vetor)
print("memoria_comparilhada", memoria_compartilhada)

print("Cópia rasa")
copia_rasa = copy.copy(vetor)
# Alternativas:
# copia_rasa = vetor.copy()
# copia_rasa = vetor[:]
copia_rasa[2] *= -1000
print("vetor", vetor)
print("memoria_comparilhada", memoria_compartilhada)
print("copia_rasa", copia_rasa)

print("Cópia profunda")
copia_profunda = copy.deepcopy(vetor)
copia_profunda[3] *= -10000
print("vetor", vetor)
print("memoria_comparilhada", memoria_compartilhada)
print("copia_rasa", copia_rasa)
print("copia_profunda", copia_profunda)

function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write(vetor[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

-- <http://lua-users.org/wiki/CopyTable>
function shallowcopy(orig)
    local orig_type = type(orig)
    local copy
    if orig_type == 'table' then
        copy = {}
        for orig_key, orig_value in pairs(orig) do
            copy[orig_key] = orig_value
        end
    else -- number, string, boolean, etc
        copy = orig
    end
    return copy
end

-- <http://lua-users.org/wiki/CopyTable>
-- Save copied tables in `copies`, indexed by original table.
function deepcopy(orig, copies)
    copies = copies or {}
    local orig_type = type(orig)
    local copy
    if orig_type == 'table' then
        if copies[orig] then
            copy = copies[orig]
        else
            copy = {}
            copies[orig] = copy
            for orig_key, orig_value in next, orig, nil do
                copy[deepcopy(orig_key, copies)] = deepcopy(orig_value, copies)
            end
            setmetatable(copy, deepcopy(getmetatable(orig), copies))
        end
    else -- number, string, boolean, etc
        copy = orig
    end
    return copy
end

local vetor = {1, 2, 3, 4, 5}

escreva_vetor("Memória compartilhada")
local memoria_compartilhada = vetor
vetor[1] = vetor[1] * -10
memoria_compartilhada[2] = memoria_compartilhada[2] * -100
escreva_vetor("vetor", vetor)
escreva_vetor("memoria_comparilhada", memoria_compartilhada)

escreva_vetor("Cópia rasa")
local copia_rasa = shallowcopy(vetor)
copia_rasa[3] = copia_rasa[3] * -1000
escreva_vetor("vetor", vetor)
escreva_vetor("memoria_comparilhada", memoria_compartilhada)
escreva_vetor("copia_rasa", copia_rasa)

escreva_vetor("Cópia profunda")
local copia_profunda = deepcopy(vetor)
copia_profunda[4] = copia_profunda[4] * -10000
escreva_vetor("vetor", vetor)
escreva_vetor("memoria_comparilhada", memoria_compartilhada)
escreva_vetor("copia_rasa", copia_rasa)
escreva_vetor("copia_profunda", copia_profunda)

extends Node

func _ready():
    var vetor = [1, 2, 3, 4, 5]

    print("Memória compartilhada")
    var memoria_compartilhada = vetor
    vetor[0] *= -10
    memoria_compartilhada[1] *= -100
    print("vetor", vetor)
    print("memoria_comparilhada", memoria_compartilhada)

    print("Cópia rasa")
    var copia_rasa = vetor.duplicate(false)
    copia_rasa[2] *= -1000
    print("vetor", vetor)
    print("memoria_comparilhada", memoria_compartilhada)
    print("copia_rasa", copia_rasa)

    print("Cópia profunda")
    var copia_profunda = vetor.duplicate(true)
    copia_profunda[3] *= -10000
    print("vetor", vetor)
    print("memoria_comparilhada", memoria_compartilhada)
    print("copia_rasa", copia_rasa)
    print("copia_profunda", copia_profunda)

Subrotinas:

JavaScript: Array.from() (documentação), slice() (documentação), operadores de espalhamento (spread; documentação), JSON.parse() (documentação) e JSON.stringify() (documentação);
Python: copy.copy() e copy.deepcopy() (documentação);
Lua: shallowcopy() e deepcopy (fonte e documentação);
GDScript: duplicate (documentação).

A versão para JavaScript possui limitações, caso o vetor armazene definições de funções ou o valor infinito em ponto flutuante. Para uma implementação mais robusta, pode-se usar, por exemplo, cloneDeep() da biblioteca Lodash.

As implementações de shallowcopy() e deepcopy() para Lua podem ser obtidas de lua-users.org, em Copy Table. A implementação de deepcopy() utiliza a abordagem recursiva previamente comentada. Como ela emprega recursos mais avançados (como metatable), ela não será discutida neste tópico.

No exemplo, como vetor é um vetor de números inteiros (ou seja, um vetor de um tipo primitivo), uma cópia rasa funciona tão bem quanto uma cópia profunda. Contudo, caso vetor armazenasse valores definidos por referência (por exemplo, uma matriz como [[1, 2, 3], [4, 5, 6], [7, 8, 9]]), apenas a cópia profunda permitiria alterações de valores nas listas internas sem afetar outras cópias. Um exemplo da diferença de cópias rasas e profundas para estruturas de dados contendo valores armazenados como referência será feito na seção de cópias e compartilhamento de dados em dicionários. Os princípios são os mesmos para vetores, dicionários e quaisquer outros dados cujas variáveis são armazenadas como referências.

Vetores Paralelos (ou Structure of Arrays)

Uma técnica usada em programação de alto desempenho chama-se vetores paralelos (parallel arrays), também conhecidos como structures of arrays (SoA). Vetores paralelos utilizam um mesmo índice para relacionar dados correlatos de uma mesma entidade. Simplificadamente, a técnica permite escrever sistemas de alto desempenho por permitir usar eficientemente a memória cache de processadores.

let nomes_poligonos = ["Triângulo", "Quadrado", "Retângulo", "Pentágono", "Hexágono"]
let lados_poligonos = [3, 4, 4, 5, 6]
for (let indice = 0; indice < nomes_poligonos.length; ++indice) {
    let nome = nomes_poligonos[indice]
    let lados = lados_poligonos[indice]
    console.log("Um ", nome, " tem ", lados, " lados.")
}

nomes_poligonos = ["Triângulo", "Quadrado", "Retângulo", "Pentágono", "Hexágono"]
lados_poligonos = [3, 4, 4, 5, 6]
for indice in range(len(nomes_poligonos)):
    nome = nomes_poligonos[indice]
    lados = lados_poligonos[indice]
    print("Um ", nome, " tem ", lados, " lados.")

# Forma alternativa.
for nome, lado in zip(nomes_poligonos, lados_poligonos):
    print("Um ", nome, " tem ", lados, " lados.")

local nomes_poligonos = {"Triângulo", "Quadrado", "Retângulo", "Pentágono", "Hexágono"}
local lados_poligonos = {3, 4, 4, 5, 6}
for indice = 1, #nomes_poligonos do
    local nome = nomes_poligonos[indice]
    local lados = lados_poligonos[indice]
    print("Um ", nome, " tem ", lados, " lados.")
end

extends Node

func _ready():
    var nomes_poligonos = ["Triângulo", "Quadrado", "Retângulo", "Pentágono", "Hexágono"]
    var lados_poligonos = [3, 4, 4, 5, 6]
    for indice in range(len(nomes_poligonos)):
        var nome = nomes_poligonos[indice]
        var lados = lados_poligonos[indice]
        print("Um ", nome, " tem ", lados, " lados.")

No exemplo anterior, nomes_poligonos e lados_poligonos utilizam o mesmo índice para se referir a um mesmo polígono. Por exemplo, o primeiro valor de cada vetor refere-se a um triângulo. Caso se tivesse mais dados, bastaria definir um novo vetor e usar o mesmo índice para cada polígono considerado. Por exemplo, soma_angulos_internos poderia armazenar a soma dos ângulos internos para cada polígono. O vetor ficaria algo como: [180.0, 360.0, 360.0, 540.0, 720.0].

Para facilitar a leitura, uma possibilidade seria alinhar os valores dos vetores. Por exemplo:

let nomes_poligonos       = ["Triângulo", "Quadrado", "Retângulo", "Pentágono", "Hexágono"]
let lados_poligonos       = [3,           4,          4,           5,           6]
let soma_angulos_internos = [180.0,       360.0,      360.0,       540.0,       720.0]

O exemplo também apresentou um iterador adicional para Python. Em Python, zip() (documentação) fornece uma forma prática de acessar os valores de cada vetor usando iteradores. O nome zip é empregado em programação funcional para iteração usando a técnica.

Matrizes (Matrices) e Vetores de Vetores

Em muitas linguagens de programação, vetores podem armazenar dados de quaisquer tipos -- sejam eles primitivos ou compostos. Em particular, vetores podem armazenar vetores. Quando isso ocorre, diz-se que o vetor é um vetor de vetores (ou lista de listas).

No caso especial em que cada índice possui um vetor, e este vetor no índice é um escalar (ou seja, não é um vetor), diz-se que o vetor de vetores é uma matriz. Em outras palavras, ele assemelha-se a uma tabela.

O conceito torna-se mais fácil com um exemplo. Assumindo-se indexação iniciada em zero, pode-se imaginar que um vetor v armazene:

Em v[0], o vetor [1, 2, 3];
Em v[1], o vetor [4, 5, 6];
Em v[2], o vetor [7, 8, 9].

O resultado é o seguinte vetor:

v = [
   [1, 2, 3],
   [4, 5, 6],
   [7, 8, 9]
]

Pode-se pensar em v como uma tabela.

Linha	Coluna 1	Coluna 2	Coluna 3
`v[0]`	1	2	3
`v[1]`	4	5	6
`v[2]`	7	8	9

Assim, por exemplo, v[0][0] == 1, v[1][0] == 4, v[2][2] == 9. Isso ocorre porque o valor acessado em v será um vetor. Em pseudocódigo, vetor_linha = v[indice]. Assim, vetor_linha[outro_indice] será um valor armazenado na linha do vetor. Da mesma forma, pode-se manipular vetor_linha como qualquer outro vetor.

Seguindo o mesmo raciocínio, pode-se criar vetores de vetores de vetores. Neste caso, cada linha do primeiro vetor seria uma matriz.

Pode-se declara um vetor de vetor em uma única linha (por exemplo, [[1, 2, 3], [4, 5, 6], [7, 8, 9]]). Em muitas linguagens de programação, é possível declará-lo em várias. A versão em múltiplas linhas é, potencialmente, mais fácil de ler.

let matriz = [
   [1, 2, 3],
   [4, 5, 6],
   [7, 8, 9]
]

for (let linha = 0; linha < 3; ++linha) {
    var texto_linha = ""
    for (let coluna = 0; coluna < 3; ++coluna) {
        texto_linha += matriz[linha][coluna] + " "
        // Caso você prefira, pode-se explicitar o uso de toString().
        // texto_linha += matriz[linha][coluna].toString() + " "
    }

    console.log(texto_linha)
}

matriz = [
   [1, 2, 3],
   [4, 5, 6],
   [7, 8, 9]
]

for linha in range(3):
    for coluna in range(3):
        print(matriz[linha][coluna], end=" ")

    print("")

local matriz = {
   {1, 2, 3},
   {4, 5, 6},
   {7, 8, 9}
}

for linha = 1, 3 do
    for coluna = 1, 3 do
        io.write(matriz[linha][coluna] .. " ")
    end

    print("")
end

extends Node

func _ready():
    var matriz = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]

    for linha in range(3):
        var texto_linha = ""
        for coluna in range(3):
            texto_linha += str(matriz[linha][coluna]) + " "

        print(texto_linha)

Matrizes são comuns em jogos digitais e computação gráfica. Por sinal, com o conhecimento adquirido até este momento, já é possível implementar diversos jogos simples com saída em terminal. Por exemplo, muitos jogos de cartas podem ser implementados com vetores, e vários jogos de tabuleiro podem ser implementados usando matrizes.

Ordem de Linhas e Ordem de Colunas

Algo a atentar ao usar vetores como matrizes é que existem duas formas de iterar sobre os elementos da matriz. Pode-se usar a ordem: para linha... para coluna ou a ordem para coluna... para linha. Embora o resultado seja o mesmo, o desempenho decorrente da ordem de uso pode variar significativamente. Nos casos de JavaScript, Python, Lua e GDScript, como matrizes são listas de listas, a escolha pode não fazer muita diferença. Contudo, em linguagens como C e C++, a diferença pode ser significativa. Isso ocorre devido à ordem na qual a linguagem de programação armazena valores na memória.

Linguagens de programação que armazenam linhas em seqüência (no exemplo, 1 2 3, depois 4 5 6, depois 7 8 9) são ditas com ordem de linhas (row-major order). Linguagens de programação que armazenam colunas em seqüencia (no exemplo, 1 4 7, depois 2 5 8, depois 3 6 9) são ditas com ordem de colunas (row-column order). Em ordem de linhas (caso de C e C++), é mais eficiente iterar primeiro em linhas (laço externo), depois em colunas (laço interno). Em ordem de colunas (caso de MATLAB, GNU Octave, R e Julia), é mais eficiente iterar primeiro com colunas, depois em linhas.

Matriz Como um Vetor

Com um pouco de criatividade, e conhecimento de programação e aritmética, é possível converter matrizes em um vetor linear.

Índice	0	1	2	3	4	5	6	7	8	9	10	11
Valor	1	2	3	4	5	6	7	8	9	10	11	12

O vetor anterior pode ser pensado como uma matriz, caso se escreva o índice em função de um valor assumido como o número de colunas. Por exemplo, caso se assuma 3 colunas, deve-se iniciar uma nova linha a cada 3 valores.

Coluna 1	Coluna 2	Coluna 3
1	2	3
4	5	6
7	8	9
10	11	12

Para manter o paralelo com o exemplo usando duas estruturas de repetição, pode-se definir a seguinte implementação para iterar sobre todos os elementos do vetor como se fosse uma matriz. Também é possível escrever uma variação usando-se resto de divisão inteira.

let matriz = [
   1, 2, 3,
   4, 5, 6,
   7, 8, 9,
   10, 11, 12
]

const LINHAS = 4
const COLUNAS = 3

for (let linha = 0; linha < LINHAS; ++linha) {
    var texto_linha = ""
    for (let coluna = 0; coluna < COLUNAS; ++coluna) {
        texto_linha += matriz[linha * COLUNAS + coluna] + " "
    }

    console.log(texto_linha)
}

console.log("Como um vetor")
var texto_matriz = ""
for (let indice = 0; indice < matriz.length; ++indice) {
    texto_matriz += matriz[indice] + " "

    if ((indice + 1) % COLUNAS == 0) {
        texto_matriz += "\n"
    }
}

console.log(texto_matriz)

from typing import Final

matriz = [
   1, 2, 3,
   4, 5, 6,
   7, 8, 9,
   10, 11, 12
]

LINHAS: Final = 4
COLUNAS: Final = 3

for linha in range(LINHAS):
    for coluna in range(COLUNAS):
        print(matriz[linha * COLUNAS + coluna], end=" ")

    print("")

print("Como um vetor")
for indice in range(len(matriz)):
    print(matriz[indice], end=" ")

    if ((indice + 1) % COLUNAS == 0):
        print("")

local matriz = {
   1, 2, 3,
   4, 5, 6,
   7, 8, 9,
   10, 11, 12
}

local LINHAS <const> = 4
local COLUNAS <const> = 3

for linha = 1, LINHAS do
    for coluna = 1, COLUNAS do
        io.write(matriz[(linha - 1) * COLUNAS + coluna] .. " ")
    end

    print("")
end

print("Como um vetor")
for indice = 1, #matriz do
    io.write(matriz[indice] .. " ")

    if (indice % COLUNAS == 0) then
        print()
    end
end

extends Node

const LINHAS = 4
const COLUNAS = 3

func _ready():
    var matriz = [
        1, 2, 3,
        4, 5, 6,
        7, 8, 9,
        10, 11, 12
    ]

    for linha in range(LINHAS):
        var texto_linha = ""
        for coluna in range(COLUNAS):
            texto_linha += str(matriz[linha * COLUNAS + coluna]) + " "

        print(texto_linha)

    print("Como um vetor")
    var texto_matriz = ""
    for indice in range(len(matriz)):
        texto_matriz += str(matriz[indice]) + " "

        if ((indice + 1) % COLUNAS == 0):
            texto_matriz += "\n"

    print(texto_matriz)

O exemplo mostra como é possível interpretar um mesmo conjunto de dados de forma diferente para modificar um significado para uma mesma representação. Faça um teste de mesa para entender a expressão para cálculo do índice. Também pode ser interessante declarar matriz em uma única linha para verificar que as quebras de linha não interferem na criação do vetor. Por exemplo, em JavaScript:

let matriz = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
const COLUNAS = 3
var texto_matriz = ""
for (let indice = 0; indice < matriz.length; ++indice) {
    texto_matriz += matriz[indice] + " "

    if ((indice + 1) % COLUNAS == 0) {
        texto_matriz += "\n"
    }
}

console.log(texto_matriz)

Não são as quebras de linha na declaração as responsáveis por transformar o vetor em uma matriz, mas a lógica de programação definida para manipular os valores nos índices. Em uma matriz em ordem de linhas, cada nova linha estará exatamente após cada número de valores definido para COLUNAS, pois a próxima linha começa ao final da última coluna da linha atual.

Cadeias de Caracteres (Strings)

Em linguagens de programação de alto nível que fornecem um tipo para cadeias de caracteres -- normalmente chamado de string --, realizar operações básica como atribuição e leitura de valores é mais simples que em linguagens de baixo nível. Agora que se conhece vetores, pode-se começar a trabalhar com cadeias de caracteres em nível mais baixo.

Considerando-se diferenças de codificação, cadeias de caracteres assemelham-se a vetores. Em algumas linguagens de programação, cadeias de caracteres são vetores de caracteres codificados. Em algumas outras, elas são vetores de bytes, que codificam caracteres.

Com estruturas de repetição e conhecimento de vetores, pode-se começar a manipular cadeias de caracteres caractere por caractere. Ao invés de pensar-se na cadeia como um único valor, pode-se pensá-la como ela realmente é: uma seqüência de caracteres que, potencialmente, podem ser manipulados individualmente.

Operações e Técnicas Usando Cadeias de Caracteres

Ao pensar cadeias de caracteres como vetores, pode-se usar todas as operações e técnicas de vetores com elas. Além disso, cadeias de caracteres possuem operações características próprias. Algumas delas já são familiares; outras serão novas.

Tamanho ou comprimento (size ou length): o número de caracteres presentes na cadeia de caracteres. O valor nem sempre será igual ao tamanho do vetor que armazena a cadeia de caracteres. Por exemplo, em linguagens de programação que tratam cadeias de caracteres como vetores de caracteres, os valores podem variar. A variável que armazena pode ter uma capacidade máxima, mas o conteúdo pode ocupar apenas parcialmente a memória disponível. Outra possibilidade que se deve atentar é a codificação. Em linguagens que tratam cadeias de caracteres como vetores de bytes, o tamanho real da cadeia de caracteres pode ser diferente (menor) que o informado por subrotinas que forneçam o comprimento (um único caractere pode ser composto por múltiplos bytes);
Concatenação (concatenation, concat): combinação de duas cadeias de caracteres, na qual a segunda é adicionada ao final da primeira. O resultado pode alterar o valor original (in-place) ou retornar como um resultado (out-of-place);
Conversão de tipos: conversão de tipos para cadeia de caracteres, transformando valores em texto (ou vice-versa);
Conversão de caixa (case conversion): conversão de caracteres para representações maiúsculas ou minúsculas;
Comparações (sensíveis ou não sensíveis à caixa): além de igualdade e diferença, é comum fornecer operadores ou subrotinas para verificação de ordem alfabética em cadeias de caracteres (algo útil para ordenação de vetores de cadeias de caracteres);
Verificação de valor: a cadeia de caracteres é:
- Um número ou composto apenas por dígitos?
- Composta apenas por letras minúsculas ou maiúsculas?
- Um espaço em branco?
Linguagens de programação e bibliotecas costumam fornecer subrotinas para identificar o que significa o valor armazenado em uma cadeia de caracteres;
Iteração em caracteres: para acesso e/ou manipulação de caracteres específicos em uma cadeia de caracteres. Por exemplo, a iteração permite acessar os caracteres F, r, a, n, c e o em Franco;
Busca por substring (find): busca por uma palavra ou expressão dentro de uma cadeia de caracteres. Em geral, o resultado retorna a posição da ocorrência (caso exista), ao invés de simplesmente Verdadeiro ou Falso. O termo substring refere-se a uma sub-cadeia de caracteres. Por exemplo, Franco é substring de Franco Garcia, assim como f e o G, mas Olá ou FrancoG não são. Em linguagens de programação sensíveis à caixa, franco também não é. Em linguagens de programação que não sejam sensíveis à caixa, franco seria;
Extração de substring (fatia ou slice): extração de parte dos dados armazenados em um cadeia de caracteres. Por exemplo, em Olá, meu nome é Franco!, pode-se extrair uma substring como Franco fornecendo-se os índices inicial e final adequados;
Busca e substituição (find ou search, e replace): assim como é possível buscar por um valor, é possível substituí-lo, ou seja, trocar uma substring por outra, alterando partes do conteúdo da cadeia de caracteres. Por exemplo, modificar a mensagem Olá, meu nome é Franco! por Tchau, Franco! substitui Olá, meu nome é por Tchau,, mantendo o restante da cadeia de caracteres;
Tokenização (tokenization) ou divisão/separação (split): extração de valores em um vetor. Por exemplo, Olá, meu nome é Franco! poderia ser dividida a cada espaço (delimitador), resultando em ["Olá,", "meu", "nome", "é", "Franco!"];
Identificação de padrões (pattern matching) e expressões regulares (regular expressionns ou regex): busca (com potencial substituição) por cadeias de caracteres usando padrões especificados pela programadora ou pelo programador.

Assim como era o caso com vetores, todas as operações anteriores podem ser definidas usando estruturas condicionais e estruturas de repetição. Por sinal, a implementação é um bom exercício para a prática de programação.

Antes de continuar, convém comentar que recursos disponíveis variam de linguagem para linguagem de programação. Isso é válido tanto para disponibilidade de recursos, quanto para a qualidade da implementação dos recursos disponíveis. Algumas linguagens de programação possuem boas bibliotecas para manipulação de cadeias de caracteres (inclusive na biblioteca padrão). Em outras, o ideal é usar uma biblioteca externa de qualidade para evitar problemas.

Concatenação e Conversão de Tipos

JavaScript, Python, Lua e GDScript fornecem operadores próprios para concatenação de cadeias de caracteres. Em JavaScript, Python e GDScript, o operador é o +. Em Lua, usa-se .. para concatenar dois valores.

let s = "Franco " + 1 + " " + (-1.23) + " " + true
console.log(s)

s = "Franco " + str(1) + " " + str(-1.23) + " " + str(True)
print(s)

local s = "Franco " .. 1 .. " " .. (-1.23) .. " " .. tostring(true)
print(s)

extends Node

func _ready():
    var s = "Franco " + str(1) + " " + str(-1.23) + " " + str(true)
    print(s)

As conversões de tipos primitivos para cadeias de caracteres foram apresentadas previamente em Tipos de Dados.

Em JavaScript, a conversão de tipos para cadeias de caracteres é implícita. Também é possível usar o método nome_variavel.toString().

Em Python e GDScript, a conversão de tipos deve ser feita explicitamente, usando str().

Em Lua, a conversão é implícita para todos os tipos menos boolean, que requer o uso de tostring(). Caso se queira usar tostring() sempre, também é possível.

Muitas linguagens de programação também permitem sobrecarregar operadores específicos para realizar conversão de valores de/para cadeias de caracteres. Convém procurar pela funcionalidade ao trabalhar com tipos compostos (especialmente com registros ou classes).

Tamanho e Iteração

Linguagens de programação costumam fornecer uma subrotina chamada length(), len() ou size() (ou algo similar) para obtenção de tamanho de cadeias de caracteres. Em algumas linguagens, como C, um caractere especial demarca o final da cadeia de caracteres (como o inteiro 0 ou o caractere \0), permitindo o cálculo do tamanho de uma string válida usando uma estrutura de repetição (contudo, caso a cadeia de caracteres não termine com o símbolo esperado, ocorrerá um erro grave chamado de buffer overread para leitura ou buffer overrun para escrita).

JavaScript, Python, Lua e GDScript são linguagens de alto nível com subrotinas para obtenção do comprimento.

let cadeia_caracteres = "Olá, meu nome é Franco!"
let tamanho = cadeia_caracteres.length
console.log(tamanho)

for (let indice_caractere = 0; indice_caractere < tamanho; ++indice_caractere) {
    console.log(cadeia_caracteres[indice_caractere])
}

console.log("\n-------\n")

for (const caractere of cadeia_caracteres) {
   console.log(caractere)
}

cadeia_caracteres = "Olá, meu nome é Franco!"
tamanho = len(cadeia_caracteres)
print(tamanho)

for indice_caractere in range(tamanho):
    print(cadeia_caracteres[indice_caractere])

print("\n-------\n")

for caractere in cadeia_caracteres:
   print(caractere)

local cadeia_caracteres = "Olá, meu nome é Franco!"
local tamanho = string.len(cadeia_caracteres)
                -- Para Lua 5.1 ou mais recente, também pode-se usar #cadeia_caracteres.
print(tamanho)

-- O que ocorre com os acentos?
for indice_caractere = 1, tamanho do
    print(string.sub(cadeia_caracteres, indice_caractere, indice_caractere))
    -- ou
    -- print(cadeia_caracteres:sub(indice_caractere, indice_caractere))
end

print("\n-------\n")

for caractere in string.gmatch(cadeia_caracteres, ".") do
                 -- ou cadeia_caracteres:gmatch(".")
   print(caractere)
end

extends Node

func _ready():
    var cadeia_caracteres = "Olá, meu nome é Franco!"
    var tamanho = len(cadeia_caracteres)
    print(tamanho)

    for indice_caractere in range(tamanho):
        print(cadeia_caracteres[indice_caractere])

    print("\n-------\n")

    for caractere in cadeia_caracteres:
       print(caractere)

Para Python e GDScript, len() é uma função conhecida. Para JavaScript, a propriedade length (documentação) fornece o tamanho. Para Lua, string.len() fornece o tamanho, string.sub() permite obter substrings e string.gmatch() permite fazer buscas (documentação). Tanto string.sub() quanto string.gmatch() serão tópico de estudo de próximas subseções.

A saída do programa em Lua será diferente da saída do programa nas demais linguagens. O tamanho de cadeia_caracteres em JavaScript, Python e GDScript será 23, mas, em Lua, será 25. Isso ocorre porque a linguagem está assumindo que cada caractere possui um único byte, algo que não ocorre para á e é, que possuem dois bytes cada um. De fato, ao tentar escrever o valor para cada posição, a saída será estranha, com um valor incorreto. Caracteres comuns à língua inglesa não terão o problema. A partir da versão 5.3 de Lua, a linguagem conta com suporte básico para Unicode Transformation Format 8-bit (UTF-8), permitindo a codificação de caracteres de outros idiomas usando UTF-8 ao invés de American Standard Code for Information Interchange (ASCII).

A partir da versão 5.3, o código a seguir em Lua apresenta o resultado correto.

local cadeia_caracteres = "Olá, meu nome é Franco!"
local tamanho = utf8.len(cadeia_caracteres)
print(tamanho)

for posicao_bytes, code_point in utf8.codes(cadeia_caracteres) do
   -- print(posicao_bytes, code_point, utf8.char(code_point))
   print(utf8.char(code_point))
end

A implementação usa utf8.len() para obter o tamanho, utf8.codes() para a iteração e utf8.char() para obter um caractere (documentação apenas em Inglês).

Com utf8.len(), o tamanho correto 23 será retornado. Para escrever apenas os caracteres, pode-se usar print(utf8.char(code_point)). A linha comentada escreve os outros valores retornados por utf8.codes(). Caso se remova o comentário da linha, é interessante notar que o contador posicao_bytes aumenta de duas unidades ao processar os caracteres acentuados á ou é, comprovando que cada um realmente é definido por dois bytes em UTF-8.

O exemplo em Lua demonstra que é preciso cuidado ao manipular índices diretamente em cadeias de caracteres. Não se pode assumir o resultado sem o conhecimento de como a linguagem armazena e codifica texto. Assim, caso a linguagem não forneça subrotinas na biblioteca padrão para processamento de textos em codificações diferentes de ASCII, é possível criar subrotinas próprias ou (preferencialmente) usar uma biblioteca externa de alta qualidade.

Conversão de Caixas

Em particular, conversões de caixa também são sensíveis à codificação. É comum que subrotinas para conversão de caracteres para minúsculas ou maiúsculas funcionem apenas com ASCII ou UTF-8.

console.log("0123 ABCDEF abcdef ÁÉÍÓÚ ÀÈÌÒÙ ÃÕ Ç áéíóú àèìòù ãõ ç".toLowerCase())
console.log("0123 ABCDEF abcdef ÁÉÍÓÚ ÀÈÌÒÙ ÃÕ Ç áéíóú àèìòù ãõ ç".toUpperCase())

print("0123 ABCDEF abcdef ÁÉÍÓÚ ÀÈÌÒÙ ÃÕ Ç áéíóú àèìòù ãõ ç".lower())
print("0123 ABCDEF abcdef ÁÉÍÓÚ ÀÈÌÒÙ ÃÕ Ç áéíóú àèìòù ãõ ç".upper())

os.setlocale("pt_BR.UTF-8")

print(string.lower("0123 ABCDEF abcdef ÁÉÍÓÚ ÀÈÌÒÙ ÃÕ Ç áéíóú àèìòù ãõ ç"))
print(string.upper("0123 ABCDEF abcdef ÁÉÍÓÚ ÀÈÌÒÙ ÃÕ Ç áéíóú àèìòù ãõ ç"))

local s = "0123 ABCDEF abcdef ÁÉÍÓÚ ÀÈÌÒÙ ÃÕ Ç áéíóú àèìòù ãõ ç"
print(s:lower())
print(s:upper())

extends Node

func _ready():
    print("0123 ABCDEF abcdef ÁÉÍÓÚ ÀÈÌÒÙ ÃÕ Ç áéíóú àèìòù ãõ ç".to_lower())
    print("0123 ABCDEF abcdef ÁÉÍÓÚ ÀÈÌÒÙ ÃÕ Ç áéíóú àèìòù ãõ ç".to_upper())

Das implementações acima, a versão em Lua provavelmente falhará para caracteres acentuados. Infelizmente, não há funções pré-definida para utf8.lower() ou utf8.upper(), embora o uso de os.setlocale() possa ser usado em algumas plataformas. Assim, deve-se procurar por uma biblioteca caso se tenha interesse em realizar conversões de caixa para idiomas diferentes de Inglês.

Comparações

Em Operações Relacionais e Comparações, comentou-se sobre comparações de cadeias de caracteres.

console.log("Franco" === "Franco")
console.log("Franco" !== "Franco")
console.log("Franco" === "franco")
console.log("FrAnCo" === "FrAnCo")
console.log("fRaNcO".toLowerCase() === "FrAnCo".toLowerCase())
console.log("fRaNcO".toUpperCase() === "FrAnCo".toUpperCase())

print("Franco" == "Franco")
print("Franco" != "Franco")
print("Franco" == "franco")
print("FrAnCo" == "FrAnCo")
print("fRaNcO".lower() == "FrAnCo".lower())
print("fRaNcO".upper() == "FrAnCo".upper())

print("Franco" == "Franco")
print("Franco" ~= "Franco")
print("Franco" == "franco")
print("FrAnCo" == "FrAnCo")
print(string.lower("fRaNcO") == string.lower("FrAnCo"))
print(string.upper("fRaNcO") == string.upper("FrAnCo"))

local x = "fRaNcO"
local y = "FrAnCo"
print(x:lower() == y:lower())
print(x:upper() == y:upper())

extends Node

func _ready():
    print("Franco" == "Franco")
    print("Franco" != "Franco")
    print("Franco" == "franco")
    print("FrAnCo" == "FrAnCo")
    print("fRaNcO".to_lower() == "FrAnCo".to_lower())
    print("fRaNcO".to_upper() == "FrAnCo".to_upper())

O exemplo anterior é uma adaptação do exemplo apresentado no tópico sobre operações relacionais. JavaScript, Python, Lua e GDScript são sensíveis à caixa; assim, o exemplo ilustra comparações usando apenas os operadores e usando conversões de caixa.

Em linguagens que não forneçam um operador para verificar igualdades de cadeias de caracteres, pode-se comparar valores posição a posição. Caso todos eles sejam idênticos (e as cadeias de caracteres tenham o mesmo comprimento), as cadeias de caracteres serão iguais.

Verificação de Valores

Algumas linguagens de programação possuem subrotinas para verificar se uma cadeia de caracteres contém apenas caracteres que satisfaçam a um critério. Isso pode ser feito com subrotinas pré-definidas para casos particular ou usando expressões regulares.

A existência e o número de subrotinas pré-definidas varia de linguagem para linguagem de programação. Os exemplos abaixo fornecem ilustram o uso de algumas delas, sendo potencialmente diferentes para cada linguagem. Caso a linguagem não forneça uma verificação necessária, pode-se implementá-los usando expressões regulares (que ainda serão comentadas neste tópico), ou estruturas de repetição e estruturas de condição. As implementações em Python e GDScript são as mais simples, pois usarem métodos pré-definidos.

JavaScript usa expressões regulares nos trechos usando /padrao/ (documentação), que ainda serão abordadas. O mesmo vale para Lua, com string.match() (documentação). Python possui vários métodos pré-definidos para verificação, como isalpha() e isdecimal() (documentação; eles começam com o prefixo is). GDScript possui alguns métodos para verificação de tipos e formatos, como para caminhos de arquivos e nomes de arquivos, números, cores em estilo HTML e endereços de Internet Protocol (IP) para comunicação via rede (documentação).

let valores = ["Franco", "123", "123.45", "Franco123", "franco", "FRANCO", " \n\t"]
for (const valor of valores) {
    console.log(valor)
    console.log("Letras", /^[A-Z]+$/i.test(valor))
    console.log("Alfanumérico", /^\w+$/i.test(valor)) // Inclui underscore (_).
    console.log("Dígitos", /^\d+$/i.test(valor))
    console.log("Letras minúsculas", /^[a-z]+$/.test(valor))
    console.log("Letras maiúsculas", /^[A-Z]+$/.test(valor))
    console.log("Espaços", /^\s+$/i.test(valor))

    console.log("-------\n")
}

valores = ["Franco", "123", "123.45", "Franco123", "franco", "FRANCO", " \n\t"]
for valor in valores:
    print(valor)
    print("isalpha", valor.isalpha())
    print("isascii", valor.isascii())
    print("isdigit ", valor.isdigit())
    print("isdecimal", valor.isdecimal())
    print("isnumeric", valor.isnumeric())
    print("islower", valor.islower())
    print("isupper", valor.isupper())
    print("isspace", valor.isspace())

    print("-------\n")

local valores = {"Franco", "123", "123.45", "Franco123", "franco", "FRANCO", " \n\t"}
for _, valor in ipairs(valores) do
    print(valor)
    print("Letras", string.match(valor, "[^%a]") == nil) -- ou valor:match("[^%a]")
    print("Alfanumérico", string.match(valor, "[^%w]") == nil)
    print("Dígitos", string.match(valor, "[^%d]") == nil)
    print("Letras minúsculas", string.match(valor, "[^%l]") == nil)
    print("Letras maiúsculas", string.match(valor, "[^%u]") == nil)
    print("Espaços", string.match(valor, "[^%s]") == nil)

    print("-------\n")
end

extends Node

func _ready():
    var valores = ["Franco", "123", "123.45", "Franco123", "franco", "FRANCO", " \n\t"]
    for valor in valores:
        print(valor)
        printt("is_valid_float", valor.is_valid_float())
        printt("is_valid_integer", valor.is_valid_integer())

        print("-------\n")

O último valor em valores corresponde a um espaço, uma quebra de linha e uma tabulação. Esses valores são tipicamente considerados como espaços em branco (white spaces) em linguagens de programação.

As versões usando padrões em JavaScript e Lua não reconhecem números reais (como 123.45), pois se verifica apenas por dígitos (mas o número contém pontos), nem números negativos (devido ao símbolo -). Além disso, elas são exemplos rápidos; elas requerem testes antes de uso em programas reais. Para conveniência, também seria interessante refatorá-las em funções.

Extração de Substring

Caso seja necessário obter parte dos dados de uma cadeia de caracteres, pode-se realizar a extração de substring. Para isso, basta fornecer-se o índice inicial e o índice final que devem ser usados para extração. Algumas linguagens de programação (como GDScript) utilizam um contador de caracteres ao invés da posição final.

let frase = "Olá, meu nome é Franco!"
console.log(frase.slice(16))
console.log(frase.slice(16, 22))

frase = "Olá, meu nome é Franco!"
print(frase[16:])
print(frase[16:22])
print(frase[16:22:3]) # Alterna de três em três caracteres.

local frase = "Olá, meu nome é Franco!"
print(string.sub(frase, 19)) -- ou frase:sub(19)
print(string.sub(frase, 19, 24)) -- ou frase:sub(19, 24)

extends Node

func _ready():
    var frase = "Olá, meu nome é Franco!"
    print(frase.substr(16))
    print(frase.substr(16, 6))

Subrotinas:

JavaScript: slice() (documentação);
Lua: string.sub() (documentação);
Python: operador : para slice (documentação);
GDScript: substr() (documentação).

A diferença de índices em Lua deve-se à contagem dos acentos como posições no vetor. Caso se considerasse apenas a indexação iniciada em 1, os índices deveriam ser 17 para o início e 23 para o fim.

A operação de extração também pode ser feita com vetores. No caso, obtém dados dos índices desejados, como um filtro por posições.

Busca por Substring

Uma operação comum em manipulação de cadeias de caracteres consiste em procurar pela ocorrência de uma cadeia (chamada de substring) em outra (a cadeia de caracteres considerada). Além de comum em programação, ela também é comum em sistemas que envolvam leitura ou manipulação de texto. Por exemplo, editores de texto, processadores de texto, leitores de documento e navegadores de Internet comumente fornecem uma funcionalidade para buscar por uma palavra-chave ou expressão (comumente disponível no atalho Ctrl f).

Buscas simples por uma substring determinada podem usar subrotinas como find() ou search(). Buscas complexas podem usar expressões regulares para procurar um padrão com alternativas.

Um caso especial de busca por substring é verificar se uma cadeia de caracteres começa ou termina com uma determinada substring (comumente chamadas como start_with() ou begin_with() para busca no início ou end_with() para busca no fim). A busca pelo início permite identificar prefixos (por exemplo, para verificar domínios em páginas de Internet ou caminhos para diretórios em sistemas de arquivos), enquanto a busca no fim permite a identificação de sufixos (por exemplo, para verificar extensões de arquivos).

let nome = "Franco"
console.log(nome.includes("ra"))
console.log(nome.indexOf("ra"))
console.log(nome.startsWith("Fr"))
console.log(nome.endsWith("co"))

nome = "Franco"
print(nome.find("ra"))
print(nome.startswith("Fr"))
print(nome.endswith("co"))

local nome = "Franco"
print(string.find(nome, "ra")) -- ou nome:find("ra")
local prefixo = "Fr"
print(string.find(nome, prefixo, 1, true) == 1) -- ou nome:find(prefixo, 1, true) == 1
local sufixo = "co"
local posicao_sufixo = #nome - #sufixo + 1
print(string.find(nome, sufixo, posicao_sufixo, true) == posicao_sufixo) -- ou nome:find(sufixo, posicao_sufixo, true) == posicao_sufixo
-- Alternativa:
print(string.sub(nome, -#sufixo) == sufixo)

extends Node

func _ready():
    var nome = "Franco"
    print(nome.find("ra"))
    print(nome.begins_with("Fr"))
    print(nome.ends_with("co"))

Subrotinas:

JavaScript: includes() (documentação), indexOf() (documentação), startsWith() (documentação), endsWith() (documentação);
Python: find() (documentação), startswith() (documentação), endswith() (documentação);
Lua: string.find() (documentação);
GDScript: find() (documentação), begins_with() (documentação), ends_with() (documentação).

Nos exemplos, Lua não possui subrotinas pré-definidas para busca por prefixo ou sufixo, mas elas podem usar string.find() com ajustes para as posições.

Além disso, JavaScript possui duas alternativas para find(): includes() retorna um valor lógico informando sobre a existência, enquanto indexOf() retorna o índice. Em todas as demais linguagens, a subrotina para busca retorna o índice da primeira posição encontrada. Em caso de erro, Lua retorna nil; Python, GDScript e JavaScript (indexOf()) retornam -1.

Algo a atentar é que uma cadeia de caracteres pode conter mais de uma ocorrência do termo procurado. No caso, o comportamento padrão de subrotinas costuma retornar o primeiro. Implementações costumam permitir fornecer uma posição inicial como parâmetro para a busca. Assim, caso se tenha interesse em localizar todas as ocorrências, pode-se usar uma estrutura de repetição para procurar iterativamente pela próxima (basta ajustar o próximo índice inicial a cada ocorrência do termo).

Busca e Substituição

Subrotinas como find() permitem localizar substrings. A operação complementar da busca é a substituição (replace).

let frase = "Olá, meu nome é Franco!"
frase = frase.replace("Franco", "FRANCO")
console.log(frase)

frase = "Olá, meu nome é Franco!"
frase = frase.replace("Franco", "FRANCO")
print(frase)

local frase = "Olá, meu nome é Franco!"
frase = string.gsub(frase, "Franco", "FRANCO", 1) -- ou frase:gsub("Franco", "FRANCO", 1)
print(frase)

extends Node

func _ready():
    var frase = "Olá, meu nome é Franco!"
    frase = frase.replace("Franco", "FRANCO")
    print(frase)

Subrotinas:

JavaScript: replace() (documentação);
Python: replace() (documentação);
Lua: string.gsub() (documentação);
GDScript: replace() (documentação).

Algumas implementações, como a de Lua, permitem alterar todas as ocorrências. O uso de 1 solicita a troca apenas da primeira.

Em linguagens de programação que troquem apenas a primeira ocorrência, pode-se usar uma estrutura de repetição para alterar as demais. Deve-se tomar cuidado porque, caso os tamanhos do termo procurado e do termo modificado sejam diferentes, deve-se ajustar os índices para busca de acordo. Em particular, caso o termo modificado contenha o termo original, deve-se tomar cuidado para não o substituir novamente por engano. Outra opção é usar uma expressão regular para trocar todas as ocorrências de uma vez.

Tokenização e Split

Assim como é possível converter um vetor em uma cadeia de caracteres usando um acumulador, é possível converter uma cadeia de caracteres em vetor usando operações de split ou tokenização (tokenization). O princípio é separar substrings da cadeia de caracteres original a cada identificação de um delimitador. O delimitador não é incluído nos resultados.

Delimitadores tradicionais incluem espaços, vírgulas, ponto e vírgulas, quebras de linhas e tabulações. Contudo, qualquer seqüência de caracteres pode ser adotada como um delimitador. O ideal é escolher uma que não comprometa a extração de dados válidos.

let frase = "Olá, meu nome é Franco!"
let delimitador = " "
let palavras = frase.split(delimitador)
console.log(palavras)

frase = "Olá, meu nome é Franco!"
delimitador = " "
palavras = frase.split(delimitador)
print(palavras)

-- Procedimento inclui aspas entre cada valor para facilitar a leitura de cada
-- cadeia de caracteres extraída.
function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write("\"" .. vetor[indice] .. "\"")
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

function split(cadeia_caracteres, delimitador)
    delimitador = delimitador or " "
    local resultado = {}
    local tamanho = #cadeia_caracteres
    local inicio = 1
    while (inicio <= tamanho) do
        local fim, proximo = string.find(cadeia_caracteres, delimitador, inicio, true)
        if (fim ~= nil) then
            table.insert(resultado, string.sub(cadeia_caracteres, inicio, fim - 1))
            inicio = proximo + 1
        else
            table.insert(resultado, string.sub(cadeia_caracteres, inicio))
            -- Qualquer valor maior que tamanho para terminar o laço.
            inicio = tamanho + 1
        end
    end

    -- Adiciona um valor vazio caso cadeia_caracteres termine com o delimitador.
    if (string.sub(cadeia_caracteres, -#delimitador) == delimitador) then
        table.insert(resultado, "")
    end

    return resultado
end

local frase = "Olá, meu nome é Franco!"
local delimitador = " "
local palavras = split(frase, delimitador)
escreva_vetor(palavras)

extends Node

func _ready():
    var frase = "Olá, meu nome é Franco!"
    var delimitador = " "
    var palavras = frase.split(delimitador)
    print(palavras)

Subrotinas:

JavaScript: split() (documentação);
Python: split() (documentação);
Lua: não fornece uma subrotina;
GDScript: split() (documentação).

Muitas implementações adotam um espaço ( ) como delimitador padrão, caso não se especifique um. Assim, convém consultar a documentação da subrotina escolhida.

Lua não fornece uma subrotina para split na biblioteca padrão. O exemplo fornece uma implementação usando apenas recursos apresentados até o momento (por exemplo, ele não utiliza expressões regulares). A implementação aceita valores vazios, caso cadeia_caracteres termine com um delimitador ou apresente dois delimitadores em seqüência. Isso é útil, por exemplo, ao trabalhar com valores separados por vírgulas (Comma Separated Values ou CSV) ou valores separados por tabulações (Tab Separated Values ou TSV). Por exemplo, a cadeia de caracteres a,,c,,e,, delimitada por uma vírgula resultaria em ["a", "", "c", "e", "", ""], enquanto ,, resultaria em ["", "", ""].

Expressões Regulares (Regex)

Expressões regulares são expressões que podem corresponder a valores que pertençam a uma linguagem regular. Linguagens regulares possuem diversas limitações; mesmo assim, expressões regulares podem ser úteis para buscas correspondendo a padrões simples. Em programação, expressões regulares são um recurso mais avançado para a busca (e, potencialmente substituição) de valores em cadeias de caracteres. Alguns exemplos anteriores utilizaram expressões regulares, embora sem explicação.

Uma introdução adequada a expressões regulares requer um tópico próprio. Assim, essa subseção serve apenas para fins ilustrativos, como indicação de que a funcionalidade existe. Ou seja, uma curiosidade que poderá ser útil no futuro.

Buscas por expressões regulares permitem identificar as posições de cada ocorrência. Cada ocorrência pode ser extraída ou substituída por outro valor.

Uma dificuldade para o uso de expressões regulares é o fato de existirem vários formatos para definição das expressões. Linguagens de programação (ou bibliotecas) podem definir o próprio ou usar alguns padrões famosos. Assim, a sintaxe tende a variar entre uma implementação e outra.

Alguns formatos populares incluem Perl Compatible Regular Expressions (PRCE), Basic Regular Expression (BRE) e Extended Regular Expression (ERE). Outras ferramentas definem os próprios formatos (por exemplo, o editor de texto Emacs possui um formato próprio). Várias implementações utilizam ou são compatíveis com PCRE.

Praticamente toda implementação possui os seguintes recursos:

Classes de caracteres: padrões especiais para representar conjuntos de caracteres pré-definidos. Por exemplo:
Valor Significado
b Espaço
s Qualquer tipo de espaço em branco
d Dígitos (0 até 9)
w Caracteres alfanuméricos (letras, dígitos e underscore)
. Qualquer caractere
$ Fim do texto
^ Início do texto
Os valores anteriores costumam ser prefixados por algum caractere, como contrabarra (\) ou cerquilha (#, também chamado de antífen, jogo da velha, ou, para a juventude, hashtag). Algumas implementações definem a letra maiúscula como o grupo contrário à letra minúscula.
Também existe uma forma de definir grupos usando colchetes. Por exemplo, [abc] significa qualquer caractere que seja a, b ou c, enquanto [A-Z] corresponde a qualquer letra maiúscula e [A-Za-z0-9] corresponde a qualquer caractere alfanumérico (incluindo underscore, também chamado sublinhado ou underline, que tem o símbolo _).
Novamente, a forma pode variar implementação para implementação; portanto, deve-se verificar a documentação;
Padrões: seqüências de caracteres ou de classes de caracteres com, possivelmente, especificadores para quantidades.
Símbolo Significado
* 0 ou mais ocorrências
+ 1 ou mais ocorrências (greed em algumas implementações)
- 1 ou mais ocorrências (não greed em algumas implementações)
? 0 ou 1 ocorrência
Por exemplo, escrever .* significa qualquer combinação de zero ou mais de qualquer caractere (pois é o significado de .). Por outro lado, (abc)+ corresponde a qualquer seqüência não vazia de abc (por exemplo, abc ou abcabcabc).
O termo greed significa algo como busca gulosa ou gananciosa, no sentido de que ela procura pela maior quantidade possível de caracteres que satisfaçam ao padrão definido. Em uma busca greed, o casamento da expressão continua até o último valor válido identificado. Em uma busca não greed, ele termina na primeira ocorrência;
Capturas: blocos que permitem obter valores que satisfaçam a um padrão identificado. A idéia da captura é prover uma forma de acessar o valor obtido da identificação de um padrão, qualquer que ele seja. Capturas podem ser nomeadas ou indexadas (na ordem em que foram definidas).
Algumas implementações usam parênteses para definir um grupo de captura.

Valor	Significado
`b`	Espaço
`s`	Qualquer tipo de espaço em branco
`d`	Dígitos (0 até 9)
`w`	Caracteres alfanuméricos (letras, dígitos e underscore)
`.`	Qualquer caractere
`$`	Fim do texto
`^`	Início do texto

Símbolo	Significado
`*`	0 ou mais ocorrências
`+`	1 ou mais ocorrências (greed em algumas implementações)
`-`	1 ou mais ocorrências (não greed em algumas implementações)
`?`	0 ou 1 ocorrência

Para demonstrar o potencial de expressões regulares, pode-se considerar um formato de diálogo como a seguir. Para evitar problemas, o texto omite acentos.

- Franco: Oi, tudo bem?
- Seu Nome: Oi!
- Seu Nome: Tudo em ordem.
- Franco: Que bom!

Qualquer valor que estiver entre o hífen e os dois pontos formam o nome da personagem. Qualquer valor após os dois pontos e antes de uma quebra de linha constituem a linha de diálogo (por exemplo, uma frase).

Pode-se supor que se deseje alterar o formato do diálogo para algo como [NOME] disse "[FRASE]".

Para escrever a expressão regular, deve-se montar uma expressão com os formatos esperados. No caso, o problema requer análise linha a linha. O formato será algo como - , seguido de qualquer texto, seguido de : , seguido de qualquer texto, seguido de \n. Qualquer texto pode ser escrito como qualquer combinação alfanumérica ou qualquer caractere escrito zero ou mais vezes.

Para ilustrar alguns usos, pode-se supor que o nome da personagem seja não vazio e composto por caracteres alfanuméricos, enquanto a frase possa ser qualquer texto válido exceto a quebra de linha. Assim, o reconhecimento de nome pode ser escrito como - ([\w ]+):, enquanto o reconhecimento do texto (que virá logo após) será escrito como : (.*)\n. Juntando ambas as expressões, o resultado é - ([\w ]+): (.*)\n (um dos dois pontos foi removido para evitar duplicação)

Antes de começar a implementação, convém salientar que costuma ser necessário adicionar caracteres de escape nas contrabarras (assim como em colchetes e parênteses que devam aparecer em texto). Em outras palavras, escrever \\ ao invés de \ ao usar uma contrabarra em uma cadeia de caracteres. Algumas linguagens de programação, como JavaScript e Python, fornecem recursos especiais para a escrita de expressões com maior facilidade. Por exemplo, prefixando uma cadeia de caracteres com r"" em Python, é possível usar uma contrabarra única. Da mesma forma, JavaScript possui uma sintaxe especial usando barras para a escrita de expressões regulares como literais ao invés de cadeias de caracteres.

Para a implementação, cada linguagem terá suas especificidades. Em Python, o trecho \w deverá ser escrito como \\w para incluir a contrabarra na cadeia de caracteres. Em Lua, a linguagem adotar %w ao invés de w para o grupo alfanumérico. Em Lua, o operador * também será substituído por -, para usara a versão não greed (caso contrário, a procura continuaria até a última quebra de linha identificada ao invés de parar após a primeira).

let roteiro = "- Franco: Oi, tudo bem?\n- Seu Nome: Oi!\n- Seu Nome: Tudo em ordem.\n- Franco: Que bom!\n"
let expressao_regular = /- ([\w ]+): (.*)\n/g
let resultado = expressao_regular.exec(roteiro)
while (resultado !== null) {
    // Para escrever o vetor obtido como resposta:
    // console.log(resultado)
    let nome = resultado[1]
    let frase = resultado[2]
    let novo_formato = nome + " disse \"" + frase + "\""
    console.log(novo_formato)
    resultado = expressao_regular.exec(roteiro)
}

import re

roteiro = "- Franco: Oi, tudo bem?\n- Seu Nome: Oi!\n- Seu Nome: Tudo em ordem.\n- Franco: Que bom!\n"
expressao_regular = re.compile(r"- ([\w ]+): (.*)\n")
resultado = expressao_regular.findall(roteiro)
for grupo in resultado:
    # Para escrever o vetor obtido como resposta:
    # print(grupo)
    nome = grupo[0]
    frase = grupo[1]
    novo_formato = nome + " disse \"" + frase + "\""
    print(novo_formato)

local roteiro = "- Franco: Oi, tudo bem?\n- Seu Nome: Oi!\n- Seu Nome: Tudo em ordem.\n- Franco: Que bom!\n"
local expressao_regular = "- ([%w ]+): (.-)\n"
for nome, frase in string.gmatch(roteiro, expressao_regular) do
    local novo_formato = nome .. " disse \"" .. frase .. "\""
    print(novo_formato)
end

extends Node

func _ready():
    var roteiro = "- Franco: Oi, tudo bem?\n- Seu Nome: Oi!\n- Seu Nome: Tudo em ordem.\n- Franco: Que bom!\n"
    var expressao_regular = RegEx.new()
    expressao_regular.compile("- ([\\w ]+): (.*)\n")
    var resultado = expressao_regular.search_all(roteiro)
    for grupo in resultado:
        # Para escrever o vetor obtido como resposta:
        # print(grupo)
        var nome = grupo.strings[1]
        var frase = grupo.strings[2]
        var novo_formato = nome + " disse \"" + frase + "\""
        print(novo_formato)

Padrões:
- JavaScript: documentação;
- Python: documentação;
- Lua: documentação;
- GDScript: documentação.
Busca:
- JavaScript: exec() (documentação);
- Python: re.compile() (documentação) e findall() (documentação);
- Lua: string.gmatch() (documentação);
- GDScript: RegEx.new() (documentação), compile() (documentação), search_all() (documentação).

O resultado de cada programa deverá ser:

Franco disse "Oi, tudo bem?"
Seu Nome disse "Oi!"
Seu Nome disse "Tudo em ordem."
Franco disse "Que bom!"

Caso se alterasse o roteiro, os novos resultados continuaram a ser processados corretamente, desde que se siga corretamente o formato para cada linha de diálogo. Além disso, seria possível tornar a implementação ainda mais concisa usando substituição ao invés de identificação.

let roteiro = "- Franco: Oi, tudo bem?\n- Seu Nome: Oi!\n- Seu Nome: Tudo em ordem.\n- Franco: Que bom!\n"
let expressao_regular = /- ([\w ]+): (.*)\n/g
let resultado = roteiro.replace(expressao_regular, "$1 disse \"$2\"\n",)
console.log(resultado)

import re

roteiro = "- Franco: Oi, tudo bem?\n- Seu Nome: Oi!\n- Seu Nome: Tudo em ordem.\n- Franco: Que bom!\n"
expressao_regular = re.compile(r"- ([\w ]+): (.*)\n")
resultado = expressao_regular.sub(r"""\1 disse "\2"\n""", roteiro)
print(resultado)

local roteiro = "- Franco: Oi, tudo bem?\n- Seu Nome: Oi!\n- Seu Nome: Tudo em ordem.\n- Franco: Que bom!\n"
local expressao_regular = "- ([%w ]+): (.-)\n"
local resultado = string.gsub(roteiro, expressao_regular, "%1 disse \"%2\"\n")
print(resultado)

extends Node

func _ready():
    var roteiro = "- Franco: Oi, tudo bem?\n- Seu Nome: Oi!\n- Seu Nome: Tudo em ordem.\n- Franco: Que bom!\n"
    var expressao_regular = RegEx.new()
    expressao_regular.compile("- ([\\w ]+): (.*)\n")
    var resultado = expressao_regular.sub(roteiro, "$1 disse \"$2\"\n", true)
    print(resultado)

Substituição:
- JavaScript: replace() (documentação);
- Python: sub() (documentação);
- Lua: string.gsub() (documentação);
- GDScript: sub() (documentação).

Usando-se a subrotina para substituição, pode-se eliminar o uso da estrutura de repetição para troca de ocorrências. Evidentemente, caso se deseje, é possível alterar a solução (com parâmetros adequados) para modificar apenas a primeira ocorrência ao invés de todas.

Expressões regulares não são muito legíveis sem experiência e prática. Na realidade, elas podem ser difíceis de ler mesmo com experiência e prática. Existem ferramentas que facilitam a criação e visualização de expressões regulares, como RegExr para JavaScript. Elas podem ser um bom recuso para aprendizado e para apoiar a criação, especialmente porque apresentam os resultados de modificações na expressão em tempo real.

No mais, pode-se evitar o uso de expressões regulares usando-se estruturas de repetição e condição para escrever um analisador sintático (também chamado de parser). Mesmo assim, é conveniente aprender a usar expressões regulares em algum momento da carreira de programação.

Dicionários (Dictionaries), Mapas (Maps) ou Tabelas (Tables)

Vetores (ou listas) estão disponíveis por padrão em praticamente linguagem de programação, mas não são a única forma de armazenar coleções de valores. Linguagens modernas também costumam fornecer uma implementação padrão para uma estrutura de dados associativa conhecida como dicionário, embora a implementação, em si, possa variar. Por exemplo, o dicionário pode ser implementado como uma tabelas hash (hash table ou hash map) ou como uma árvore (tree). A forma de operá-lo, contudo, é semelhante.

Vetores associam um valor a um índice. Dicionários associam um valor a uma chave (ou ID) escolhida pela programadora ou pelo programador. Em particular, implementações de dicionários costumam permitir a associação de um dado a uma chave de qualquer tipo de dado. Cadeias de caracteres representam um dos tipos de dados mais comuns para uso como chaves de dicionários. Por exemplo, uma associação com chave "nome" e valor "Franco" em um dicionário chamado dicionario permite usar o valor dicionario["nome"] para recuperar o valor armazenado "Franco". Assim, chave e valor definem um par que pode ser facilmente acessado usando a chave.

Uma vantagem do uso de dicionário é a facilidade para acessar um dado usando a chave, pois o dicionário abstrai a busca pela chave para acessar o valor. Por exemplo, imagine que se queira armazenar uma relação de IDEs recomendados neste material para pessoas iniciantes em programação por linguagem. Usando-se vetores, poder-se-ia armazenar o nome da linguagem de um vetor e o IDE em outro, usando a técnica de vetores paralelos para mapear o índice. Para buscar por um IDE, primeiro dever-se-ia conhecer o índice, para, depois, buscar o IDE.

let nomes_linguagens = ["Python", "Lua", "GDScript", "JavaScript"]
let ides_linguagens = ["Thonny", "ZeroBrane Studio", "Godot Engine", "Editor de texto e navegador de Internet"]

let linguagem_procurada = "GDScript"
let indice_linguagem_procurada = nomes_linguagens.indexOf(linguagem_procurada)
if (indice_linguagem_procurada !== -1) {
    let recomendacao = ides_linguagens[indice_linguagem_procurada]
    console.log(linguagem_procurada, ": ", recomendacao)
} else {
    console.log("Nenhuma recomendação para ", linguagem_procurada)
}

nomes_linguagens = ["Python", "Lua", "GDScript", "JavaScript"]
ides_linguagens = ["Thonny", "ZeroBrane Studio", "Godot Engine", "Editor de texto e navegador de Internet"]

linguagem_procurada = "GDScript"
indice_linguagem_procurada = nomes_linguagens.index(linguagem_procurada)
if (indice_linguagem_procurada != -1):
    recomendacao = ides_linguagens[indice_linguagem_procurada]
    print(linguagem_procurada, ": ", recomendacao)
else:
    print("Nenhuma recomendação para ", linguagem_procurada)

function busca_sequencial(vetor, valor)
    for indice, valor_atual in ipairs(vetor) do
        if (valor == valor_atual) then
            return indice
        end
    end

    return -1
end

local nomes_linguagens = {"Python", "Lua", "GDScript", "JavaScript"}
local ides_linguagens = {"Thonny", "ZeroBrane Studio", "Godot Engine", "Editor de texto e navegador de Internet"}

local linguagem_procurada = "GDScript"
local indice_linguagem_procurada = busca_sequencial(nomes_linguagens, linguagem_procurada)
if (indice_linguagem_procurada ~= -1) then
    local recomendacao = ides_linguagens[indice_linguagem_procurada]
    print(linguagem_procurada, ": ", recomendacao)
else
    print("Nenhuma recomendação para ", linguagem_procurada)
end

extends Node

func _ready():
    var nomes_linguagens = ["Python", "Lua", "GDScript", "JavaScript"]
    var ides_linguagens = ["Thonny", "ZeroBrane Studio", "Godot Engine", "Editor de texto e navegador de Internet"]

    var linguagem_procurada = "GDScript"
    var indice_linguagem_procurada = nomes_linguagens.find(linguagem_procurada)
    if (indice_linguagem_procurada != -1):
        var recomendacao = ides_linguagens[indice_linguagem_procurada]
        print(linguagem_procurada, ": ", recomendacao)
    else:
        print("Nenhuma recomendação para ", linguagem_procurada)

A desvantagem da abordagem é a primeira busca pelo nome da linguagem. Ela poderia ser melhorada mantendo-se os vetores ordenados por nome de linguagem.

Outra opção seria convencionar um índice específico para cada linguagem. Por exemplo, o primeiro índice (0 ou 1, dependendo da linguagem usada na implementação) poderia corresponder sempre a Python. Cada índice poderia ser armazenado em uma constante para facilitar o acesso. A desvantagem da abordagem seria requer alterações no código-fonte a cada inclusão de uma nova linguagem de programação.

Em ambas as abordagens, a situação indesejada é a necessidade de conhecer o índice que armazena o valor (seja via busca, seja via convenção). Usando um dicionário, é possível associar diretamente um valor a uma chave. Conhecendo-se a chave, pode-se obter o valor.

// Com JavaScript Object:
let ides_linguagens = {
    "Python": "Thonny",
    "Lua": "ZeroBrane Studio",
    "GDScript": "Godot Engine",
    "JavaScript": "Editor de texto e navegador de Internet"
}
// Também é possível escrever:
// let ides_linguagens = {
//    Python: "Thonny",
//    Lua: "ZeroBrane Studio",
//    GDScript: "Godot Engine",
//    JavaScript: "Editor de texto e navegador de Internet"
//}

let linguagem_procurada = "GDScript"
let recomendacao = ides_linguagens[linguagem_procurada]
if (recomendacao !== undefined) {
    console.log(linguagem_procurada, ": ", recomendacao)
} else {
    console.log("Nenhuma recomendação para ", linguagem_procurada)
}

// Com Map:
ides_linguagens = new Map()
ides_linguagens.set("Python", "Thonny")
ides_linguagens.set("Lua", "ZeroBrane Studio")
ides_linguagens.set("GDScript", "Godot Engine")
ides_linguagens.set("JavaScript", "Editor de texto e navegador de Internet")

linguagem_procurada = "GDScript"
if (ides_linguagens.has(linguagem_procurada)) {
    let recomendacao = ides_linguagens.get(linguagem_procurada)
    console.log(linguagem_procurada, ": ", recomendacao)
} else {
    console.log("Nenhuma recomendação para ", linguagem_procurada)
}

ides_linguagens = {
    "Python": "Thonny",
    "Lua": "ZeroBrane Studio",
    "GDScript": "Godot Engine",
    "JavaScript": "Editor de texto e navegador de Internet"
}

linguagem_procurada = "GDScript"
if (linguagem_procurada in ides_linguagens):
    recomendacao = ides_linguagens[linguagem_procurada]
    print(linguagem_procurada, ": ", recomendacao)
else:
    print("Nenhuma recomendação para ", linguagem_procurada)

local ides_linguagens = {
    Python = "Thonny",
    Lua = "ZeroBrane Studio",
    GDScript = "Godot Engine",
    JavaScript = "Editor de texto e navegador de Internet"
}

local linguagem_procurada = "GDScript"
local recomendacao = ides_linguagens[linguagem_procurada]
if (linguagem_procurada ~= nil) then
    print(linguagem_procurada, ": ", recomendacao)
else
    print("Nenhuma recomendação para ", linguagem_procurada)
end

extends Node

func _ready():
    var ides_linguagens = {
        "Python": "Thonny",
        "Lua": "ZeroBrane Studio",
        "GDScript": "Godot Engine",
        "JavaScript": "Editor de texto e navegador de Internet"
    }

    var linguagem_procurada = "GDScript"
    if (linguagem_procurada in ides_linguagens):
        var recomendacao = ides_linguagens[linguagem_procurada]
        print(linguagem_procurada, ": ", recomendacao)
    else:
        print("Nenhuma recomendação para ", linguagem_procurada)

JavaScript, Python, Lua e GDScript permitem declarar um dicionário com chaves (em Lua, vetores e dicionários são implementados como uma estrutura chamada table; por isso, ambos são declarados usando chaves). A inserção e o acesso a valores usam o operador colchetes, que recebe o valor da chave como parâmetro. Em Python e GDScript, pode-se verificar se uma chave existe usando a palavra chave in. Em JavaScript (com JavaScript Object) e Lua, tenta-se acessar o valor e verifica-se se ele não é nulo.

No caso de JavaScript, o uso de chaves, na realidade, cria um JavaScript Object ao invés de um dicionário. Para criar um dicionário propriamente dito, pode-se fazer new Map() (documentação), usando os métodos set() (documentação) para inserir ou alterar um valor, get() (documentação) para acessar um valor existente, e has() (documentação) para verificar se uma chave existe. Os três métodos permitem escrever código equivalente ao exemplo inicial. Em muitos casos, pode-se usar JavaScript Object como um dicionário; contudo, como será apresentado em algumas subseções, apenas Map possui alguns métodos úteis para manipulação de dicionários.

Vetores, listas e dicionários são estruturas de dados (embora possa se discutir que um array possa estar em um nível mais baixo, como um tipo composto). Todos eles permitem armazenar e gerenciar coleções de dados. A escolha da estrutura de dados mais adequada dependerá do problema (especialmente porque, muitas vezes, é possível escolher mais de uma para resolver um problema).

Dicionários são estruturas de dados práticas para programar, sobretudo para prototipação. A escolha entre usar um vetor ou um dicionário depende das características do problema a ser resolvido. Em geral, o acesso a um elemento de um vetor é uma operação mais rápida que a de um elemento em um dicionário. Contudo, isso assume que o índice para acesso seja conhecido. Caso se precise usar uma busca seqüencial para encontrar o índice de acesso, o uso de um dicionário tende a ser mais rápido.

Além disso, vetores costumam ser escolhas melhores para se preservar e definir ordem, definido aos índices. Exceto caso a implementação afirme o contrário, não se pode assumir ordem para iteração em dicionários.

Quando desempenho é prioridade, a escolha da estrutura de dados torna-se importante. No caso, é necessário analisar o problema quanto à forma de uso de uma coleção. O número (ou proporção) de inserções, remoções, buscas e acessos a valores poderá indicar a escolha mais recomendada. Cada uma das operações possui complexidade entre a dependendo da implementação da estrutura de dados e da operação a ser feita.

Entretanto, quando se está aprendendo a programar, desempenho não deve ser prioridade (exceto caso o problema exija que seja). Assim, neste momento, você pode escolher a estrutura de dados que facilitar a solução para seu problema. Essa recomendação, inclusive, pode ser útil mesmo para a prática profissional. Muitas vezes, é conveniente criar um primeiro protótipo com uma solução simples, para, em seguida, medir o desempenho do programa usando um profiler para identificar gargalos (bottlenecks) de desempenho. Assim, pode-se priorizar partes da soluções que realmente requeiram otimizações ao invés de tentar adivinhá-las com suposições.

Operações e Técnicas Usando Dicionários

As operações e técnicas para manipulação de dicionários são praticamente as mesmas para vetores.

Acesso a valores e iteração;
Obtenção do tamanho (size ou length);
Verificação de dicionário vazio (empty);
Inicialização;
Escrita ou impressão (write, print ou dump);
Acumulação de valores (reduce);
Seleção ou filtro de valores (filter);
Busca (find ou search);
Cópia (duplicação ou clone): geração de um novo vetor idêntico ao original;
Inserir (add, insert, set), remover (remove, delete) e limpar (empty, clear).

Uma diferença é a ausência de busca seqüêncial, ordenação e busca binária, que são detalhes da implementação. Implementações de dicionários podem ter as chaves ordenadas (por exemplo, usando árvores) ou desordenadas (por exemplo, usando tabelas hash).

Qualquer que seja a implementação, a programador ou o programador que usar o dicionário pronto não precisa se preocupar com a ela. Ao invés de ordenação é busca, deve-se a verificar se a chave existe no dicionário. Dependendo da implementação, a tentativa de acesso a um valor usando uma chave inexistente podem resultar em erro ou exceção (travando o programa), ou o retorno de um valor considerado como nulo. Em implementações cujo acesso resulte em erro, o ideal é verificar se a chave realmente existente antes de tentar acessar o valor (ou assegurar-se que, de fato, ela existe).

Declaração e Inicialização

Assim com vetores, pode-se inicializar os valores de um dicionária na declaração ou realizando inserções após a declaração. Linguagens de programação costumam oferecer duas formas para acessar um valor em um dicionário:

Uma subrotina para obter o valor (normalmente chamada get ou read). Por exemplo, meu_dicionario.get(chave);
Um operador para acesso ao valor (normalmente colchetes, da mesma forma que um vetor). Por exemplo, meu_dicionario[key].

Algumas linguagens oferecem uma das alternativas, outras oferecem ambas. Algumas linguagens ainda permitem usar uma terceira forma, quando a chave é uma cadeia de caracteres: meu_dicionario.key, que é equivalente à segunda forma e assemelha-se ao uso de variáveis (atributos ou campos) de registos (que serão o próximo tópico de estudo).

A declaração também costumam permitir duas variações:

A declaração usando nome da estrutura de dados (map, dictionary, dict, table...);
Um símbolo especial (comumente um par de chaves).

// JavaScript object (pode ser usado como dicionário com os devidos cuidados).
let meu_dicionario = {
    "um": 1,
    "dois": 2,
    "três": 3
}
// A rigor, a melhor forma de criação é
// let meu_dicionario = Object.create(null)
// ao invés de {}, para evitar a criação de propriedades pré-definidas.

meu_dicionario["quatro"] = 4
meu_dicionario.cinco = 5
meu_dicionario["seis"] = 6

console.log(meu_dicionario["um"])
console.log(meu_dicionario["dois"])
console.log(meu_dicionario.três) // JavaScript permite o uso mesmo que a chave
                                 // tenha caracteres especiais
console.log(meu_dicionario.quatro)
console.log(meu_dicionario["cinco"])
console.log(meu_dicionario["seis"])

// Dicionário propriamente dito.
meu_dicionario = new Map()
meu_dicionario.set("um", 1)
meu_dicionario.set("dois", 2)
meu_dicionario.set("três", 3)
meu_dicionario.set("quatro", 4)
meu_dicionario.set("cinco", 5)
meu_dicionario.set("seis", 6)

console.log(meu_dicionario.get("um"))
console.log(meu_dicionario.get("dois"))
console.log(meu_dicionario.get("três"))
console.log(meu_dicionario.get("quatro"))
console.log(meu_dicionario.get("cinco"))
console.log(meu_dicionario.get("seis"))

meu_dicionario = {
    "um": 1,
    "dois": 2,
    "três": 3
}

meu_dicionario["quatro"] = 4
meu_dicionario["cinco"] = 5
meu_dicionario["seis"] = 6

print(meu_dicionario["um"])
print(meu_dicionario["dois"])
print(meu_dicionario["três"])
print(meu_dicionario["quatro"])
print(meu_dicionario["cinco"])
print(meu_dicionario["seis"])

local meu_dicionario = {
    um = 1,
    dois = 2,
    ["três"] = 3 -- Chaves de tipos numéricos ou com caracteres com acentos,
                 -- espaços ou outros símbolos especiais devem estar entre
                 -- colchetes. No caso, ["três"] é a cadeia de caracteres
                 -- "três", não um vetor (vetores em Lua tem sintaxe {},
                 -- pois também são tabelas).
}

meu_dicionario["quatro"] = 4
meu_dicionario.cinco = 5
meu_dicionario["seis"] = 6

print(meu_dicionario["um"])
print(meu_dicionario["dois"])
print(meu_dicionario["três"]) -- O uso de acentos requer impede o acesso
                              -- usando .três. Neste caso, deve-se usar
                              -- colchetes.
print(meu_dicionario.quatro)
print(meu_dicionario["cinco"])
print(meu_dicionario.seis)

extends Node

func _ready():
    var meu_dicionario = {
        "um": 1,
        dois = 2,
        "três": 3
    }

    meu_dicionario["quatro"] = 4
    meu_dicionario.cinco = 5
    meu_dicionario["seis"] = 6

    print(meu_dicionario["um"])
    print(meu_dicionario["dois"])
    print(meu_dicionario["três"]) # O uso de acentos requer impede o acesso
                                  # usando .três. Neste caso, deve-se usar
                                  # colchetes.
    print(meu_dicionario.quatro)
    print(meu_dicionario["cinco"])
    print(meu_dicionario.get("seis"))
    # get() permite retornar um valor personalizado de erro caso o
    # valor não exista.
    # print(meu_dicionario.get("sete", "Erro: valor não encontrado"))

Em JavaScript, o uso de chaves cria um JavaScript Object ao invés de um dicionário propriamente dito. Embora ele possa ser usado como dicionário com os devidos cuidados, pode-se usar um dicionário real por meio da declaração new Map(). O dicionário criado com Map é mais moderno e com mais recursos, embora não permita o uso com colchetes para acesso a valores.

JavaScript, Lua e GDScript fornecem algumas alternativas para inicialização e acesso a valores em dicionários. Python define uma única forma para cada um.

Assim como é o caso com vetores, algumas linguagens de programação permitem declarar separar a última entrada com vírgula, algo que pode ser útil quando usada em conjunto com sistemas para controle de versões, como git.

Por exemplo:

let meu_dicionario = {
    "um" : 1,
    "dois": 2,
    "três": 3,
}

Os benefícios são os mesmos descritos para vetores. A escolha de estilo é de sua preferência.

No mais, GDScript também fornece um método get() (documentação) para acessar valores em um dicionário. O método permite passar um segundo parâmetro como valor para se retornar caso a chave fornecida não exista no dicionário.

Diferentes Tipos para Chaves e Valores

Algumas implementações permitem misturar tipos de dados para chaves e também para valores em dicionários. Em geral, pessoalmente eu normalmente recomendaria o uso de um mesmo tipo para chave e um mesmo tipo para os valores. O tipo da chave e do valor podem ser diferentes (por exemplo, a chave ser um número inteiro e o valor ser uma cadeia de caracteres), mas misturar chaves de diferentes tipos ou valores de diferentes tipos torna o uso da estrutura mais complexa (por exemplo, a chave ser um número inteiro, um número real ou uma cadeia de caracteres).

Contudo, existem duas aplicações interessantes para a mistura de valores. A primeira é usar um dicionário como uma enumeração, em que pares de chave e valor estejam mapeados um para o outro. Desde que os valores armazenados não mudem (ou tomando-se os devidos cuidados para atualizar os pares), pode-se criar um dicionário que seja, ao mesmo tempo, seu dicionário reverso.

let meu_dicionario = new Map()
meu_dicionario.set("um", 1)
meu_dicionario.set(1, "um")
meu_dicionario.set("dois", 2)
meu_dicionario.set(2, "dois")
meu_dicionario.set("três", 3)
meu_dicionario.set(3, "três")

console.log(meu_dicionario.get("um"))
console.log(meu_dicionario.get(1))

meu_dicionario = {
    "um": 1,
    1: "um",
    "dois": 2,
    2: "dois",
    "três": 3,
    3: "três"
}

print(meu_dicionario["um"])
print(meu_dicionario[1])

local meu_dicionario = {
    um = 1,
    [1] = "um",
    dois = 2,
    [2] = "dois",
    ["três"] = 3,
    [3] = "três"
}

print(meu_dicionario["um"])
print(meu_dicionario[1])

extends Node

func _ready():
    var meu_dicionario = {
        "um": 1,
        1: "um",
        "dois": 2,
        2: "dois",
        "três": 3,
        3: "três"
    }

    print(meu_dicionario["um"])
    print(meu_dicionario[1])

No exemplo, meu_dicionario mapeia o nome de um número (chave) com seu valor (valor), e o valor de um número (chave) com seu nome (valor). Assim, ao invés de criar dois dicionários para pares de valores e chaves, pode-se definir apenas um (como se fosse um dicionário duplo).

Uma forma mais simples de criar o dicionário reverso consiste no uso de estruturas de repetição, usando iterações. Após inserir um dos conjuntos de valores, pode-se iterar por todos os pares chave e valor fazendo meu_dicionario[valor] = chave. A atribuição inserirá a combinação inversa no dicionário.

A segunda aplicação interessante é modelar registros usando dicionários, algo que possa ser útil caso a linguagem de programação não forneça funcionalidades para a criação de registros ou classes. Por exemplo, pode-se convencionar um dicionário que armazene os campos nome (cadeia de caracteres), ano (número inteiro) e nota (número real) para mapear avaliações para livros, músicas ou filmes. A abordagem será apresentada em um exercício.

Inserções, Remoções, Limpeza e Tamanho

Ao contrário de vetores, que podem ser de tamanho fixo, dicionários normalmente permitem redimensionamento. Assim, operações de inserção e remoção de dados tentem a ser comuns. De fato, ao invés de inicializar valores nulos (ou zeros) em chaves como placeholders (um valor considerado nulo ou neutro com propósito de marcar espaço ou "guardar lugar"), costuma ser preferível adicionar um valor em um dicionário apenas quando a chave efetivamente armazene um valor. Em outras palavras, dicionários costumam ser esparsos.

A seção sobre inicialização forneceu exemplos para inserção de dados. Um adendo importante é que a inserção de valor para uma chave que já exista substitui o valor antigo. Dicionários normalmente não permitem a inserção de chaves duplicadas. Caso se precise duplicar chaves com valores potenciais diferentes, pode-se usar uma estrutura de dados diferente chamada de multimap. Outra opção é usar árvores que permitem chaves duplicadas (por exemplo, uma árvore-B ou B-tree, comumente usada em bancos de dados).

A remoção pode variar de acordo com a implementação e/ou linguagem de programação. Algumas implementações definem uma subrotina ou um comando para a remoção; outras convencionam que a atribuição de um valor nulo para uma chave funciona como remoção do valor.

let meu_dicionario = {}

meu_dicionario["a"] = 1.0
meu_dicionario["b"] = 2.0
meu_dicionario["c"] = 3.0
meu_dicionario["d"] = 4.0
// JavaScript Object não permite obter tamanho.

console.log(meu_dicionario["a"])
meu_dicionario["a"] = -1.0
console.log(meu_dicionario["a"])

delete meu_dicionario["a"]

// JavaScript Object não possui subrotina para limpeza do dicionário.

// Usando Map.

meu_dicionario = new Map()

meu_dicionario.set("a", 1.0)
meu_dicionario.set("b", 2.0)
meu_dicionario.set("c", 3.0)
meu_dicionario.set("d", 4.0)
console.log(meu_dicionario.size)

console.log(meu_dicionario.get("a"))
meu_dicionario.set("a", -1.0)
console.log(meu_dicionario.get("a"))

meu_dicionario.delete("a")
console.log(meu_dicionario.size)

meu_dicionario.clear()
console.log(meu_dicionario.size)

meu_dicionario = {}

meu_dicionario["a"] = 1.0
meu_dicionario["b"] = 2.0
meu_dicionario["c"] = 3.0
meu_dicionario["d"] = 4.0
print(len(meu_dicionario))

print(meu_dicionario["a"])
meu_dicionario["a"] = -1.0
print(meu_dicionario["a"])

del meu_dicionario["a"]
print(len(meu_dicionario))

meu_dicionario.clear()
print(len(meu_dicionario))

function tamanho_tabela(tabela)
    local tamanho = 0
    for _ in pairs(tabela) do
        tamanho = tamanho + 1
    end

    return tamanho
end

function limpe_tabela(tabela)
    for chave, _ in pairs(tabela) do
        tabela[chave] = nil
    end
end

local meu_dicionario = {}

meu_dicionario["a"] = 1.0
meu_dicionario["b"] = 2.0
meu_dicionario["c"] = 3.0
meu_dicionario["d"] = 4.0
print(tamanho_tabela(meu_dicionario))

print(meu_dicionario["a"])
meu_dicionario["a"] = -1.0
print(meu_dicionario["a"])

meu_dicionario["a"] = nil
print(tamanho_tabela(meu_dicionario))

limpe_tabela(meu_dicionario)
print(tamanho_tabela(meu_dicionario))

extends Node

func _ready():
    var meu_dicionario = {}

    meu_dicionario["a"] = 1.0
    meu_dicionario["b"] = 2.0
    meu_dicionario["c"] = 3.0
    meu_dicionario["d"] = 4.0
    print(len(meu_dicionario))

    print(meu_dicionario["a"])
    meu_dicionario["a"] = -1.0
    print(meu_dicionario["a"])

    meu_dicionario.erase("a")
    print(len(meu_dicionario))

    meu_dicionario.clear()
    print(len(meu_dicionario))

Python e GDScript utilizam len() para obtenção tamanho, como também ocorreu para cadeias de caracteres e vetores.

Em JavaScript, apenas Map possui uma propriedade (size; documentação) para verificar o tamanho do dicionário e um método para limpeza (clear(); documentação). Os demais métodos já foram citados na introdução sobre dicionários.

Assim, o exemplo em JavaScript ilustra algumas limitações do uso de um JavaScript Object como um dicionário: não é possível obter o tamanho, nem limpar o dicionário com uma única chamada. Embora seja possível obter o tamanho usando algumas alternativas, é mais apropriado usar Map em cenários mais complexos que exijam uma solução mais robusta.

let meu_dicionario = {"a": 1, "b": 2, "c": 3}
console.log(Object.keys(meu_dicionario).length)

Em Lua, não há uma subrotina pré-definida para obter o tamanho de uma tabela. Pode-se definir uma função para isso, mas é importante atentar que ela precisa percorrer toda a tabela para calcular o tamanho. Assim, pode ser preferível armazenar o tamanho em uma variável separada e implementar subrotinas para adicionar e remover valores, ajustando a variável com o tamanho de acordo.

function adicione_a_tabela(tabela, chave, valor, tamanho_atual)
    local tamanho = tamanho_atual
    if (tabela[chave] == nil) then
        tamanho = tamanho + 1
    end

    tabela[chave] = valor

    return tamanho
end

function remova_da_tabela(tabela, chave, tamanho_atual)
    if (tabela[chave] ~= nil) then
        tabela[chave] = nil
        return (tamanho_atual - 1)
    else
        return tamanho_atual
    end
end

function tamanho_tabela(tabela)
    local tamanho = 0
    for _ in pairs(tabela) do
        tamanho = tamanho + 1
    end

    return tamanho
end

local meu_dicionario = {}
local tamanho_meu_dicionario = 0

tamanho_meu_dicionario = adicione_a_tabela(meu_dicionario, "a", 1, tamanho_meu_dicionario)
print(tamanho_meu_dicionario, tamanho_tabela(meu_dicionario))

tamanho_meu_dicionario = adicione_a_tabela(meu_dicionario, "b", 2, tamanho_meu_dicionario)
print(tamanho_meu_dicionario, tamanho_tabela(meu_dicionario))

tamanho_meu_dicionario = adicione_a_tabela(meu_dicionario, "b", 3, tamanho_meu_dicionario)
print(tamanho_meu_dicionario, tamanho_tabela(meu_dicionario))

tamanho_meu_dicionario = remova_da_tabela(meu_dicionario, "a", tamanho_meu_dicionario)
print(tamanho_meu_dicionario, tamanho_tabela(meu_dicionario))

tamanho_meu_dicionario = remova_da_tabela(meu_dicionario, "a", tamanho_meu_dicionario)
print(tamanho_meu_dicionario, tamanho_tabela(meu_dicionario))

No exemplo, a função tamanho_tabela() é chamada para comparar os resultados para demonstrar que estão corretos. Em particular, o tamanho não pode ser incrementado em uma inserção na qual a chave já exista, ou decrementado em uma remoção na qual a chave não exista. As operações podem ser implementadas de forma com registros. Também é possível melhorar o processo usando uma metatable (embora isso exija a versão 5.2 ou superior de Lua; documentação). Para isso, pode-se usar a função setmetatable() (documentação). Por exemplo:

function tamanho_tabela(tabela)
    local tamanho = 0
    for _ in pairs(tabela) do
        tamanho = tamanho + 1
    end

    return tamanho
end

-- Requer Lua 5.2 ou mais recente.
function crie_tabela()
    local tabela = {}
    -- __len é uma função a ser chamada quando do uso do operador #.
    setmetatable(tabela, {__len = tamanho_tabela})

    return tabela
end

local meu_dicionario = crie_tabela()
meu_dicionario["a"] = 1.0
meu_dicionario["b"] = 2.0
print(#meu_dicionario)

meu_dicionario["a"] = nil
print(#meu_dicionario)

Metatables são um recurso mais avançado de Lua; assim, o bloco de código anterior tem fins ilustrativos. Deve-se notar que o cálculo do tamanho usando a função tamanho_tabela tem complexidade , não sendo, portanto, ideal. Armazenar o valor em uma variável com tamanho pode ser uma solução melhor caso se precise do valor do tamanho com freqüência.

Acesso a Valores e Iteração

Exemplos anteriores mostraram como acessar um valor quando se conhece a chave usada no dicionário. Quando não se conhece a chave, pode-se iterar por todos as entradas armazenadas no dicionário usando iteradores.

let meu_dicionario = {
    "um": 1,
    "dois": 2,
    "três": 3
}

for (let chave in meu_dicionario) {
    let valor = meu_dicionario[chave]
    console.log(chave, valor)
}

for (let chave of Object.keys(meu_dicionario)) {
    console.log(chave)
}

for (let valor of Object.values(meu_dicionario)) {
    console.log(valor)
}

// Dicionário propriamente dito.
meu_dicionario = new Map()
meu_dicionario.set("um", 1)
meu_dicionario.set("dois", 2)
meu_dicionario.set("três", 3)

for (let [chave, valor] of meu_dicionario) {
    console.log(chave, valor)
}

for (let [chave, valor] of meu_dicionario.entries()) {
    console.log(chave, valor)
}

for (let chave of meu_dicionario.keys()) {
    console.log(chave)
}

for (let valor of meu_dicionario.values()) {
    console.log(valor)
}

meu_dicionario = {
    "um": 1,
    "dois": 2,
    "três": 3
}

for chave in meu_dicionario:
    valor = meu_dicionario[chave]
    print(chave, valor)

for chave, valor in meu_dicionario.items():
    print(chave, valor)

for chave in meu_dicionario.keys():
    print(chave)

for valor in meu_dicionario.values():
    print(valor)

local meu_dicionario = {
    um = 1,
    dois = 2,
    ["três"] = 3
}

for chave, valor in pairs(meu_dicionario) do
    print(chave, valor)
end

for chave in pairs(meu_dicionario) do
    print(chave)
end

for _, valor in pairs(meu_dicionario) do
    print(valor)
end

extends Node

func _ready():
    var meu_dicionario = {
        "um": 1,
        "dois": 2,
        "três": 3
    }

    for chave in meu_dicionario:
        var valor = meu_dicionario[chave]
        print(chave, valor)

    for chave in meu_dicionario.keys():
        print(chave)

    for valor in meu_dicionario.values():
        print(valor)

Subrotinas:

JavaScript: Object.keys() (documentação), Object.values() (documentação), entries() (documentação), keys() (documentação), values() (documentação);
Python: items() (documentação), keys() (documentação), values() (documentação);
Lua: pairs() (documentação). A diferença entre ipairs() e pairs() é que ipairs() itera apenas em índices numéricos (o i pode ser interpretado como índice ou inteiro), enquanto pairs() itera sobre chaves de qualquer tipo. Como vetores em Lua são tabelas otimizadas para índices numéricos, a diferença é o tipo do índice.
GDScript: keys() (documentação), values() (documentação);

Os exemplos mostram que é possível iterar sobre combinações de chaves e valores, apenas chaves, e apenas valores. Algo que se pode notar em algumas execuções é que nem sempre as chaves terão uma ordem definida.

Algumas implementações podem ordenar valores de chaves, outras podem seguir a ordem de inserção, outras podem usar outros critérios ou ordem aleatória. Caso se precise de algum critério para acessar as chaves, pode-se obter um vetor com elas, ordená-lo conforme a necessidade e usar o vetor para obter os valores na ordem desejada.

Assim, exceto caso a documentação da implementação de dicionário escolhida afirme o contrário, não se deve assumir uma ordem para as chaves durante a iteração. Para se definir ordem, vetores e listas podem ser opções melhores.

Busca

Buscas em dicionários podem ocorrer de duas formas:

Busca por um valor armazenado em alguma chave;
Busca por uma chave. Alternativamente, a busca por uma chave pode ter o objetivo de verificar se ela existe ou não. Algumas implementações de dicionários não permitem acessar o valor de uma chave inexistente, o que pode gerar uma exceção ou fazer com que o programa trave.

Como o segundo caso já foi exemplificado, convém começar por ele.

Busca por Uma Chave e Verificação de Existência de Chave

Em algumas implementações de dicionários, deve-se assegurar que uma chave exista no dicionário antes de tentar acessar valor armazenado. Para isso, pode-se usar subrotinas como has() ou hasKey(). Caso a linguagem não forneça uma subrotina assim, uma alternativa é obter todas as chaves como um vetor e realizar a busca no vetor. Outra alternativa é iterar sobre o dicionário e procurar pela chave a cada repetição.

O exemplo introdutório fazia a verificação antes de tentar acessar a chave. Ele é reproduzido, novamente, aqui. Para ilustrar outra abordagem com JavaScript Objects, a comparação com undefined foi trocada pela chamada de hasOwnProperty() na versão em JavaScript. As outras versões continuam iguais.

// Com JavaScript Object:
let ides_linguagens = {
    "Python": "Thonny",
    "Lua": "ZeroBrane Studio",
    "GDScript": "Godot Engine",
    "JavaScript": "Editor de texto e navegador de Internet"
}

let linguagem_procurada = "GDScript"
if (ides_linguagens.hasOwnProperty(linguagem_procurada)) {
    let recomendacao = ides_linguagens[linguagem_procurada]
    console.log(linguagem_procurada, ": ", recomendacao)
} else {
    console.log("Nenhuma recomendação para ", linguagem_procurada)
}

// Com Map:
ides_linguagens = new Map()
ides_linguagens.set("Python", "Thonny")
ides_linguagens.set("Lua", "ZeroBrane Studio")
ides_linguagens.set("GDScript", "Godot Engine")
ides_linguagens.set("JavaScript", "Editor de texto e navegador de Internet")

linguagem_procurada = "GDScript"
if (ides_linguagens.has(linguagem_procurada)) {
    let recomendacao = ides_linguagens.get(linguagem_procurada)
    console.log(linguagem_procurada, ": ", recomendacao)
} else {
    console.log("Nenhuma recomendação para ", linguagem_procurada)
}

ides_linguagens = {
    "Python": "Thonny",
    "Lua": "ZeroBrane Studio",
    "GDScript": "Godot Engine",
    "JavaScript": "Editor de texto e navegador de Internet"
}

linguagem_procurada = "GDScript"
if (linguagem_procurada in ides_linguagens):
    recomendacao = ides_linguagens[linguagem_procurada]
    print(linguagem_procurada, ": ", recomendacao)
else:
    print("Nenhuma recomendação para ", linguagem_procurada)

local ides_linguagens = {
    Python = "Thonny",
    Lua = "ZeroBrane Studio",
    GDScript = "Godot Engine",
    JavaScript = "Editor de texto e navegador de Internet"
}

local linguagem_procurada = "GDScript"
local recomendacao = ides_linguagens[linguagem_procurada]
if (linguagem_procurada ~= nil) then
    print(linguagem_procurada, ": ", recomendacao)
else
    print("Nenhuma recomendação para ", linguagem_procurada)
end

extends Node

func _ready():
    var ides_linguagens = {
        "Python": "Thonny",
        "Lua": "ZeroBrane Studio",
        "GDScript": "Godot Engine",
        "JavaScript": "Editor de texto e navegador de Internet"
    }

    var linguagem_procurada = "GDScript"
    if (linguagem_procurada in ides_linguagens):
        var recomendacao = ides_linguagens[linguagem_procurada]
        print(linguagem_procurada, ": ", recomendacao)
    else:
        print("Nenhuma recomendação para ", linguagem_procurada)

Subrotinas para JavaScript: hasOwnProperty() (documentação), has() (documentação).

Linguagens de programação que retornam um valor nulo no caso de chave inexistente, como Lua, permitem tentar acessar o valor para verificar se a chave existe. Uma contrapartida é que, nesses casos, não é possível saber se existe uma chave que armazene o valor nulo ou se a chave não exista no dicionário. Embora isso possa parecer um pouco redundante, a diferença pode ser significativa para a modelagem de alguns problemas.

Busca por um Valor Armazenado em Alguma Chave

No caso da busca de um valor armazenado em alguma chave, normalmente deseja-se saber se o valor existe no dicionário e, caso exista, qual a chave para acessá-lo.

function javascript_object_busque_por_valor(dicionario, valor_desejado) {
    for (let chave in dicionario) {
        let valor = dicionario[chave]
        if (valor === valor_desejado) {
            return chave
        }
    }

    return undefined
}

let meu_dicionario = {
    "um": 1,
    "dois": 2,
    "três": 3
}

console.log(javascript_object_busque_por_valor(meu_dicionario, 2))
console.log(javascript_object_busque_por_valor(meu_dicionario, -2))

// Dicionário propriamente dito.
function map_busque_por_valor(dicionario, valor_desejado) {
    for (let [chave, valor] of dicionario) {
        if (valor === valor_desejado) {
            return chave
        }
    }

    return undefined
}

meu_dicionario = new Map()
meu_dicionario.set("um", 1)
meu_dicionario.set("dois", 2)
meu_dicionario.set("três", 3)

console.log(map_busque_por_valor(meu_dicionario, 2))
console.log(map_busque_por_valor(meu_dicionario, -2))

def busque_por_valor(dicionario, valor_desejado):
    for chave in dicionario:
        valor = dicionario[chave]
        if (valor == valor_desejado):
            return chave

    return None

meu_dicionario = {
    "um": 1,
    "dois": 2,
    "três": 3
}

print(busque_por_valor(meu_dicionario, 2))
print(busque_por_valor(meu_dicionario, -2))

function busque_por_valor(dicionario, valor_desejado)
    for chave, valor in pairs(dicionario) do
        if (valor == valor_desejado) then
            return chave
        end
    end

    return nil
end

local meu_dicionario = {
    um = 1,
    dois = 2,
    ["três"] = 3
}

print(busque_por_valor(meu_dicionario, 2))
print(busque_por_valor(meu_dicionario, -2))

extends Node

func busque_por_valor(dicionario, valor_desejado):
    for chave in dicionario:
        var valor = dicionario[chave]
        if (valor == valor_desejado):
            return chave

    return null

func _ready():
    var meu_dicionario = {
        "um": 1,
        "dois": 2,
        "três": 3
    }

    print(busque_por_valor(meu_dicionario, 2))
    print(busque_por_valor(meu_dicionario, -2))

A solução apresentada retorna a primeira chave identificada com o valor. Em outras palavras, caso o valor existisse em diversas chaves, apenas a primeira seria retornada. Uma segunda limitação é que o valor nulo usado para retorno não pode ser usado como chave em um dicionário (o que nem sempre é um problema; muitas implementações não permitem o valor nulo como chave).

Para eliminar as limitações, poder-se-ia retornar um vetor de chaves identificas. Um vetor vazio significaria que nenhuma ocorrência foi identificada.

Além disso, deve-se observar que a busca por um valor é uma operação lenta (ela é uma busca seqüencial, com complexidade ; em potencial, a complexidade para acesso ao valor pode torná-la ainda mais complexa), pois é o inverso da definição de um dicionário. Caso se faça verificações de valor com freqüência, pode ser conveniente definir um segundo dicionário no qual as chaves do primeiro sejam os valores do segundo e vice-versa. Alternativamente, em linguagens que permitem misturar tipos de chaves e valores, poder-se-ia usar um único dicionário como um dicionário duplo.

Acumuladores

Acumuladores em dicionários funcionam da mesma forma que em vetores. A diferença é que se pode acumulador valores e/ou chaves, dependendo do problema considerado.

let meu_dicionario = {
    "um": 1,
    "dois": 2,
    "três": 3
}

let texto = "{\n"
for (let chave in meu_dicionario) {
    let valor = meu_dicionario[chave]
    texto += "  " + chave + ": " + valor + ",\n"
}
texto += "}"

console.log(texto)

// Dicionário propriamente dito.
meu_dicionario = new Map()
meu_dicionario.set("um", 1)
meu_dicionario.set("dois", 2)
meu_dicionario.set("três", 3)

texto = "{\n"
for (let [chave, valor] of meu_dicionario) {
    texto += "  " + chave + ": " + valor + ",\n"
}
texto += "}"

console.log(texto)

meu_dicionario = {
    "um": 1,
    "dois": 2,
    "três": 3
}

texto = "{\n"
for chave in meu_dicionario:
    valor = meu_dicionario[chave]
    texto += "  " + chave + ": " + str(valor) + ",\n"

texto += "}"

print(texto)

local meu_dicionario = {
    um = 1,
    dois = 2,
    ["três"] = 3
}

local texto = "{\n"
for chave, valor in pairs(meu_dicionario) do
    texto = texto .. "  " .. chave .. ": " .. valor .. ",\n"
end
texto = texto .. "}"

print(texto)

extends Node

func _ready():
    var meu_dicionario = {
        "um": 1,
        "dois": 2,
        "três": 3
    }

    var texto = "{\n"
    for chave in meu_dicionario:
        var valor = meu_dicionario[chave]
        texto += "  " + chave + ": " + str(valor) + ",\n"

    texto += "}"

    print(texto)

O exemplo anterior mostra como escrever todos os valores de um dicionário em linguagens como Lua, cuja subrotina para escrita não apresenta todo o conteúdo de um dicionário. Uma versão mais sofisticada poderia ser uma função recursiva que também escrevesse vetores e/ou dicionários armazenados como chaves e/ou valores no dicionário. Um exemplo será fornecido na seção sobre cópias de dicionários.

Seleção ou Filtro de Valores

A seleção ou filtro de valores também é similar a operação correspondente em vetores.

let meu_dicionario = {
    "um": 1,
    "dois": 2,
    "três": 3
}

let chaves_impares = []
for (let chave in meu_dicionario) {
    let valor = meu_dicionario[chave]
    if (valor % 2 === 1) {
        chaves_impares.push(chave)
    }
}

console.log(chaves_impares)

// Dicionário propriamente dito.
meu_dicionario = new Map()
meu_dicionario.set("um", 1)
meu_dicionario.set("dois", 2)
meu_dicionario.set("três", 3)

chaves_impares = []
for (let [chave, valor] of meu_dicionario) {
    if (valor % 2 === 1) {
        chaves_impares.push(chave)
    }
}

console.log(chaves_impares)

meu_dicionario = {
    "um": 1,
    "dois": 2,
    "três": 3
}

chaves_impares = []
for chave in meu_dicionario:
    valor = meu_dicionario[chave]
    if (valor % 2 == 1):
        chaves_impares.append(chave)

print(chaves_impares)

local meu_dicionario = {
    um = 1,
    dois = 2,
    ["três"] = 3
}

local chaves_impares = {}
for chave, valor in pairs(meu_dicionario) do
    if (valor % 2 == 1) then
        table.insert(chaves_impares, chave)
    end
end

io.write("[ ")
for indice, valor in ipairs(chaves_impares) do
    io.write(valor .. ", ")
end
print("]")

extends Node

func _ready():
    var meu_dicionario = {
        "um": 1,
        "dois": 2,
        "três": 3
    }

    var chaves_impares = []
    for chave in meu_dicionario:
        var valor = meu_dicionario[chave]
        if (valor % 2 == 1):
            chaves_impares.append(chave)

    print(chaves_impares)

O exemplo anterior seleciona chaves baseadas no valor (seleção caso número ímpar). Uma vantagem de armazenar a chave seria a facilidade para acesso ao valor. Por exemplo, poder-se-ia fazer algo como meu_dicionario[chaves_impares[0]] para acessar o valor do primeiro resultado obtido, caso o índice 0 seja válido para chaves_impares.

Cópia Rasa, Cópia Profunda e Memória Compartilhada

Operações de cópia e compartilhamento de memória em dicionários costuma ocorrer como para vetores. As regras costumam ser as mesmas: a passagem de dicionários como parâmetros para subrotinas é feita referência. Além disso, atribuições compartilham memória ao invés de criar cópias.

Caso se queira cópias independentes, deve-se, pois, usar (ou definir) uma subrotina que faça cópia profunda. Cópias de valores resultarão em cópias rasas, algo que não costuma ser de interesse (pois dados como vetores e outros dicionários armazenados internamente serão compartilhados).

No exemplo a seguir, o dicionário original possui os seguintes tipos para cada chave:

inteiro: um número inteiro, ou seja, um valor de tipo primitivo. Uma cópia rasa ou profunda pode duplicá-lo;
real: um número real, ou seja, um valor de tipo primitivo. Uma cópia rasa ou profunda pode duplicá-lo;
vetor: um vetor ou uma lista, ou seja, um tipo composto armazenado como referência. Apenas uma cópia profunda pode duplicá-lo (e ela deve ser recursiva);
dicionario: um dicionário ou uma tabela, ou seja, um tipo composto armazenado como referência. Apenas uma cópia profunda pode duplicá-lo (e ela deve ser recursiva).

A cada mudança de valor, convém analisar cada uma das variáveis armazenados para verificar mudanças no valor de original, memoria_compartilhada, copia_rasa e copia_profunda. Cada uma das variáveis será declarada após ilustrar-se as alterações nas anteriores.

let original = {
    "inteiro": 1,
    "real": 1.1,
    "vetor": [1, 2, 3],
    "dicionario": {
        "olá": "Olá, meu nome é Franco!"
    }
}
console.log("Original: ", original)

console.log("\nMemória compartilhada")
let memoria_compartilhada = original
original["inteiro"] = 2
memoria_compartilhada["real"] = 2.2
console.log("Original: ", original)
console.log("Memória Compartilhada: ", memoria_compartilhada)

console.log("\nCópia Rasa")
let copia_rasa = {...original}
memoria_compartilhada["inteiro"] = 3
original["inteiro"] = 3
memoria_compartilhada["real"] = 3.3
copia_rasa["inteiro"] = -33
copia_rasa["real"] = -33.3
copia_rasa["vetor"][0] = 111
copia_rasa["dicionario"]["olá"] = "Oi, meu nome é Franco!"
original["vetor"][1] = 222
console.log("Original: ", original)
console.log("Memória Compartilhada: ", memoria_compartilhada)
console.log("Cópia rasa: ", copia_rasa)

console.log("\nCópia Profunda")
// ATENÇÃO: Possui limitações, como apresentado para vetores.
let copia_profunda = JSON.parse(JSON.stringify(original))
memoria_compartilhada["inteiro"] = 4
original["inteiro"] = 4
memoria_compartilhada["real"] = 4.4
copia_rasa["inteiro"] = -44
copia_rasa["real"] = -44.4
copia_rasa["vetor"][0] = 1234
copia_rasa["dicionario"]["olá"] = "Oi, meu nome é Franco!!!"
original["vetor"][1] = 1234
copia_profunda["inteiro"] = 999
copia_profunda["real"] = 999.99
copia_profunda["vetor"][0] = 999
copia_profunda["dicionario"]["olá"] = "Olá, Franco!"
console.log("Original: ", original)
console.log("Memória Compartilhada: ", memoria_compartilhada)
console.log("Cópia rasa: ", copia_rasa)
console.log("Cópia profunda: ", copia_profunda)

// Versão com Map.
original = new Map()
original.set("inteiro", 1)
original.set("real", 1.1)
original.set("vetor", [1, 2, 3])
original.set("dicionario", new Map().set("olá", "Olá, meu nome é Franco!"))
console.log("Original: ", original)

console.log("\nMemória compartilhada")
memoria_compartilhada = original
original.set("inteiro", 2)
memoria_compartilhada.set("real", 2.2)
console.log("Original: ", original)
console.log("Memória Compartilhada: ", memoria_compartilhada)

console.log("\nCópia Rasa")
copia_rasa = new Map(original)
memoria_compartilhada.set("inteiro", 3)
original.set("inteiro", 3)
memoria_compartilhada.set("real", 3.3)
copia_rasa.set("inteiro", -33)
copia_rasa.set("real", -33.3)
copia_rasa.get("vetor")[0] = 111
copia_rasa.get("dicionario").set("olá", "Oi, meu nome é Franco!")
original.get("vetor")[1] = 222
console.log("Original: ", original)
console.log("Memória Compartilhada: ", memoria_compartilhada)
console.log("Cópia rasa: ", copia_rasa)

console.log("\nCópia Profunda")
// ATENÇÃO: A cópia profunda será imperfeita.
// Além das limitações anteriores, uma limitação adicional é que a cópia profunda
// não será recursiva.
// O ideal é usar algo como cloneDeep() da biblioteca Lodash para fazer uma
// cópia profunda melhor.
copia_profunda = new Map(JSON.parse(JSON.stringify(Array.from(original))))
memoria_compartilhada.set("inteiro", 4)
original.set("inteiro", 4)
memoria_compartilhada.set("real", 4.4)
copia_rasa.set("inteiro", -44)
copia_rasa.set("real", -44.4)
copia_rasa.get("vetor")[0] = 1234
copia_rasa.get("dicionario").set("olá", "Oi, meu nome é Franco!!!")
original.get("vetor")[1] = 1234
copia_profunda.set("inteiro", 999)
copia_profunda.set("real", 999.99)
copia_profunda.get("vetor")[0] = 999
// Eis o problema: cópia profunda não é recursiva.
// O valor armazenado em "dicionario" será um JavaScript Object ao invés de um Map.
// copia_profunda.get("dicionario").set("olá", "Olá, Franco!") // Esperado: Map.
copia_profunda.get("dicionario")["olá"] = "Olá, Franco!" // Resultado: JavaScript Object.
console.log("Original: ", original)
console.log("Memória Compartilhada: ", memoria_compartilhada)
console.log("Cópia rasa: ", copia_rasa)
console.log("Cópia profunda: ", copia_profunda)

import copy

original = {
    "inteiro": 1,
    "real": 1.1,
    "vetor": [1, 2, 3],
    "dicionario": {
        "olá": "Olá, meu nome é Franco!"
    }
}
print("Original: ", original)

print("\nMemória compartilhada")
memoria_compartilhada = original
original["inteiro"] = 2
memoria_compartilhada["real"] = 2.2
print("Original: ", original)
print("Memória Compartilhada: ", memoria_compartilhada)

print("\nCópia Rasa")
copia_rasa = copy.copy(original)
memoria_compartilhada["inteiro"] = 3
original["inteiro"] = 3
memoria_compartilhada["real"] = 3.3
copia_rasa["inteiro"] = -33
copia_rasa["real"] = -33.3
copia_rasa["vetor"][0] = 111
copia_rasa["dicionario"]["olá"] = "Oi, meu nome é Franco!"
original["vetor"][1] = 222
print("Original: ", original)
print("Memória Compartilhada: ", memoria_compartilhada)
print("Cópia rasa: ", copia_rasa)

print("\nCópia Profunda")
copia_profunda = copy.deepcopy(original)
memoria_compartilhada["inteiro"] = 4
original["inteiro"] = 4
memoria_compartilhada["real"] = 4.4
copia_rasa["inteiro"] = -44
copia_rasa["real"] = -44.4
copia_rasa["vetor"][0] = 1234
copia_rasa["dicionario"]["olá"] = "Oi, meu nome é Franco!!!"
original["vetor"][1] = 1234
copia_profunda["inteiro"] = 999
copia_profunda["real"] = 999.99
copia_profunda["vetor"][0] = 999
copia_profunda["dicionario"]["olá"] = "Olá, Franco!"
print("Original: ", original)
print("Memória Compartilhada: ", memoria_compartilhada)
print("Cópia rasa: ", copia_rasa)
print("Cópia profunda: ", copia_profunda)

function escreva_indentacao(nivel)
    for indentacao = 1, nivel do
        -- Caso prefira indentação com tabulação, use a linha abaixo.
        -- io.write("\t")
        -- Para indentação com espaços, pode-se escolher o número a seguir.
        io.write("  ")
    end
end

-- tabela não pode ter uma referência para a própria tabela.
-- Caso contrário, a recursão será infinita.
-- O procedimento não escreve a chave recursivamente.
function escreva_tabela(tabela, nivel)
    -- O uso de or a seguir corresponde a:
    -- if (nivel ~= nil) then
    --     nivel = nivel
    -- else
    --     nivel = 1
    -- end
    -- No caso, isso faz com que nivel, caso omitido, seja inicializado com 1.
    nivel = nivel or 1
    if (type(tabela) == "table") then
        io.write("{\n")
        for chave, valor in pairs(tabela) do
            escreva_indentacao(nivel)
            io.write(tostring(chave) .. ": ")
            -- A chamada recursiva permitir escrever vetores ou dicionários
            -- que estejam armazenados como valor.
            escreva_tabela(valor, nivel + 1)
            io.write("\n")
        end
        escreva_indentacao(nivel - 1)
        io.write("},")
    else
        local aspas = ""
        if (type(tabela) == "string") then
            aspas = "\""
        end
        io.write(aspas .. tostring(tabela) .. aspas .. ",")
    end
end

-- <http://lua-users.org/wiki/CopyTable>
function shallowcopy(orig)
    local orig_type = type(orig)
    local copy
    if orig_type == 'table' then
        copy = {}
        for orig_key, orig_value in pairs(orig) do
            copy[orig_key] = orig_value
        end
    else -- number, string, boolean, etc
        copy = orig
    end
    return copy
end

-- <http://lua-users.org/wiki/CopyTable>
-- Save copied tables in `copies`, indexed by original table.
function deepcopy(orig, copies)
    copies = copies or {}
    local orig_type = type(orig)
    local copy
    if orig_type == 'table' then
        if copies[orig] then
            copy = copies[orig]
        else
            copy = {}
            copies[orig] = copy
            for orig_key, orig_value in next, orig, nil do
                copy[deepcopy(orig_key, copies)] = deepcopy(orig_value, copies)
            end
            setmetatable(copy, deepcopy(getmetatable(orig), copies))
        end
    else -- number, string, boolean, etc
        copy = orig
    end
    return copy
end

local original = {
    inteiro = 1,
    real = 1.1,
    vetor = {1, 2, 3},
    dicionario = {
        ["olá"] = "Olá, meu nome é Franco!"
    }
}

io.write("Original: ")
escreva_tabela(original)

print("\n\nMemória compartilhada")
local memoria_compartilhada = original
original["inteiro"] = 2
io.write("\nOriginal: ")
escreva_tabela(original)
io.write("\nMemória Compartilhada: ")
escreva_tabela(memoria_compartilhada)

print("\n\nCópia Rasa")
local copia_rasa = shallowcopy(original)
memoria_compartilhada["inteiro"] = 3
original["inteiro"] = 3
memoria_compartilhada["real"] = 3.3
copia_rasa["inteiro"] = -33
copia_rasa["real"] = -33.3
copia_rasa["vetor"][1] = 111
copia_rasa["dicionario"]["olá"] = "Oi, meu nome é Franco!"
original["vetor"][2] = 222
io.write("\nOriginal: ")
escreva_tabela(original)
io.write("\nMemória Compartilhada: ")
escreva_tabela(memoria_compartilhada)
io.write("\nCópia rasa: ")
escreva_tabela(copia_rasa)

print("\n\nCópia Profunda")
local copia_profunda = deepcopy(original)
memoria_compartilhada["inteiro"] = 4
original["inteiro"] = 4
memoria_compartilhada["real"] = 4.4
copia_rasa["inteiro"] = -44
copia_rasa["real"] = -44.4
copia_rasa["vetor"][1] = 1234
copia_rasa["dicionario"]["olá"] = "Oi, meu nome é Franco!!!"
original["vetor"][2] = 1234
copia_profunda["inteiro"] = 999
copia_profunda["real"] = 999.99
copia_profunda["vetor"][0] = 999
copia_profunda["dicionario"]["olá"] = "Olá, Franco!"
io.write("\nOriginal: ")
escreva_tabela(original)
io.write("\nMemória Compartilhada: ")
escreva_tabela(memoria_compartilhada)
io.write("\nCópia rasa: ")
escreva_tabela(copia_rasa)
io.write("\nCópia profunda: ")
escreva_tabela(copia_profunda)

extends Node

func _ready():
    var original = {
        "inteiro": 1,
        "real": 1.1,
        "vetor": [1, 2, 3],
        "dicionario": {
            "olá": "Olá, meu nome é Franco!"
        }
    }
    print("Original: ", original)

    print("\nMemória compartilhada")
    var memoria_compartilhada = original
    original["inteiro"] = 2
    memoria_compartilhada["real"] = 2.2
    print("Original: ", original)
    print("Memória Compartilhada: ", memoria_compartilhada)

    print("\nCópia Rasa")
    var copia_rasa = original.duplicate() # ou original.duplicate(false)
    memoria_compartilhada["inteiro"] = 3
    original["inteiro"] = 3
    memoria_compartilhada["real"] = 3.3
    copia_rasa["inteiro"] = -33
    copia_rasa["real"] = -33.3
    copia_rasa["vetor"][0] = 111
    copia_rasa["dicionario"]["olá"] = "Oi, meu nome é Franco!"
    original["vetor"][1] = 222
    print("Original: ", original)
    print("Memória Compartilhada: ", memoria_compartilhada)
    print("Cópia rasa: ", copia_rasa)

    print("\nCópia Profunda")
    var copia_profunda = original.duplicate(true)
    memoria_compartilhada["inteiro"] = 4
    original["inteiro"] = 4
    memoria_compartilhada["real"] = 4.4
    copia_rasa["inteiro"] = -44
    copia_rasa["real"] = -44.4
    copia_rasa["vetor"][0] = 1234
    copia_rasa["dicionario"]["olá"] = "Oi, meu nome é Franco!!!"
    original["vetor"][1] = 1234
    copia_profunda["inteiro"] = 999
    copia_profunda["real"] = 999.99
    copia_profunda["vetor"][0] = 999
    copia_profunda["dicionario"]["olá"] = "Olá, Franco!"
    print("Original: ", original)
    print("Memória Compartilhada: ", memoria_compartilhada)
    print("Cópia rasa: ", copia_rasa)
    print("Cópia profunda: ", copia_profunda)

Subrotinas (mesmas usadas para vetores):

JavaScript: Array.from() (documentação), JSON.parse() (documentação) e JSON.stringify() (documentação);
Python: copy.copy() e copy.deepcopy() (documentação);
Lua: shallowcopy() e deepcopy (fonte e documentação);
GDScript: duplicate (documentação).

A implementação em Lua apresenta um procedimento recursivo para escrever a tabela, chamado escreva_tabela(). Ele é uma versão aprimorada de escreva_vetor(), capaz de escrever vetores e dicionários aninhados. O procedimento utiliza apenas recursos estudados ao longo deste material. Para implementações mais completas, pode-se usar uma biblioteca externa ou consultar esta página do website Lua Users.

A implementação em JavaScript usando Map é imperfeita para a cópia profunda. Como comentado em vetores, o ideal seria usar uma biblioteca externa. Isso também aplica-se para a versão usando JavaScript Object.

Além disso, os exemplos são longos. Ao invés de executar o programa todo, pode ser mais interessante escrever as variáveis a cada modificação para observar mudanças. Duas boas estratégias para usar os exemplos são:

Analisar as mudanças linha a linha, escrevendo os dicionários relevantes;
Executar cada bloco definido, cada qual iniciado por um print().
- print("Original: ", original);
- print("\nMemória compartilhada");
- print("\nCópia Rasa");
- print("\nCópia Profunda").

Deve-se notar que apenas uma cópia profunda efetivamente duplica todos os valores armazenados de forma que eles se tornem independentes. Cópias rasas duplicam apenas tipos primitivos (ou outros tipos imutáveis), compartilhando tipos armazenados como referência. Memória compartilhada compartilha todos os valores.

Logo, quando se quiser uma cópia única, deve-se realizar uma cópia profunda. Qualquer outro tipo de atribuição ou cópia compartilha a memória (parcialmente ou totalmente).

Outras Estruturas de Dados

Vetores e dicionários são excelentes estruturas de dados para aprendizado de programação e para prototipação de sistemas. Entretanto, existem outras estruturas de dados que podem ser mais convenientes para resolver certos problemas ou para melhorar o desempenho de um programa.

Embora a preocupação com desempenho não deva ser uma prioridade para iniciantes, maior conveniência para resolver problemas sempre é útil. Assim, esta seção apresenta algumas estruturas de dados adicionais. Existem muitas outras estruturas não comentadas neste momento; as que serão descritas podem ser implementadas com facilidade usando-se vetores e/ou dicionários.

Pilhas (Stacks)

O termo pilha (stack) já apareceu em tópicos anteriores. Por exemplo, o termo apareceu em estouro de pilha (stack overflow), que é um potencial erro para a definição de subrotinas recursivas, dentre outros, sem um caso base adequado.

Pilhas em programação não são baterias (embora elas também tenham uma capacidade). Pilhas são uma estrutura de dados na qual o último elemento adicionado é o primeiro elemento a ser removido. A estrutura também é conhecida como last-in, first-out (LIFO; último dentro, primeiro fora).

Um dos exemplos mais tradicionais de uma pilha no mundo real é uma pilha de pratos. Outro exemplo é uma pilha de cadeiras (como de plástico). Um terceiro exemplo é uma pilha de panquecas, como no estilo de filmes estado-unidenses. Um quarto exemplo são pilhas de cartas em jogos de baralho ou jogos de cartas (card games). Quando se obtém a carta do topo, desempilha-se uma pilha.

Quando se empilha um prato, o segundo é colocado sobre o primeiro. O terceiro é colocado sobre o segundo, e assim sucessivamente. O primeiro prato a ser removido é do topo da pilha.

Pilhas em programação funcionam da mesma forma. Por exemplo, caso se empilhe (push) um valor A, depois um valor B, depois um valor C, o resultado é uma seqüência [A, B, C]. Assim, não se escolhe uma ordem para inserção; o novo elemento sempre é adicionado no topo.

Quando se desempilha (pop) um valor da pilha, também não se escolhe um em particular, mas se remove o elemento do topo. Assim, no caso anterior, os elementos seriam removidos na ordem C (primeiro a sair, que foi o último a entrada), B e A (último a sair, que foi o primeiro a entrar). Remover todos os elementos da pilha em ordem correto é chamado de esvaziar a pilha. Tentar remover um elemento de uma pilha vazia é um erro.

Evidentemente, aplicações reais tendem a ser um pouco mais complexas. Por exemplo, poder-se-ia empilhar A, B, C, depois desempilhar um valor (C), resultando em [A, B]. Em seguida, poder-se-ia empilhar D e E, resultando em [A, B, D, E]. Agora, esvaziar a pilha removeria os elementos na ordem E (primeiro), D, B, A (último). Os elementos disponíveis dependem, pois, tanto da ordem de empilhamento quando da quantidade (e da ordem) de desempilhamentos.

Pilhas possuem um tamanho mínimo, que é zero, chamado de pilha vazia. Pilhas podem possui um tamanho máximo, chamado de capacidade (como em vetores, dicionários e outras estruturas de dados). Uma pilha sem limite arbitrário ainda é restrita, em última instância, pela quantidade de memória de um computador. Assim, na prática, toda estrutura de dados é finita em programação.

A limitação permite entender o que é um estouro de pilha. Simplificadamente, todo processo tem uma quantidade máxima de memória que pode ser alocada em uma região de memória chamada pilha. Algumas alocações usam memória da pilha. Variáveis locais e chamadas de funções (retornos e endereços) costumam ser alocados nela. Caso seja feito um número de chamadas recursivas que exaura a memória disponível na pilha, o programa não poderá fazer novas chamadas recursivas. De fato, o programa não pode mais alocar nenhuma memória na pilha. Por falta de memória na pilha, uma nova tentativa resulta em estouro de pilha.

Algumas linguagens de programação fornecem implementações de pilhas na biblioteca padrão. Em linguagens que não forneçam, pode-se usar uma biblioteca externa ou um vetor. Para usar um vetor, toda nova inserção deve ser feita no fim. Toda nova remoção também deve ser feita no fim. Alternativamente, pode-se adicionar valores e removê-los sempre do início, embora a operação costume ser mais cara.

let pilha = []
// Inserção no fim.
pilha.push(1)
pilha.push(2)
pilha.push(3)
console.log(pilha) // [1, 2, 3]

// Remoção do fim.
let valor_removido = pilha.pop() // 3
console.log(pilha) // [1, 2]

pilha.push(4)
console.log(pilha) // [1, 2, 4]

pilha.pop()
console.log(pilha) // [1, 2]

pilha.pop()
console.log(pilha) // [1]

pilha.pop()
console.log(pilha) // []

pilha = []
# Inserção no fim.
pilha.append(1)
pilha.append(2)
pilha.append(3)
print(pilha) # [1, 2, 3]

# Remoção do fim.
valor_removido = pilha.pop() # 3
print(pilha) # [1, 2]

pilha.append(4)
print(pilha) # [1, 2, 4]

pilha.pop()
print(pilha) # [1, 2]

pilha.pop()
print(pilha) # [1]

pilha.pop()
print(pilha) # []

function escreva_vetor(pilha)
    if (pilha == nil) then
        return
    end

    local tamanho = #pilha
    io.write("[")
    for indice = 1, tamanho do
        io.write(pilha[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

local pilha = {}
-- Inserção no fim.
table.insert(pilha, 1)
pilha[#pilha + 1] = 2 -- Forma alternativa.
table.insert(pilha, #pilha + 1, 3) -- Forma equivalente.
escreva_vetor(pilha) -- [1, 2, 3]

-- Remoção do fim.
local valor_removido = table.remove(pilha) -- 3
escreva_vetor(pilha) -- [1, 2]

table.insert(pilha, 4)
escreva_vetor(pilha) -- [1, 2, 4]

table.remove(pilha)
escreva_vetor(pilha) -- [1, 2]

table.remove(pilha)
escreva_vetor(pilha) -- [1]

table.remove(pilha)
escreva_vetor(pilha) -- []

extends Node

func _ready():
    var pilha = []
    # Inserção no fim.
    pilha.append(1)
    pilha.push_back(2) # Alternativa.
    pilha.append(3)
    print(pilha) # [1, 2, 3]

    # Remoção do fim.
    var valor_removido = pilha.pop_back() # 3
    print(pilha) # [1, 2]

    pilha.append(4)
    print(pilha) # [1, 2, 4]

    pilha.pop_back()
    print(pilha) # [1, 2]

    pilha.pop_back()
    print(pilha) # [1]

    pilha.pop_back()
    print(pilha) # []

Quando um elemento é desempilhado, uma chamada a pop() costuma fornecer o valor removido. Caso ela não seja retorne o valor, a pilha costuma fornecer um método para consultar o valor do topo (por exemplo, top() ou peek()). Consultar o valor do topo não remove o valor da pilha, mas permite descobrir o valor armazenado.

Em implementações na quais a remoção ou a inserção no fim sejam operações caras, pode ser preferível implementar uma estrutura de dados pilha propriamente dita (ou usar uma biblioteca com implementação eficiente).

Por exemplo, Python fornece uma implementação de pilha na biblioteca padrão.

from queue import LifoQueue

# Para tamanho infinito, pode-se usar maxsize=0 ou com número negativo.
pilha = LifoQueue(maxsize = 3)
# Inserção no fim.
pilha.put(1)
pilha.put(2)
pilha.put(3)
print(pilha.qsize(), pilha.full(), pilha.empty()) # 3, True, False

# Remoção do fim.
valor_removido = pilha.get() # 3
print(valor_removido)

pilha.put(4)

valor_removido = pilha.get() # 4
print(valor_removido)

valor_removido = pilha.get() # 2
print(valor_removido)

valor_removido = pilha.get() # 1
print(valor_removido)
print(pilha.empty())

A classe LifoQueue (documentação) implementa uma pilha. O método put() (documentação) empilha valores e o método get() (documentação) desempilha o valor do topo da pilha. Caso se defina maxsize no construtor de LifoQueue, pode-se escolher o número máximo de valores que se pode armazenar. O método empty() (documentação) esvazia a pilha.

Filas (Queues)

Em diversas culturas, pessoas possuem o hábito de formar filas (queues) para atendimento ou para a realização de alguma atividade na ordem de chegada.

Filas em programação são uma estrutura de dados nas quais os elementos são removidos na mesma ordem de inserção. A estrutura é também é conhecida como first-in, first-out (FIFO; primeiro dentro, primeiro fora).

A operação de adicionar um elemento a uma fila costuma chamar enfileirar (enqueue) ou adicionar. A operação de remover um elemento da fila costuma chamar desenfileirar (dequeue) ou remover. Assim como pilhas, filas podem possuir uma capacidade máxima, pode-se esvaziar uma fila (removendo-se elementos na ordem de inserção), e é um erro tentar desenfileirar um valor de uma fila vazia.

Filas são comuns em programas. Por exemplo, uma lista de reprodução de músicas que toca na ordem definida trabalha como uma fila. Memórias para tarefas chamadas de buffers também utilizam filas.

Assim como pilhas, algumas linguagens de programação fornecem implementações de filas na biblioteca padrão. Em linguagens que não forneçam, pode-se usar uma biblioteca externa ou um vetor. Para usar um vetor, toda nova inserção deve ser feita no fim. Toda nova remoção deve ser feita no início. Também é possível adicionar todo novo elemento no início, e remover todo elemento do fim.

let fila = []
// Inserção no fim.
fila.push(1)
fila.push(2)
fila.push(3)
console.log(fila) // [1, 2, 3]

// Remoção do fim.
let valor_removido = fila.shift() // 1
console.log(fila) // [2, 3]

fila.push(4)
console.log(fila) // [2, 3, 4]

fila.shift()
console.log(fila) // [3, 4]

fila.shift()
console.log(fila) // [4]

fila.shift()
console.log(fila) // []

fila = []
# Inserção no fim.
fila.append(1)
fila.append(2)
fila.append(3)
print(fila) # [1, 2, 3]

# Remoção do fim.
valor_removido = fila.pop(0) # 1
print(fila) # [2, 3]

fila.append(4)
print(fila) # [2, 3, 4]

fila.pop(0)
print(fila) # [3, 4]

fila.pop(0)
print(fila) # [4]

fila.pop(0)
print(fila) # []

function escreva_vetor(fila)
    if (fila == nil) then
        return
    end

    local tamanho = #fila
    io.write("[")
    for indice = 1, tamanho do
        io.write(fila[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

local fila = {}
-- Inserção no fim.
table.insert(fila, 1)
fila[#fila + 1] = 2 -- Forma alternativa.
table.insert(fila, #fila + 1, 3) -- Forma equivalente.
escreva_vetor(fila) -- [1, 2, 3]

-- Remoção do fim.
local valor_removido = table.remove(fila, 1) -- 1
escreva_vetor(fila) -- [2, 3]

table.insert(fila, 4)
escreva_vetor(fila) -- [2, 3, 4]

table.remove(fila, 1)
escreva_vetor(fila) -- [3, 4]

table.remove(fila, 1)
escreva_vetor(fila) -- [4]

table.remove(fila, 1)
escreva_vetor(fila) -- []

extends Node

func _ready():
    var fila = []
    # Inserção no fim.
    fila.append(1)
    fila.push_back(2) # Alternativa.
    fila.append(3)
    print(fila) # [1, 2, 3]

    # Remoção do fim.
    var valor_removido = fila.pop_front() # 1
    print(fila) # [2, 3]

    fila.append(4)
    print(fila) # [2, 3, 4]

    fila.pop_front()
    print(fila) # [3, 4]

    fila.pop_front()
    print(fila) # [4]

    fila.pop_front()
    print(fila) # []

Embora remoções do início possam ser caras (por exemplo, ) em algumas implementações de vetores, elas podem ser usadas para protótipos ou problemas com tamanho pequeno. Para problemas que requeiram filas grandes, pode ser preferível escolher uma implementação de pilha com melhor desempenho.

Por exemplo, Python fornece uma implementação para fila na biblioteca padrão.

from queue import Queue

# Para tamanho infinito, pode-se usar maxsize=0 ou com número negativo.
fila = Queue(maxsize = 3)
# Inserção no fim.
fila.put(1)
fila.put(2)
fila.put(3)
print(fila.qsize(), fila.full(), fila.empty()) # 3, True, False

# Remoção do início.
valor_removido = fila.get() # 1
print(valor_removido)

fila.put(4)

valor_removido = fila.get() # 2
print(valor_removido)

valor_removido = fila.get() # 3
print(valor_removido)

valor_removido = fila.get() # 4
print(valor_removido)
print(fila.empty())

A classe Queue (documentação) implementa uma fila (também pode-se usar SimpleQueue para uma fila sem limites de tamanho). A interface é a mesma definida para LifoQueue, mas put() enfileira um valor na última posição e get() desenfileira o primeiro a ser removido.

Filas de Prioridade (Priority Queues)

Uma variação de implementação para filas é uma fila de prioridade (priority queue). Em filas de prioridade, a ordem de inserção de elementos em uma fila pode depender do valor de um atributo adotado como prioridade. Valores com maior prioridade são adicionados antes de valores com menor prioridade, o que permite removê-los antes.

A definição de prioridade para cada elemento pode ser feita com maior facilidade usando-se registros, que será o próximo tópico de estudo.

Neste momento, como alternativa, pode-se declarar diversas filas, cada qual representando uma certa prioridade. Ao se tentar remover o próximo elemento, um elemento será removido da fila não vazia de maior prioridade.

Python fornece uma implementação para fila de prioridade no módulo queue chamada de PriorityQueue.

Conjuntos (Sets)

Como em Matemática, conjuntos (sets) são coleções não se pode armazenar valores duplicados. A ordem dos valores não importa, mas a estrutura de dados não admite duplicatas.

Pode-se implementar conjuntos usando vetores com facilidade: basta verificar pela existência do valor antes de tentar adicioná-lo. Caso o valor já exista, ele não deve ser adicionado novamente no vetor. Caso contrário, deve-se adicioná-lo.

function adicione_conjunto(vetor, valor) {
    if (!vetor.includes(valor)) {
        vetor.push(valor)
    }
}

let conjunto = []
adicione_conjunto(conjunto, "a")
adicione_conjunto(conjunto, "b")
adicione_conjunto(conjunto, "c")
adicione_conjunto(conjunto, "c")
adicione_conjunto(conjunto, "c")
console.log(conjunto)
console.log(conjunto.includes("a"))
console.log(conjunto.includes("d"))

def adicione_conjunto(vetor, valor):
    if (not valor in vetor):
        vetor.append(valor)

conjunto = []
adicione_conjunto(conjunto, "a")
adicione_conjunto(conjunto, "b")
adicione_conjunto(conjunto, "c")
adicione_conjunto(conjunto, "c")
adicione_conjunto(conjunto, "c")
print(conjunto)
print("a" in conjunto)
print("d" in conjunto)

function escreva_vetor(fila)
    if (fila == nil) then
        return
    end

    local tamanho = #fila
    io.write("[")
    for indice = 1, tamanho do
        io.write(fila[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

function busca_sequencial(vetor, valor)
    for indice, valor_atual in ipairs(vetor) do
        if (valor == valor_atual) then
            return indice
        end
    end

    return -1
end

function pertence_ao_conjunto(vetor, valor)
    return (busca_sequencial(vetor, valor) ~= -1)
end

function adicione_conjunto(vetor, valor)
    if (not pertence_ao_conjunto(vetor, valor)) then
        table.insert(vetor, valor)
    end
end

conjunto = {}
adicione_conjunto(conjunto, "a")
adicione_conjunto(conjunto, "b")
adicione_conjunto(conjunto, "c")
adicione_conjunto(conjunto, "c")
adicione_conjunto(conjunto, "c")
escreva_vetor(conjunto)
print(pertence_ao_conjunto(conjunto, "a"))
print(pertence_ao_conjunto(conjunto, "d"))

extends Node

func adicione_conjunto(vetor, valor):
    if (not valor in vetor):
        vetor.append(valor)

func _ready():
    var conjunto = []
    adicione_conjunto(conjunto, "a")
    adicione_conjunto(conjunto, "b")
    adicione_conjunto(conjunto, "c")
    adicione_conjunto(conjunto, "c")
    adicione_conjunto(conjunto, "c")
    print(conjunto)
    print("a" in conjunto)
    print("d" in conjunto)

Também é possível implementar conjuntos usando dicionários. No caso, pode-se usar a chave como garantia de unicidade do valor. Quando se adicionar um valor, basta inserir qualquer valor (por exemplo, Verdadeiro) com a chave requerida. Como dicionários não admitem chaves duplicadas, o valor é indiferente (basta que a chave exista). Para se remover o valor, basta remover a entrada usando a chave.

Python ({}; documentação) e JavaScript (Set; documentação) fornecem implementações de conjuntos na biblioteca padrão.

let conjunto = new Set()
conjunto.add("a")
conjunto.add("b")
conjunto.add("c")
conjunto.add("c")
conjunto.add("c")
console.log(conjunto) // "a", "b", "c"
console.log(conjunto.has("a"))
console.log(conjunto.has("d"))

conjunto = {"a", "b", "c", "c", "c"}
print(conjunto) # {"a", "b", "c"}
print("a" in conjunto)
print("d" in conjunto)

Em Python, a sintaxe é similar a de dicionários, mas os elementos possuem apenas o valor (não uma combinação de chave e valor).

Programação Funcional: Map, For Each, Reduce e Filter

Muitas linguagens de programação modernas e frameworks começaram a adotar técnicas do paradigma de programação funcional em bibliotecas. Um exemplo para JavaScript é React, usando para programação de sistemas Web.

Em estilo procedural, todas as seguintes operações podem ser feitas usando-se estruturas de repetição:

Map;
For Each;
Reduce, Fold ou Accumulate;
Filter.

Também existem outras operações comuns, como, por exemplo:

Iterate;
Zip.

Em paradigma funcional, pode-se abstrair a repetição por meio de uma chamada de função, que implementará a repetição e executará o código fornecido como parâmetro (por exemplo, usando uma função anônima ou lambda). O resultado da expressão será uma coleção que aplica o código a cada elemento e calcula o resultado (ou o efeito colateral).

Um exemplo de uso de função como parâmetro neste tópico foi usado na ordenação de vetores em JavaScript. O próximo exemplo mostra como reescrever algumas técnicas de forma mais funcional (ao invés de imperativa). Lua e GDScript não definem subrotinas para map(), reduce(), filter() e for_each(). Como a linguagem permite passar funções como parâmetros, os exemplos ilustram possíveis implementações. O mesmo aplica-se para for_each() em Python.

let numeros = [1, 2, 3, 4]

let quadrados = numeros.map(function(valor) {
    return (valor * valor)
})
console.log(quadrados)

// O código anterior pode ser reescrito como:
quadrados = numeros.map(valor => valor * valor)
console.log(quadrados)

// Similar a map, quando se deseja criar um procedimento ao invés de uma função
// (objetivo é o efeito colateral).
quadrados.forEach(valor => console.log(valor))

let somatorio_quadrados = quadrados.reduce((resultado_anterior, proximo_valor) => (resultado_anterior + proximo_valor), 0)
console.log(somatorio_quadrados)

let quadrados_pares = quadrados.filter(valor => (valor % 2 === 0))
console.log(quadrados_pares)

// Combinação de operações: somatório de quadrados pares.
let resultado_parcial = numeros.map(valor => valor * valor)
resultado_parcial = resultado_parcial.filter(valor => (valor % 2 === 0))
let resultado = resultado_parcial.reduce((resultado_anterior, proximo_valor) => (resultado_anterior + proximo_valor), 0)
console.log(resultado)

// Em uma única atribuição:
resultado = numeros.map(valor => valor * valor)
                   .filter(valor => (valor % 2 === 0))
                   .reduce((resultado_anterior, proximo_valor) => (resultado_anterior + proximo_valor), 0)
console.log(resultado)

from functools import reduce

def for_each(funcao, vetor):
    for valor in vetor:
        funcao(valor)

numeros = [1, 2, 3, 4]

quadrados = list(map(lambda valor: (valor * valor), numeros))
print(quadrados)

# Similar a map, quando se deseja criar um procedimento ao invés de uma função
# (objetivo é o efeito colateral).
for_each(lambda valor: print(valor), quadrados)

somatorio_quadrados = reduce(lambda resultado_anterior, proximo_valor: (resultado_anterior + proximo_valor), quadrados, 0)
print(somatorio_quadrados)

quadrados_pares = list(filter(lambda valor: (valor % 2 == 0), quadrados))
print(quadrados_pares)

# Combinação de operações: somatório de quadrados pares.
resultado_parcial = list(map(lambda valor: (valor * valor), numeros))
resultado_parcial = list(filter(lambda valor: (valor % 2 == 0), resultado_parcial))
resultado = reduce(lambda resultado_anterior, proximo_valor: (resultado_anterior + proximo_valor), resultado_parcial, 0)
print(resultado)

# Em uma única atribuição:
resultado = reduce(lambda resultado_anterior, proximo_valor: (resultado_anterior + proximo_valor),
                   list(filter(lambda valor: (valor % 2 == 0),
                               list(map(lambda valor: (valor * valor),
                                        numeros)))),
                   0)
print(resultado)

function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write(vetor[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

function map(tabela, funcao)
    local resultado = {}
    for chave, valor in pairs(tabela) do
        resultado[chave] = funcao(valor)
    end

    return resultado
end

function for_each(tabela, procedimento)
    for chave, valor in pairs(tabela) do
        procedimento(valor)
    end
end

function reduce(tabela, funcao, resultado_inicial)
    local resultado = resultado_inicial
    for chave, proximo_valor in pairs(tabela) do
        resultado = funcao(resultado, proximo_valor)
    end

    return resultado
end

function filter(tabela, funcao)
    local resultado = {}
    for chave, valor in pairs(tabela) do
        if (funcao(valor)) then
            if (type(chave) == "number") then
                table.insert(resultado, valor)
            else
                resultado[chave] = valor
            end
        end
    end
    return resultado
end

local numeros = {1, 2, 3, 4}
local quadrados = map(numeros,
                      function (valor)
                          return (valor * valor)
                      end)
escreva_vetor(quadrados)

-- Similar a map, quando se deseja criar um procedimento ao invés de uma função
-- (objetivo é o efeito colateral).
for_each(quadrados,
        function(valor)
            print(valor)
        end)

local somatorio_quadrados = reduce(quadrados,
                                   function (resultado_anterior, proximo_valor)
                                       return (resultado_anterior + proximo_valor)
                                   end,
                                   0)
print(somatorio_quadrados)

local quadrados_pares = filter(quadrados,
                               function (valor)
                                   return (valor % 2 == 0)
                               end)
escreva_vetor(quadrados_pares)

-- Combinação de operações: somatório de quadrados pares.
local resultado_parcial = map(numeros,
                              function (valor)
                                  return (valor * valor)
                              end)
resultado_parcial = filter(resultado_parcial,
                           function (valor)
                               return (valor % 2 == 0)
                           end)
local resultado = reduce(resultado_parcial,
                         function (resultado_anterior, proximo_valor)
                             return (resultado_anterior + proximo_valor)
                         end,
                         0)
print(resultado)

-- Em uma única atribuição:
resultado = reduce(filter(map(numeros,
                              function (valor) return (valor * valor) end),
                          function (valor) return (valor % 2 == 0) end),
                   function (resultado_anterior, proximo_valor) return (resultado_anterior + proximo_valor) end,
                   0)
print(resultado)

# A versão 3 de Godot Engine não permite definir funções lambda.
# Assim, os exemplos definem funções e procedimentos explicitamente para que a
# implementação funcione com Godot 3.

extends Node

func map(vetor, funcao):
    var resultado = []
    for valor in vetor:
        resultado.push_back(call(funcao, valor))

    return resultado

func for_each(vetor, funcao):
    for valor in vetor:
        call(funcao, valor)

func reduce(vetor, funcao, resultado_inicial):
    var resultado = resultado_inicial
    for proximo_valor in vetor:
        resultado = call(funcao, resultado, proximo_valor)

    return resultado

func filter(vetor, funcao):
    var resultado = []
    for valor in vetor:
        if (call(funcao, valor)):
            resultado.append(valor)

    return resultado

func quadrado(x):
    return (x * x)

func escreva_numero(x):
    print(x)

func soma(x, y):
    return (x + y)

func numero_par(x):
    return (x % 2 == 0)

func _ready():
    var numeros = [1, 2, 3, 4]

    var quadrados = map(numeros, "quadrado")
    print(quadrados)

    # Similar a map, quando se deseja criar um procedimento ao invés de uma função
    # (objetivo é o efeito colateral).
    for_each(quadrados, "escreva_numero")

    var somatorio_quadrados = reduce(quadrados, "soma", 0)
    print(somatorio_quadrados)

    var quadrados_pares = filter(quadrados, "numero_par")
    print(quadrados_pares)

    # Combinação de operações: somatório de quadrados pares.
    var resultado_parcial = map(numeros, "quadrado")
    resultado_parcial = filter(resultado_parcial, "numero_par")
    var resultado = reduce(resultado_parcial, "soma", 0)
    print(resultado)

    # Em uma única atribuição:
    resultado = reduce(filter(map(numeros,
                                  "quadrado"),
                              "numero_par"),
                        "soma",
                        0)
    print(resultado)

Subrotinas:

JavaScript: map() (documentação), forEach() (documentação), reduce() (documentação), filter (documentação);
Python: map() (documentação), reduce() (documentação), filter() (documentação);
Lua: não fornece subrotinas;
GDScript: não fornece subrotinas. A implementação usa call() (documentação) para chamar a função pelo nome fornecido.

As versões em JavaScript e GDScript podem ser mais ilustrativas. JavaScript por fornecer um operador especial (=>) para retornar facilmente resultados em funções. GDScript pelo fato da versão 3 de Godot Engine não permitir o uso de funções anônimas, requerendo a passagem do nome da subrotina.

O código resultante é compacto e elegante, embora diferente. Diferentemente do paradigma imperativo, o paradigma funcional constrói programas primariamente como combinações de funções. De certa forma, código funcional é mais abstrato e próximo da Matemática, porque a chamada de uma subrotina pode abstrair parte da estrutura do programa.

Para referência, pode-se comparar a versão funcional com uma versão imperativa.

let numeros = [1, 2, 3, 4]

let quadrados = []
for (valor of numeros) {
    quadrados.push(valor * valor)
}

for (valor of quadrados) {
     console.log(valor)
}

let somatorio_quadrados = 0
for (proximo_valor of quadrados) {
     somatorio_quadrados += proximo_valor
}

console.log(somatorio_quadrados)

let quadrados_pares = []
for (valor of quadrados) {
    if (valor % 2 === 0) {
        quadrados_pares.push(valor)
    }
}

// Combinação de operações: somatório de quadrados pares.
let resultado_parcial = quadrados_pares
let resultado = 0
for (proximo_valor of resultado_parcial) {
    resultado += proximo_valor
}
console.log(resultado)

// Em uma única estrutura de repetição:
resultado = 0
for (valor of numeros) {
    let quadrado = valor * valor
    if (valor % 2 === 0) {
        resultado += quadrado
    }
}

console.log(resultado)

numeros = [1, 2, 3, 4]

quadrados = []
for valor in numeros:
    quadrados.append(valor * valor)

for valor in quadrados:
     print(valor)

somatorio_quadrados = 0
for proximo_valor in quadrados:
     somatorio_quadrados += proximo_valor

print(somatorio_quadrados)

quadrados_pares = []
for valor in quadrados:
    if (valor % 2 == 0):
        quadrados_pares.append(valor)

# Combinação de operações: somatório de quadrados pares.
resultado_parcial = quadrados_pares
resultado = 0
for proximo_valor in resultado_parcial:
    resultado += proximo_valor

print(resultado)

# Em uma única estrutura de repetição:
resultado = 0
for valor in numeros:
    quadrado = valor * valor
    if (valor % 2 == 0):
        resultado += quadrado

print(resultado)

local numeros = {1, 2, 3, 4}

local quadrados = {}
for _, valor in ipairs(numeros) do
    table.insert(quadrados, valor * valor)
end

for _, valor in ipairs(quadrados) do
     print(valor)
end

local somatorio_quadrados = 0
for _, proximo_valor in ipairs(quadrados) do
     somatorio_quadrados = somatorio_quadrados + proximo_valor
end

print(somatorio_quadrados)

local quadrados_pares = {}
for _, valor in ipairs(quadrados) do
    if (valor % 2 == 0) then
        table.insert(quadrados_pares, valor)
    end
end

-- Combinação de operações: somatório de quadrados pares.
local resultado_parcial = quadrados_pares
local resultado = 0
for _, proximo_valor in ipairs(resultado_parcial) do
    resultado = resultado + proximo_valor
end

print(resultado)

-- Em uma única estrutura de repetição:
resultado = 0
for _, valor in ipairs(numeros) do
    local quadrado = valor * valor
    if (valor % 2 == 0) then
        resultado = resultado + quadrado
    end
end

print(resultado)

extends Node

func _ready():
    var numeros = [1, 2, 3, 4]

    var quadrados = []
    for valor in numeros:
        quadrados.append(valor * valor)

    for valor in quadrados:
         print(valor)

    var somatorio_quadrados = 0
    for proximo_valor in quadrados:
         somatorio_quadrados += proximo_valor

    print(somatorio_quadrados)

    var quadrados_pares = []
    for valor in quadrados:
        if (valor % 2 == 0):
            quadrados_pares.append(valor)

    # Combinação de operações: somatório de quadrados pares.
    var resultado_parcial = quadrados_pares
    var resultado = 0
    for proximo_valor in resultado_parcial:
        resultado += proximo_valor

    print(resultado)

    # Em uma única estrutura de repetição:
    resultado = 0
    for valor in numeros:
        var quadrado = valor * valor
        if (valor % 2 == 0):
            resultado += quadrado

    print(resultado)

Na solução imperativa, para evitar repetir estruturas de repetição, resultado_parcial inicia com o resultado calculado para quadrados_pares. Assim, a versão com resultado_parcial e resultado gera primeiro os vetores, para depois fazer a soma.

A versão iterativa em uma única estrutura repetição realiza o somatório do resultado final a cada passo. Ao invés de gerar todos os valores e vetores intermediários, o resultado final é calculado termo a termo. Ambas as formas geram o mesmo resultado, mas a alternativa usa uma única estrutura de repetição ao invés de três em seqüência.

De certa forma, a versão funcional pode permitir pensar no vetor como um todo: pensa-se em como gerar uma expressão que se possa aplicar para todo o vetor. Do todo, para a parte. Na versão iterativa, pensa-se na solução elemento a elemento e repete-se o processo para todo o vetor. Da parte, para o todo.

Soluções computacionais podem ser expressas em diferentes paradigmas de programação. Conhecendo vários, você pode escolher o que melhor puder expressar a solução para um determinado problema. O aprendizado de diferentes paradigmas fornece ferramentas adicionais para seu inventário, além de promover novas formas de pensar em solução de problemas.

Exemplos

Coleções permitem trabalhar mais facilmente com grandes quantidades de dados. O processo de resolver problemas é simples: resolve-se o problema genericamente para um valor, repete-se a solução concebida para os demais. Em outras palavras, realiza-se um trabalho braçal apenas uma vez. O trabalho repetitivo é automatizado pela máquina.

As próximas subseções apresentam alguns exemplos de problemas reais resolvidos usando coleções. Pode-se observar que todos eles repetem um mesmo processamento para todos (ou múltiplos) valores armazenados em uma coleção.

Embaralhar Vetor e Sortear Valores

Um antônimo de ordem é caos. A ordenação é uma operação que define uma ordem arbitrária para elementos armazenados. O contrário de ordenar é misturar ou embaralhar (shuffle).

Existem várias formas de embaralhar um vetor. Pode-se pensar, por exemplo, em sortear valores presentes em um vetor para criar um novo com elementos em ordem aleatória. Também é possível pensar em sortear índices de um vetor e trocá-los no mesmo vetor, como uma estratégia in-place.

Ambas as estratégias são válidas. Como a segunda talvez seja menos imediata de pensar que a primeira, o exemplo a seguir apresenta uma implementação. A solução apresentada é uma variação do algoritmo chamado Fisher-Yates shuffle ou Knuth-shuffle.

function inteiro_aleatorio(minimo_inclusive, maximo_inclusive) {
    let minimo = Math.ceil(minimo_inclusive)
    let maximo = Math.floor(maximo_inclusive)

    return Math.floor(minimo + Math.random() * (maximo + 1 - minimo))
}

function embaralhar_vetor(vetor, numero_vezes) {
    let tamanho_vetor = vetor.length
    console.assert(tamanho_vetor > 0)

    let ultimo_indice = tamanho_vetor - 1
    for (let i = 0; i < numero_vezes; ++i) {
        let primeiro_indice = inteiro_aleatorio(0, ultimo_indice)
        let segundo_indice = inteiro_aleatorio(0, ultimo_indice)

        let temporario = vetor[primeiro_indice]
        vetor[primeiro_indice] = vetor[segundo_indice]
        vetor[segundo_indice] = temporario
    }
}

let numeros = []
for (let i = 0; i < 50; ++i) {
    numeros.push(i + 1)
}

console.log(numeros)

embaralhar_vetor(numeros, 100)
console.log(numeros)

import random

def embaralhar_vetor(vetor, numero_vezes):
    tamanho_vetor = len(vetor)
    assert(tamanho_vetor > 0)

    ultimo_indice = tamanho_vetor - 1
    for i in range(numero_vezes):
        primeiro_indice = random.randint(0, ultimo_indice)
        segundo_indice = random.randint(0, ultimo_indice)

        vetor[primeiro_indice], vetor[segundo_indice] = vetor[segundo_indice], vetor[primeiro_indice]

random.seed()
numeros = []
for i in range(50):
    numeros.append(i + 1)

print(numeros)

embaralhar_vetor(numeros, 100)
print(numeros)

function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write(vetor[indice])
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

function embaralhar_vetor(vetor, numero_vezes)
    local tamanho_vetor = #vetor
    assert(tamanho_vetor > 0)

    local ultimo_indice = tamanho_vetor
    for i = 1, numero_vezes do
        local primeiro_indice = math.random(1, ultimo_indice)
        local segundo_indice = math.random(1, ultimo_indice)

        vetor[primeiro_indice], vetor[segundo_indice] = vetor[segundo_indice], vetor[primeiro_indice]
    end
end

math.randomseed(os.time())
numeros = {}
for i = 1, 50 do
    table.insert(numeros, i)
end

escreva_vetor(numeros)

embaralhar_vetor(numeros, 100)
escreva_vetor(numeros)

extends Node

func inteiro_aleatorio(minimo_inclusive, maximo_inclusive):
    var minimo = ceil(minimo_inclusive)
    var maximo = floor(maximo_inclusive)

    # randi(): [0.0, 1.0[
    return randi() % int(maximo + 1 - minimo) + minimo

func embaralhar_vetor(vetor, numero_vezes):
    var tamanho_vetor = len(vetor)
    assert(tamanho_vetor > 0)

    var ultimo_indice = tamanho_vetor - 1
    for i in range(numero_vezes):
        var primeiro_indice = inteiro_aleatorio(0, ultimo_indice)
        var segundo_indice = inteiro_aleatorio(0, ultimo_indice)

        var temporario = vetor[primeiro_indice]
        vetor[primeiro_indice] = vetor[segundo_indice]
        vetor[segundo_indice] = temporario

func _ready():
    randomize()

    var numeros = []
    for i in range(50):
        numeros.append(i + 1)

    print(numeros)

    embaralhar_vetor(numeros, 100)
    print(numeros)

Caso se queira apenas um valor escolhido aleatoriamente no vetor, pode-se, simplesmente, sortear um índice e acessar o valor. Embaralhar um vetor é útil quando se precisa acessar todos os valores armazenados sem riscos de sortear um mesmo índice.

Algumas implementações de vetores ou linguagens de programação fornecem subrotinas para embaralhar vetores na biblioteca padrão.

import random

random.seed()
numeros = []
for i in range(50):
    numeros.append(i + 1)

print(numeros)

random.shuffle(numeros)
print(numeros)

extends Node

func _ready():
    randomize()

    var numeros = []
    for i in range(50):
        numeros.append(i + 1)

    print(numeros)

    numeros.shuffle()
    print(numeros)

Python fornece o método shuffle() (documentação), da biblioteca random. GDScript fornece o método shuffle() (documentação).

Com vetores, pilhas, filas e embaralhamento, é possível implementar muitos jogos de cartas.

Estatísticas para Textos: Contagem de Palavras

Quantas palavras existem em um determinado texto? Quantas palavras diferentes (únicas) existem nele? Quantas vezes cada uma delas aparece?

Criar um programa simples que forneça a resposta é relativamente fácil usando dicionários. Criar um programa mais sofisticado requer maiores esforços. Assim, esta subseção ilustra um protótipo inicial.

Para iniciar a solução, pode-se aplicar um algoritmo de split para separar o texto de uma frase em um vetor. Em seguida, pode-se iterar por cada valor do vetor. Cada valor é considerado como uma chave de dicionário, que armazenará o número de ocorrências da palavra no texto. Quando uma palavra é encontrada pela primeira vez, cria-se uma entrada no dicionario usando a palavra como chave com o valor 1. A cada nova ocorrência, o valor é incrementado.

let texto = "Olá, meu nome é Franco! Lorem ipsum dolor sit amet consectetur adipiscing elit Etiam eget ligula eu lectus lobortis condimentum Aliquam nonummy auctor massa Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas Nulla at risus Quisque purus magna auctor et sagittis ac posuere eu lectus Nam mattis felis ut adipiscing"
let delimitador = " "
let palavras = texto.split(delimitador)

let contagem_palavras = new Map()
for (palavra of palavras) {
    let palavra_minusculas = palavra.toLowerCase()
    if (contagem_palavras.has(palavra_minusculas)) {
        contagem_palavras.set(palavra_minusculas, contagem_palavras.get(palavra_minusculas) + 1)
    } else {
        contagem_palavras.set(palavra_minusculas, 1)
    }
}

console.log("Total de palavras: ", palavras.length)
console.log("Total de palavras únicas: ", contagem_palavras.size)
console.log("Total de ocorrências para cada palavra:")
for (let [palavra, ocorrencias] of contagem_palavras) {
    console.log(palavra, ": ", ocorrencias)
}

texto = "Olá, meu nome é Franco! Lorem ipsum dolor sit amet consectetur adipiscing elit Etiam eget ligula eu lectus lobortis condimentum Aliquam nonummy auctor massa Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas Nulla at risus Quisque purus magna auctor et sagittis ac posuere eu lectus Nam mattis felis ut adipiscing"
delimitador = " "
palavras = texto.split(delimitador)

contagem_palavras = {}
for palavra in palavras:
    palavra_minusculas = palavra.lower()
    if (palavra_minusculas in contagem_palavras):
        contagem_palavras[palavra_minusculas] += 1
    else:
        contagem_palavras[palavra_minusculas] = 1

print("Total de palavras: ", len(palavras))
print("Total de palavras únicas: ", len(contagem_palavras))
print("Total de ocorrências para cada palavra:")
for palavra in contagem_palavras:
    ocorrencias = contagem_palavras[palavra]
    print(palavra, ": ", ocorrencias)

function escreva_vetor(vetor)
    if (vetor == nil) then
        return
    end

    local tamanho = #vetor
    io.write("[")
    for indice = 1, tamanho do
        io.write("\"" .. vetor[indice] .. "\"")
        if (indice < tamanho) then
            io.write(", ")
        end
    end
    print("]")
end

function split(cadeia_caracteres, delimitador)
    delimitador = delimitador or " "
    local resultado = {}
    local tamanho = #cadeia_caracteres
    local inicio = 1
    while (inicio <= tamanho) do
        local fim, proximo = string.find(cadeia_caracteres, delimitador, inicio, true)
        if (fim ~= nil) then
            table.insert(resultado, string.sub(cadeia_caracteres, inicio, fim - 1))
            inicio = proximo + 1
        else
            table.insert(resultado, string.sub(cadeia_caracteres, inicio))
            inicio = tamanho + 1
        end
    end

    if (string.sub(cadeia_caracteres, -#delimitador) == delimitador) then
        table.insert(resultado, "")
    end

    return resultado
end

function tamanho_tabela(tabela)
    local tamanho = 0
    for _ in pairs(tabela) do
        tamanho = tamanho + 1
    end

    return tamanho
end

local texto = "Olá, meu nome é Franco! Lorem ipsum dolor sit amet consectetur adipiscing elit Etiam eget ligula eu lectus lobortis condimentum Aliquam nonummy auctor massa Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas Nulla at risus Quisque purus magna auctor et sagittis ac posuere eu lectus Nam mattis felis ut adipiscing"
local delimitador = " "
local palavras = split(texto, delimitador)

local contagem_palavras = {}
for _, palavra in ipairs(palavras) do
    local palavra_minusculas = string.lower(palavra)
    if (palavras[palavra_minusculas] ~= nil) then
        contagem_palavras[palavra_minusculas] = contagem_palavras[palavra_minusculas] + 1
    else
        contagem_palavras[palavra_minusculas] = 1
    end
end

print("Total de palavras: ", #palavras)
print("Total de palavras únicas: ", tamanho_tabela(contagem_palavras))
print("Total de ocorrências para cada palavra:")
for palavra, ocorrencias in pairs(contagem_palavras) do
    print(palavra, ": ", ocorrencias)
end

extends Node

func _ready():
    var texto = "Olá, meu nome é Franco! Lorem ipsum dolor sit amet consectetur adipiscing elit Etiam eget ligula eu lectus lobortis condimentum Aliquam nonummy auctor massa Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas Nulla at risus Quisque purus magna auctor et sagittis ac posuere eu lectus Nam mattis felis ut adipiscing"
    var delimitador = " "
    var palavras = texto.split(delimitador)

    var contagem_palavras = {}
    for palavra in palavras:
        var palavra_minusculas = palavra.to_lower()
        if (palavra_minusculas in contagem_palavras):
            contagem_palavras[palavra_minusculas] += 1
        else:
            contagem_palavras[palavra_minusculas] = 1

    print("Total de palavras: ", len(palavras))
    print("Total de palavras únicas: ", len(contagem_palavras))
    print("Total de ocorrências para cada palavra:")
    for palavra in contagem_palavras:
        var ocorrencias = contagem_palavras[palavra]
        print(palavra, ": ", ocorrencias)

A implementação em JavaScript usa Map ao invés de JavaScript Object para utilizar o atributo size para a contagem de termos únicos.

Para sofisticar a solução, poder-se-ia ignorar símbolos para pontuação e outros caracteres irrelevantes. Como é possível observar, os termos Olá, e Franco! são considerados como palavras, porque a separação de valores considerou apenas espaços. Uma possibilidade é usar uma substituição para remover os caracteres. Isso também pode ser feito usando expressões regulares.

Além disso, a solução poderia considerar outros delimitadores além de espaços, como, por exemplo, quebras de linhas.

A propósito, as frases usadas no texto são chamada de lorem ipsum, comumente usadas como placeholders em editoração de texto, design gráfico, e Web design. O conteúdo foi extraído do link anterior para a Wikipédia.

Tabela de Pesquisa (Lookup Table)

Toda operação em programação possui um custo. Algumas são computacionalmente caras e lentas, outras são rápidas e baratas. Uma técnica de otimização é calcular resultados de operações caras e armazená-las em variáveis ou coleções.

Uma técnica que pode ser usada para isso é chamada de tabela de pesquisa (ou tabela de consulta), mais conhecida pelo termo em Inglês lookup table. Os resultados de uma tabela de pesquisa podem ser pré-calculados ou calculados antes do primeiro uso (uma estratégia chamada de lazy ou preguiçosa). A contrapartida é um maior consumo de memória em troca de menos operações para realização de cálculos.

Como exemplo, pode-se considerar uma tabela trigonométrica para o seno de um ângulo. Os valores para o seno de um ângulo podem ser pré-calculados e armazenados em uma tabela. Por exemplo, a tabela poderia fornecer valores de senos variando de 1° em 1°, começando em 0° até 360°.

Para converter um ângulo de graus para radianos, pode-se usar a fórmula:

Sendo um ângulo em graus (número real) e a constante com valor aproximado 3,141592.

function grau_para_radiano(angulo_graus) {
    const fator_conversao = Math.PI / 180.0

    return (angulo_graus * fator_conversao)
}

let tabela_seno_graus = []
for (let angulo = 0; angulo <= 360; ++angulo) {
    tabela_seno_graus.push(Math.sin(grau_para_radiano(angulo)))
}

console.log(tabela_seno_graus[0])
console.log(tabela_seno_graus[90])
console.log(tabela_seno_graus[180])
console.log(tabela_seno_graus[270])
console.log(tabela_seno_graus[360])

import math

def grau_para_radiano(angulo_graus):
    fator_conversao = math.pi / 180.0

    return (angulo_graus * fator_conversao)

tabela_seno_graus = []
for angulo in range(361):
    tabela_seno_graus.append(math.sin(grau_para_radiano(angulo)))

print(tabela_seno_graus[0])
print(tabela_seno_graus[90])
print(tabela_seno_graus[180])
print(tabela_seno_graus[270])
print(tabela_seno_graus[360])

function grau_para_radiano(angulo_graus)
    local fator_conversao = math.pi / 180.0

    return (angulo_graus * fator_conversao)
end

local tabela_seno_graus = {}
for angulo = 0, 360 do
    table.insert(tabela_seno_graus, math.sin(grau_para_radiano(angulo)))
end

print(tabela_seno_graus[0])
print(tabela_seno_graus[90])
print(tabela_seno_graus[180])
print(tabela_seno_graus[270])
print(tabela_seno_graus[360])

extends Node

func grau_para_radiano(angulo_graus):
    var fator_conversao = PI / 180.0

    return (angulo_graus * fator_conversao)

func _ready():
    var tabela_seno_graus = []
    for angulo in range(361):
        tabela_seno_graus.append(sin(grau_para_radiano(angulo)))

    print(tabela_seno_graus[0])
    print(tabela_seno_graus[90])
    print(tabela_seno_graus[180])
    print(tabela_seno_graus[270])
    print(tabela_seno_graus[360])

Após calculados, pode-se consultar o valor de seno de ângulos inteiros por meio do índice correspondente ao ângulo em graus na tabela tabela_seno_graus. Por exemplo, tabela_seno_graus[90] obtém o seno para o ângulo reto (90 graus).

No caso, a tabela está armazenada em um vetor. Contudo, ela poderia estar armazenada em outra estrutura de dados, como um dicionário. Assim, pode-se escolher a estrutura de dados mais apropriada para cada situação.

Tabelas de pesquisa são usadas com freqüência em uma técnica chamada programação dinâmica (dynamic programming), que usa resultados anteriores para calcular os próximos.

Biologia: Código Genético, Códons e Aminoácidos

Com mais recursos para manipulação de cadeias de caracteres, pode-se começar a resolver problemas de outras disciplinas e domínios. Por exemplo, de Biologia.

No código genético de seres vivos, uma seqüência de três bases nitrogenadas formam um códon. Cada códon corresponde a um aminoácido, conforme apresentado no link para códon.

Com uma seqüencia de bases nitrogenadas, pode-se codificar aminoácidos. O programa a seguir mapeia uma seqüência de códons em aminoácidos, seguindo a tabela do link. As tabelas geradas mapeiam colunas, depois linhas.

A solução é um pouco longa por causa da tabela, mas é simples. Uma seqüência válida de códons precisa:

Ter uma quantidade de bases nitrogenadas que seja múltiplo de 3;
Começar por um códon de início;
Terminar com um códon de parada;
Ter cada um dos códons válidos, isto é, pertencentes à tabela.

O programa é uma transcrição das condições anteriores. Ele analisa o tamanho, verifica o códon inicial, verifica o códon final. Na seqüência, itera-se de três em três bases para extrair o próximo códon, verifica-se se ele é válido e, caso seja, escreve-se o aminoácido correspondente.

let tabela_codons = {
    "UUU": "Fenilalanina",
    "UUC": "Fenilalanina",
    "UUA": "Leucina",
    "UUG": "Leucina",
    "CUU": "Leucina",
    "CUC": "Leucina",
    "CUA": "Leucina",
    "CUG": "Leucina",
    "AUU": "Isoleucina",
    "AUC": "Isoleucina",
    "AUA": "Isoleucina",
    "AUG": "Metionina",
    "GUU": "Valina",
    "GUC": "Valina",
    "GUA": "Valina",
    "GUG": "Valina",
    "UCU": "Serina",
    "UCC": "Serina",
    "UCA": "Serina",
    "UCG": "Serina",
    "CCU": "Prolina",
    "CCC": "Prolina",
    "CCA": "Prolina",
    "CCG": "Prolina",
    "ACU": "Treonina",
    "ACC": "Treonina",
    "ACA": "Treonina",
    "ACG": "Treonina",
    "GCU": "Alanina",
    "GCC": "Alanina",
    "GCA": "Alanina",
    "GCG": "Alanina",
    "UAU": "Tirosina",
    "UAC": "Tirosina",
    "UAA": "STOP",
    "UAG": "STOP",
    "CAU": "Histidina",
    "CAC": "Histidina",
    "CAA": "Glutamina",
    "CAG": "Glutamina",
    "AAU": "Asparagina",
    "AAC": "Asparagina",
    "AAA": "Lisina",
    "AAG": "Lisina",
    "GAU": "Ácido aspártico",
    "GAC": "Ácido aspártico",
    "GAA": "Ácido glutâmico",
    "GAG": "Ácido glutâmico",
    "UGU": "Cisteína",
    "UGC": "Cisteína",
    "UGA": "STOP",
    "UGG": "Triptofano",
    "CGU": "Arginina",
    "CGC": "Arginina",
    "CGA": "Arginina",
    "CGG": "Arginina",
    "AGU": "Serina",
    "AGC": "Serina",
    "AGA": "Arginina",
    "AGG": "Arginina",
    "GGU": "Glicina",
    "GGC": "Glicina",
    "GGA": "Glicina",
    "GGG": "Glicina"
}

let codons_inicio = ["UUG", "AUG", "GUG"]
let codons_parada = ["UAA", "UAG", "UGA"]

let sequencia_codons = "UUGUUUUUCUUAUUGCUUCUCCUACUGAUUAUCAUAAUGGUUGUCGUAGUGUCUUCCUCAUCGCCUCCCCCACCGACUACCACAACGGCUGCCGCAGCGUAUUACCAUCACCAACAGAAUAACAAAAAGGAUGACGAAGAGUGUUGCUGGCGUCGCCGACGGAGUAGCAGAAGGGGUGGCGGAGGGUGA"
sequencia_codons = sequencia_codons.toUpperCase()
let tamanho = sequencia_codons.length
if (tamanho % 3 !== 0) {
    console.log("Número inválido de bases nitrogenadas")
} else {
    let numero_codons = tamanho / 3
    let codon_inicial = sequencia_codons.slice(0, 3)
    let codon_final = sequencia_codons.slice(tamanho - 3, tamanho)
    if (!codons_inicio.includes(codon_inicial)) {
        console.log("Códon inicial inválido:", codon_inicial)
    } else if (!codons_parada.includes(codon_final)) {
        console.log("Códon final inválido: ", codon_final)
    } else {
        for (let indice_codon = 0; indice_codon < tamanho; indice_codon += 3) {
            let codon = sequencia_codons.slice(indice_codon, indice_codon + 3)
            if (!tabela_codons.hasOwnProperty(codon)) {
                console.log("Códon inválido: ", codon)
            } else {
                console.log(tabela_codons[codon])
            }
        }
    }
}

tabela_codons = {
    "UUU": "Fenilalanina",
    "UUC": "Fenilalanina",
    "UUA": "Leucina",
    "UUG": "Leucina",
    "CUU": "Leucina",
    "CUC": "Leucina",
    "CUA": "Leucina",
    "CUG": "Leucina",
    "AUU": "Isoleucina",
    "AUC": "Isoleucina",
    "AUA": "Isoleucina",
    "AUG": "Metionina",
    "GUU": "Valina",
    "GUC": "Valina",
    "GUA": "Valina",
    "GUG": "Valina",
    "UCU": "Serina",
    "UCC": "Serina",
    "UCA": "Serina",
    "UCG": "Serina",
    "CCU": "Prolina",
    "CCC": "Prolina",
    "CCA": "Prolina",
    "CCG": "Prolina",
    "ACU": "Treonina",
    "ACC": "Treonina",
    "ACA": "Treonina",
    "ACG": "Treonina",
    "GCU": "Alanina",
    "GCC": "Alanina",
    "GCA": "Alanina",
    "GCG": "Alanina",
    "UAU": "Tirosina",
    "UAC": "Tirosina",
    "UAA": "STOP",
    "UAG": "STOP",
    "CAU": "Histidina",
    "CAC": "Histidina",
    "CAA": "Glutamina",
    "CAG": "Glutamina",
    "AAU": "Asparagina",
    "AAC": "Asparagina",
    "AAA": "Lisina",
    "AAG": "Lisina",
    "GAU": "Ácido aspártico",
    "GAC": "Ácido aspártico",
    "GAA": "Ácido glutâmico",
    "GAG": "Ácido glutâmico",
    "UGU": "Cisteína",
    "UGC": "Cisteína",
    "UGA": "STOP",
    "UGG": "Triptofano",
    "CGU": "Arginina",
    "CGC": "Arginina",
    "CGA": "Arginina",
    "CGG": "Arginina",
    "AGU": "Serina",
    "AGC": "Serina",
    "AGA": "Arginina",
    "AGG": "Arginina",
    "GGU": "Glicina",
    "GGC": "Glicina",
    "GGA": "Glicina",
    "GGG": "Glicina"
}

codons_inicio = ["UUG", "AUG", "GUG"]
codons_parada = ["UAA", "UAG", "UGA"]

sequencia_codons = "UUGUUUUUCUUAUUGCUUCUCCUACUGAUUAUCAUAAUGGUUGUCGUAGUGUCUUCCUCAUCGCCUCCCCCACCGACUACCACAACGGCUGCCGCAGCGUAUUACCAUCACCAACAGAAUAACAAAAAGGAUGACGAAGAGUGUUGCUGGCGUCGCCGACGGAGUAGCAGAAGGGGUGGCGGAGGGUGA"
sequencia_codons = sequencia_codons.upper()
tamanho = len(sequencia_codons)
if (tamanho % 3 != 0):
    print("Número inválido de bases nitrogenadas")
else:
    numero_codons = tamanho // 3
    codon_inicial = sequencia_codons[0:3]
    codon_final = sequencia_codons[tamanho - 3 : tamanho]
    if (not codon_inicial in codons_inicio):
        print("Códon inicial inválido:", codon_inicial)
    elif (not codon_final in codons_parada):
        print("Códon final inválido: ", codon_final)
    else:
        for indice_codon in range(0, tamanho, 3):
            codon = sequencia_codons[indice_codon: indice_codon + 3]
            if (not codon in tabela_codons):
                print("Códon inválido: ", codon)
            else:
                print(tabela_codons[codon])

function busca_sequencial(vetor, valor)
    for indice, valor_atual in ipairs(vetor) do
        if (valor == valor_atual) then
            return indice
        end
    end

    return -1
end

local tabela_codons = {
    UUU = "Fenilalanina",
    UUC = "Fenilalanina",
    UUA = "Leucina",
    UUG = "Leucina",
    CUU = "Leucina",
    CUC = "Leucina",
    CUA = "Leucina",
    CUG = "Leucina",
    AUU = "Isoleucina",
    AUC = "Isoleucina",
    AUA = "Isoleucina",
    AUG = "Metionina",
    GUU = "Valina",
    GUC = "Valina",
    GUA = "Valina",
    GUG = "Valina",
    UCU = "Serina",
    UCC = "Serina",
    UCA = "Serina",
    UCG = "Serina",
    CCU = "Prolina",
    CCC = "Prolina",
    CCA = "Prolina",
    CCG = "Prolina",
    ACU = "Treonina",
    ACC = "Treonina",
    ACA = "Treonina",
    ACG = "Treonina",
    GCU = "Alanina",
    GCC = "Alanina",
    GCA = "Alanina",
    GCG = "Alanina",
    UAU = "Tirosina",
    UAC = "Tirosina",
    UAA = "STOP",
    UAG = "STOP",
    CAU = "Histidina",
    CAC = "Histidina",
    CAA = "Glutamina",
    CAG = "Glutamina",
    AAU = "Asparagina",
    AAC = "Asparagina",
    AAA = "Lisina",
    AAG = "Lisina",
    GAU = "Ácido aspártico",
    GAC = "Ácido aspártico",
    GAA = "Ácido glutâmico",
    GAG = "Ácido glutâmico",
    UGU = "Cisteína",
    UGC = "Cisteína",
    UGA = "STOP",
    UGG = "Triptofano",
    CGU = "Arginina",
    CGC = "Arginina",
    CGA = "Arginina",
    CGG = "Arginina",
    AGU = "Serina",
    AGC = "Serina",
    AGA = "Arginina",
    AGG = "Arginina",
    GGU = "Glicina",
    GGC = "Glicina",
    GGA = "Glicina",
    GGG = "Glicina"
}

local codons_inicio = {"UUG", "AUG", "GUG"}
local codons_parada = {"UAA", "UAG", "UGA"}

local sequencia_codons = "UUGUUUUUCUUAUUGCUUCUCCUACUGAUUAUCAUAAUGGUUGUCGUAGUGUCUUCCUCAUCGCCUCCCCCACCGACUACCACAACGGCUGCCGCAGCGUAUUACCAUCACCAACAGAAUAACAAAAAGGAUGACGAAGAGUGUUGCUGGCGUCGCCGACGGAGUAGCAGAAGGGGUGGCGGAGGGUGA"
sequencia_codons = string.upper(sequencia_codons)
local tamanho = #sequencia_codons
if (tamanho % 3 ~= 0) then
    print("Número inválido de bases nitrogenadas")
else
    local numero_codons = tamanho / 3
    local codon_inicial = string.sub(sequencia_codons, 1, 3)
    local codon_final = string.sub(sequencia_codons, tamanho - 2)
    if (busca_sequencial(codons_inicio, codon_inicial) == -1) then
        print("Códon inicial inválido:", codon_inicial)
    elseif (busca_sequencial(codons_parada, codon_final) == -1) then
        print("Códon final inválido: ", codon_final)
    else
        for indice_codon = 1, tamanho, 3 do
            local codon = string.sub(sequencia_codons, indice_codon, indice_codon + 2)
            if (tabela_codons[codon] == nil) then
                print("Códon inválido: ", codon)
            else
                print(tabela_codons[codon])
            end
        end
    end
end

extends Node

func _ready():
    var tabela_codons = {
        "UUU": "Fenilalanina",
        "UUC": "Fenilalanina",
        "UUA": "Leucina",
        "UUG": "Leucina",
        "CUU": "Leucina",
        "CUC": "Leucina",
        "CUA": "Leucina",
        "CUG": "Leucina",
        "AUU": "Isoleucina",
        "AUC": "Isoleucina",
        "AUA": "Isoleucina",
        "AUG": "Metionina",
        "GUU": "Valina",
        "GUC": "Valina",
        "GUA": "Valina",
        "GUG": "Valina",
        "UCU": "Serina",
        "UCC": "Serina",
        "UCA": "Serina",
        "UCG": "Serina",
        "CCU": "Prolina",
        "CCC": "Prolina",
        "CCA": "Prolina",
        "CCG": "Prolina",
        "ACU": "Treonina",
        "ACC": "Treonina",
        "ACA": "Treonina",
        "ACG": "Treonina",
        "GCU": "Alanina",
        "GCC": "Alanina",
        "GCA": "Alanina",
        "GCG": "Alanina",
        "UAU": "Tirosina",
        "UAC": "Tirosina",
        "UAA": "STOP",
        "UAG": "STOP",
        "CAU": "Histidina",
        "CAC": "Histidina",
        "CAA": "Glutamina",
        "CAG": "Glutamina",
        "AAU": "Asparagina",
        "AAC": "Asparagina",
        "AAA": "Lisina",
        "AAG": "Lisina",
        "GAU": "Ácido aspártico",
        "GAC": "Ácido aspártico",
        "GAA": "Ácido glutâmico",
        "GAG": "Ácido glutâmico",
        "UGU": "Cisteína",
        "UGC": "Cisteína",
        "UGA": "STOP",
        "UGG": "Triptofano",
        "CGU": "Arginina",
        "CGC": "Arginina",
        "CGA": "Arginina",
        "CGG": "Arginina",
        "AGU": "Serina",
        "AGC": "Serina",
        "AGA": "Arginina",
        "AGG": "Arginina",
        "GGU": "Glicina",
        "GGC": "Glicina",
        "GGA": "Glicina",
        "GGG": "Glicina"
    }

    var codons_inicio = ["UUG", "AUG", "GUG"]
    var codons_parada = ["UAA", "UAG", "UGA"]

    var sequencia_codons = "UUGUUUUUCUUAUUGCUUCUCCUACUGAUUAUCAUAAUGGUUGUCGUAGUGUCUUCCUCAUCGCCUCCCCCACCGACUACCACAACGGCUGCCGCAGCGUAUUACCAUCACCAACAGAAUAACAAAAAGGAUGACGAAGAGUGUUGCUGGCGUCGCCGACGGAGUAGCAGAAGGGGUGGCGGAGGGUGA"
    sequencia_codons = sequencia_codons.to_upper()
    var tamanho = len(sequencia_codons)
    if (tamanho % 3 != 0):
        print("Número inválido de bases nitrogenadas")
    else:
        var numero_codons = tamanho / 3
        var codon_inicial = sequencia_codons.substr(0, 3)
        var codon_final = sequencia_codons.substr(tamanho - 3, 3)
        if (not codon_inicial in codons_inicio):
            print("Códon inicial inválido:", codon_inicial)
        elif (not codon_final in codons_parada):
            print("Códon final inválido: ", codon_final)
        else:
            for indice_codon in range(0, tamanho, 3):
                var codon = sequencia_codons.substr(indice_codon, 3)
                if (not codon in tabela_codons):
                    print("Códon inválido: ", codon)
                else:
                    print(tabela_codons[codon])

A seqüência de códons usada em sequencia_codons combina um possível códon inicial com todos os códons que não são de parada, seguido por um códon de parada.

Existem outras formas de resolver o problema. Dependendo do objetivo e da operação genética a ser realizada, poderia ser interessante, por exemplo, montar um vetor como todas as seqüências de bases para manipulá-las posteriormente. Outra opção é remover tabela_codons e implementá-la como uma seqüência de estruturas condicionais para a identificação de um códon.

Novos Itens para Seu Inventário

Ferramentas:

diff;
Placeholders e lorem ipsum;
Ferramentas para construção de expressões regulares.

Habilidades:

Uso de coleções: vetores e dicionários;
Passagem de parâmetros para subrotinas por referência.

Conceitos:

Coleções;
Chave ou identificador;
Inserção;
Remoção;
Busca e substituição;
Busca seqüencial;
Busca binária;
Ordenação e embaralhamento;
Vetores;
Matrizes;
Listas;
Dicionários;
Pilhas, empilhar e desempilhar;
Filas, enfileirar e desenfileirar;
Conjuntos;
Tamanho ou comprimento;
Tamanho máximo ou capacidade;
Índice ou deslocamento;
Iteradores;
Falha de segmentação;
Seleção ou filtro;
Compartilhamento de memória;
Cópia rasa;
Cópia profunda;
Referências;
Vetores paralelos;
Substring;
Tokenização e split;
Expressões regulares;
Programação funcional;
Operações funcionais: map, for each, reduce (fold ou accumulate), filter;
Tabela de pesquisa.

Recursos de programação:

Coleções e estruturas de dados:
- Vetores, listas e matrizes;
- Dicionários e tabelas;
- Pilhas;
- Filas;
- Conjuntos.
Iteradores;
Ordenação e embaralhamento;
Programação em estilo funcional.

Pratique

A implementação de subrotinas para cada operação descrita e exemplificada neste tópico é um bom exercício para a prática.

Inicialize um vetor com 100 posições com o valor 0.
Inicialize um vetor com 1000 posições com valores crescentes: 1, 2, 3, ..., 1000. Escreva todos os valores do vetor. Em seguida, escreva todos os valores do vetor em ordem reversa (1000, 999, 998, ..., 1).
Crie um vetor com tamanho 5. Leia dados de entrada para inicializá-lo. Após a leitura de todos os dados lidos, escreva todos os valores do vetor. Indique também o maior e o menor valor armazenado.
Crie um vetor que armazene uma lista de compras. Insira novos valores (nomes de itens) até a entrada do valor fim (fim não deve ser armazenado). Após a leitura de fim, escreva todos os itens lidos.
Utilize a técnica de vetores paralelos para melhorar o exercício anterior. Crie um vetor adicional para armazenar a quantidade de cada item da lista.
Crie um vetor com 100 números aleatórios, variando de 1 até 1000. Após a inicialização de todo o vetor, escreva os valores. Ordene o vetor e escreva novamente todos os valores.
Escreva vetor de 100000 posições, iniciando cada posição com o valor do seu índice. Essa inicialização garantirá que todos os valores serão únicos. Embaralhe o vetor. Escolha um índice válido do vetor aleatório e armazene o valor. Compare o número de buscas necessário para encontrar o vetor usando busca binária e busca seqüêncial. Dica: você pode alterar o algoritmo de busca binária para adicionar um contador de iterações.
Escreva um programa que defina um vetor que possa armazenar, no máximo, 5 valores. O vetor pode ter 0, 1, 2, 3, 4 ou 5 valores armazenados, mas não mais de 5. Dica: você pode criar uma variável chamada tamanho_maximo e compará-la com o tamanho atual antes de adicionar novos valores.
Escreva um programa que leia 5 valores como entrada. Realize o somatório dos valores e escreva o resultado.
Quando é necessário usar um vetor? Quando basta uma estrutura de repetição ao invés de um vetor? Para responder a pergunta, você pode pensar em quando e quantas vezes os valores serão usados.
Crie um vetor que armazene cadeias de caracteres. Crie um segundo vetor que armazene apenas as cadeias de caracteres do primeiro vetor que tenham 3 ou mais caracteres. Escreva cada uma delas com os respectivos tamanhos.
Crie um sistema que calcule médias de estudantes em uma sala de aula. O número de estudantes é de sua escolha. Para cada estudante, deve-se armazenar valores para nome e três notas. Além disso, o sistema deve informar, para cada estudante:
- Estudante aprovado: média aritmética das três notas maior que 7.0;
- Estudante em recuperação: média aritmética das três notas entre 4,5 (inclusive) e 7,0 (inclusive);
- Estudante reprovado: média aritmética das três notas menor que 4,5.
No geral, o sistema também deve informar:
- Qual o nome estudante com melhor média;
- Qual a nota mais baixa do estudante com pior média.
Crie um sistema que leia uma cadeia de caracteres (por exemplo, uma frase). Em seguida, leia uma palavra qualquer. Informe se a palavra lida existe na cadeia de caracteres. Apresente dois resultados: um considerando diferenças de letras minúsculas e maiúsculas; outro desconsiderando diferenças.
Escreva um programa que some valores de dois vetores em um terceiro. A soma de dois vetores é definida como , para todo índice do vetor. Por exemplo, [1, 2, 3] + [4, 5, 6] é igual a [5, 7, 9]. Genericamente, sendo sendo , , , números (inteiros ou reais):
Escreva um programa que some duas matrizes e armazene os resultados em uma terceira. Por exemplo, sendo , , , , , , e números (inteiros ou reais):
Escreva um programa que armazene números inteiros em uma matriz com 3 linhas e 3 colunas. Forneça:
1. O maior valor armazenado na matriz;
2. O menor valor armazenado na matriz;
3. O maior valor armazenado em cada linha da matriz;
4. O menor valor armazenado em cada linha da matriz;
5. O maior valor armazenado em cada coluna da matriz;
6. O menor valor armazenado em cada coluna da matriz;
7. A soma de todos os seis valores determinados nos itens anteriores.
Escreva um programa que leia um texto como cadeia de caracteres. Em seguida, separe cada linha do texto em um vetor. Dica: você pode considerar o delimitador como uma quebra de linhas (\n).
Repita o exercícios anterior. Após criar o vetor com cada linha, escreva o texto original da última linha para a primeira. Em seguida, construa uma cadeia de caracteres com o texto da última linha para a primeira. Escreva o resultado.
Escreva um programa para comparar vetores. Dois vetores são iguais se cada posição de cada valor armazena o mesmo valor. Em outras palavras, para todas as posições do vetor e e devem ter o mesmo tamanho. Dica: o operador de igualdade (==) normalmente não verifica igualdade de vetores em toda linguagem de programação (ele normalmente compara endereços das referências), mas você pode comparar cada um dos valores usando uma estrutura de repetição.
Escreva um programa para comparar matrizes. Duas matrizes são iguais se os elementos de cada combinação de linha e coluna da primeira forem iguais à linha e coluna correspondente da segunda. O número de linhas e colunas das duas matrizes também deve ser igual.

Considere a seguinte relação de receitas e despesas de uma loja fictícia por mês. Escreva um programa que:

Escreva o lucro ou prejuízo mensal da empresa. Para calcular o lucro ou prejuízo, basta subtrair o valor de despesas do total de receitas de mês (isto é, receita - despesa). Um valor positivo significa lucro; um valor negativo significa prejuízo;
Determine o mês de melhor lucro e o de maior prejuízo;
O lucro (ou prejuízo) líqüido da loja do ano.

Mês	Receita	Despesa
1	1640.19	1703.98
2	2091.40	1912.48
3	1649.24	1738.39
4	1801.66	1859.99
5	1933.81	1720.56
6	1596.79	1879.82
7	1832.66	1592.29
8	1791.95	1785.40
9	1535.72	1744.74
10	2042.85	1871.51
11	1626.09	1560.18
12	2052.55	1596.51

Crie um programa que possa traduzir números de um até dez em português para inglês e vice-versa. O programa também pode converter um dos valores em qualquer um dos idiomas para número arábico ou romano.
Arábico Romano Português Inglês
1 I Um One
2 II Dois Two
3 III Três Three
4 IV Quatro Four
5 V Cinco Five
6 VI Seis Six
7 VII Sete Seven
8 VIII Oito Eight
9 IX Nove Nine
10 X Dez Ten
Leia uma seqüência de valores e escreva o resultado nas representações correspondentes. Exemplos de entrada e saída:

Arábico	Romano	Português	Inglês
1	I	Um	One
2	II	Dois	Two
3	III	Três	Three
4	IV	Quatro	Four
5	V	Cinco	Five
6	VI	Seis	Six
7	VII	Sete	Seven
8	VIII	Oito	Eight
9	IX	Nove	Nine
10	X	Dez	Ten

Entrada: 7. Saída esperada:

Romano: VII
Português: Sete
Inglês: Seven

Entrada: 1 2 3. Saída esperada:

Romano: I II III
Português: Um Dois Três
Inglês: One Two Three

Entrada: VII VII VII. Saída esperada:

Arábico: 7 7 7
Português: Sete Sete Sete
Inglês: Seven Seven Seven

Entrada: Nove Nove. Saída esperada:
```
Arábico: 9 9
Romano: IX IX
Nine Nine
```

Entrada: Ten Six. Saída esperada:

Arábico: 10 6
Romano: X VI
Português: Dez Seis

Crie um dicionário de sinônimos. Escolha palavras e sinônimos, escreve todas as palavras-chave definidas, e defina uma funcionalidade busca por palavra-chave. Dica: como cada chave pode ter um único valor, você pode armazenar os sinônimos como uma cadeia de caracteres com um delimitador ou como um vetor de cadeias de caracteres.
Crie vetores, matrizes e dicionários para praticar a criação e uso de memória compartilhada e de cópias rasas e profundas.
Crie um programa que leia um texto e uma palavra. O programa deve indicar quantas vezes a palavra escolhida aparece no texto.
Crie um dicionário com as seguintes chaves: nome, sobrenome, idade, gosta de programar. As chaves nome e sobrenome devem armazenar uma cadeia de caracteres. A chave idade deve armazenar um número (real ou inteiro, de sua preferência). A chave gosta de programar deve armazenar um valor lógico Verdadeiro, caso a pessoa goste de programar, ou Falso, caso contrário. Em seguida, crie um vetor de entradas do dicionário anterior com nomes de seus familiares, amigas e amigos. Cada posição do vetor armazenará dados de uma pessoa.
Por exemplo:
```
[
    {
        "nome": "Franco",
        "sobrenome": "Garcia",
        "idade": 99,
        "gosta de programar": True
    },
    {
        "nome": "Tyrannosaurus",
        "sobrenome": "rex",
        "idade": 66000000,
        "gosta de programar": False
    },
    {
        "nome": "Brontosaurus",
        "sobrenome": "excelsus",
        "idade": 66000000,
        "gosta de programar": False
    },
]
```
Tal uso de dicionários pode prover uma alternativa para a criação de tipos de dados compostos em linguagens que não forneçam recursos para criação de registros ou classes.
Modifique o exercício anterior para armazenar dados sobre dinossauros. Armazene dados como nome científico, nome popular, período, dieta (carnívora, herbívora, onívora) e um texto com curiosidades.
Se não gostar de dinossauros, você pode armazenar ingredientes de receitas e modo de preparo, montar um catálogo de músicas, livros ou filmes, ou um roteiro de exercícios.
Quaisquer que sejam seus interesses, computadores podem ajudar a coletar, organizar, gerenciar e processar dados.
Implemente o jogo da velha (tic-tac-toe). O jogo da velha possui um tabuleiro de três linhas e três colunas. Dois jogadores marcam símbolos no tabuleiro (normalmente X ou O). A primeira pessoa que conseguir uma seqüência de três símbolos iguais em uma linha, coluna ou diagonal vence o jogo. Caso as nove posições sejam marcadas sem um vencedor, a partida termina em empate.
Escreva um jogo de forca (hangman). No jogo de forca, a pessoa possui um número máximo de tentativas para adivinhar uma palavra. Em uma tentativa, a pessoa escolha uma letra. Se a letra constar na palavra, o jogo deve realçar todas as ocorrências da letra na palavra (além das demais letras adivinhadas corretamente em tentativas anteriores). Caso contrário, o jogo deve registrar o erro. A pessoa vence o jogo caso ela adivinhe todos os caracteres antes do limite máximo de tentativas.
Implemente um jogo de caça-palavras (word hunt). Em um caça-palavras, define-se um tabuleiro no qual a pessoa deve encontrar uma lista de palavras pré-definidas. As palavras podem aparecer na horizontal, vertical ou diagonal. Em algumas implementações, elas também podem aparecer em ordem reversa (de trás para frente). Dica: pode-se ser a jogada como uma combinação de índice de linha e de coluna.
Crie subrotinas para comparar se dois vetores, matrizes, cadeias de caracteres ou dicionários são iguais ou diferentes.

Próximos Passos

Vetores, cadeias de caracteres, dicionários e outras estruturas de dados permitiram expandir consideravelmente os conceitos e habilidades para programação de computadores.

Com este tópico, agora você pode resolver problemas com grandes quantidades de dados. Ao invés de declarar uma variável por valor, pode-se definir coleções para manipular vários dados em estruturas de repetição.

De fato, neste momento, você tem quase todo o potencial do computador a seu alcance. Os conceitos fundamentais que são válidos para praticamente todas as linguagens de programação estão quase no fim.

No próximo tópico, você poderá criar seus próprios tipos de dados como combinações de outros tipos existentes. A criação de tipos como registros (structs ou records) permitirá pensar em dados em nível mais alto, facilitando a criação de abstrações.

← Anterior:
Aprenda Programação: Estruturas de Repetição (Laços ou Loops)

Próximo:→
Aprenda Programação: Registros (Structs ou Records)

Aprenda Programação: Vetores, Cadeias de Caracteres, Coleções e Estruturas de Dados

.css-1u7q826{color:var(--theme-ui-colors-primary);-webkit-text-decoration:none;text-decoration:none;}.css-1u7q826:hover{-webkit-text-decoration:underline;text-decoration:underline;}.css-1u7q826:hover,.css-1u7q826:focus{-webkit-text-decoration:none;text-decoration:none;}Pré-Requisitos

Tipos de Dados Compostos e o Fim de Uma Era

Vetores (Arranjos ou Arrays) e Listas (Lists)

Vetores Versus Listas

Fluxogramas: Flowgorithm

Linguagens de Programação Visual: Scratch

Linguagens de Programação Textual: JavaScript, Python, Lua e GDScript

Operações e Técnicas Usando Vetores

Declaração e Inicialização

Inicialização para Poucos Valores

Lua e Vetores

Inserções, Remoções e Limpeza

Busca Seqüencial

Acumuladores

Seleção ou Filtro de Valores

Ordenação e Busca Binária

Cópia Rasa, Cópia Profunda e Memória Compartilhada

Vetores Paralelos (ou Structure of Arrays)

Matrizes (Matrices) e Vetores de Vetores

Ordem de Linhas e Ordem de Colunas

Matriz Como um Vetor

Cadeias de Caracteres (Strings)

Operações e Técnicas Usando Cadeias de Caracteres

Concatenação e Conversão de Tipos

Tamanho e Iteração

Conversão de Caixas

Comparações

Verificação de Valores

Extração de Substring

Busca por Substring

Busca e Substituição

Tokenização e Split

Expressões Regulares (Regex)

Dicionários (Dictionaries), Mapas (Maps) ou Tabelas (Tables)

Operações e Técnicas Usando Dicionários

Declaração e Inicialização

Diferentes Tipos para Chaves e Valores

Inserções, Remoções, Limpeza e Tamanho

Acesso a Valores e Iteração

Busca

Busca por Uma Chave e Verificação de Existência de Chave

Busca por um Valor Armazenado em Alguma Chave

Acumuladores

Seleção ou Filtro de Valores

Cópia Rasa, Cópia Profunda e Memória Compartilhada

Outras Estruturas de Dados

Pilhas (Stacks)

Filas (Queues)

Filas de Prioridade (Priority Queues)

Conjuntos (Sets)

Programação Funcional: Map, For Each, Reduce e Filter

Exemplos

Embaralhar Vetor e Sortear Valores

Estatísticas para Textos: Contagem de Palavras

Tabela de Pesquisa (Lookup Table)

Biologia: Código Genético, Códons e Aminoácidos

Novos Itens para Seu Inventário

Pratique

Próximos Passos

Pré-Requisitos