Arranjos

Arranjos (ou vetores, ou arrays) são sequências de elementos de um mesmo tipo, armazenados em posições contíguas de memória. Por causa da forma como os elementos são armazenados em um arranjo, o acesso a esses elementos é feito em tempo constante, ou seja, com complexidade $O(1)$.

Por questões de eficiência, é aconselhável que se use arranjos sempre que possível, especialmente em linguagens como C e C++. Nessas linguagens, arranjos são declarados com um tamanho fixo, e se for necessário adicionar mais um elemento a um arranjo que já está cheio, é necessário alocar espaço na memória para um novo arranjo do tamanho desejado e então copiar todos os elementos do arranjo antigo para o novo arranjo.

Em geral, arranjos são interessantes porque:

  • proporcionam acesso a um índice específico em tempo constante (complexidade $O(1)$);

  • são eficientes em termos de espaço, pois nenhum espaço é desperdiçado com o armazenamento de apontadores;

  • apresentam boa localidade de referência espacial ---percorrer um arranjo do começo ao fim é algo muito rápido, pois ao levar um elemento do arranjo da memória principal para a memória cache, existe uma boa chance de que os elementos vizinhos a ele (que serão percorridos no futuro) também sejam levados para a cache juntamente com ele.

Python possui arranjos com as mesmas características dos arranjos presentes em C e C++. Mas atenção: listas em Python não são arranjos no sentido estrito da palavra. Listas em Python são listas encadeadas, e como tal, elas podem armazenar elementos de tipos diferentes, que não necessariamente estão em posições contíguas de memória, e não possuem tamanho fixo.

Se quisermos usar arranjos como os de C e C++ em Python, precisamos importar o módulo array. Há várias funções disponíveis no módulo array. Para mais detalhes, digite help(array) no prompt do Python e veja a explicação dos demais métodos disponíveis nesse módulo.

É importante fazer esta distinção entre o funcionamento de listas e arranjos em Python, mas como nosso foco é nos algoritmos em si, usaremos listas para a maioria dos algoritmos que operam sobre arranjos. Tomaremos cuidado de mencionar possíveis violações no uso de listas em relação a arranjos. Além disso, nos exemplos abaixo, sempre que fizermos menção a uma lista de elementos, estamos nos referindo a um arranjo de elementos.

Em geral, os algoritmos que envolvem arranjos exigem que você saiba percorrer um arranjo (usando um for, por exemplo) e que você saiba realizar operações diversas sobre os elementos desse arranjo.

No restante desta seção, daremos exemplos (resolvidos) detalhados sobre problemas típicos envolvendo arranjos.

Exemplo: Contar elementos duplicados

Suponha que lhe seja fornecida uma lista de números inteiros positivos e um número $m$. Você pode assumir que todos os números na lista estão no intervalo $[0, m]$. Sua tarefa é dizer quais números aparecem duplicados na lista.

Como este é o primeiro algoritmo que estamos desenvolvendo, precisamos de alguns esclarecimentos preliminares. Note que a descrição da tarefa nos diz qual entrada nosso algoritmo receberá: uma lista de números inteiros positivos. Outro ponto importante é a saída do algoritmo: quais números aparecem duplicados na lista.

Agora precisamos pensar em como resolver o problema.

Quando estamos lidando com arranjos e listas, uma pergunta importante a se fazer é: O que devemos fazer se a lista de entrada estiver vazia? No nosso caso, é razoável assumir que se a lista estiver vazia devemos retornar uma lista vazia, pois não há elementos repetidos na lista de entrada.

O próximo passo é pensar em como resolver o problema se a lista possuir um ou mais elementos. Uma possível solução é percorrermos a lista uma vez para cada elemento presente e verificarmos se o elemento em questão aparece novamente na lista. Este raciocínio nos leva à seguinte solução.

def encontra_elementos_duplicados(lista, m):
    """
    Imprime os números que aparecem mais de uma vez na lista de entrada.
    É garantido que todos os números na lista de entrada estão no intervalo [0, m].
    """
    # Retorna zero se a lista de entrada estiver vazia.
    if not lista:
        return []

    # Procura por elementos repetidos na lista.
    duplicatas = []
    for i in range(len(lista)):
        for j in range(i + 1, len(lista)):
            if lista[i] == lista[j]:
                duplicatas.append(lista[j])

    # A saída do algoritmo é a lista de elementos repetidos.
    return duplicatas

elementos_duplicados = encontra_elementos_duplicados([1, 1, 20, 3, 3, 80, 7, 2, 25, 99, 75, 80], 100)
print("Elementos duplicados: ", elementos_duplicados)
Elementos duplicados:  [1, 3, 80]

Neste ponto, convém fazer algumas observações sobre a solução acima:

  • Nós usamos o comando if not lista para testar se a lista de entrada está vazia. Poderíamos ter usado o comando if len(lista) == 0 que teríamos obtido o mesmo resultado. Entretanto, o comando if not lista segue mais o estilo Python de fazer as coisas. Em outras palavras, dizemos que o comando if not lista é mais pythonico.

  • Nossa solução não explora o fato de que os números na lista estão no intervalo $[0, m]$.

  • Nossa solução percorre a lista (ou parte dela) várias vezes. A complexidade assintótica do nosso algoritmo é $O(n^2)$, em que $n$ é o tamanho da lista.

Seria possível criarmos um algoritmo mais eficiente se levarmos em consideração o fato de que os números na lista de entrada estão no intervalo $[0, m]$? Perceba que a solução acima não usa esse fato. Ela ignora completamente que os números na lista de entrada estão no intervalo $[0, m]$. Nossa próxima solução usará essa informação para reduzir a complexidade assintótica do algoritmo de busca por elementos duplicados.

Se usarmos o fato de que os números estão no intervalo $[0, m]$, podemos criar uma lista auxiliar com a frequência dos valores na lista de entrada. Todas as vezes que encontrarmos um valor na lista na lista de entrada, incrementamos sua frequência na lista auxiliar. Havendo terminado de processar a lista de entrada, percorremos a lista auxiliar e vemos se algum dos elementos possui frequência maior que 1. Este raciocínio nos leva à seguinte solução.

def encontra_elementos_duplicados_frequencia(lista, m):
    """
    Imprime os números que aparecem mais de uma vez na lista de entrada.
    É garantido que todos os números na lista de entrada estão no intervalo [0, m].
    """
    # Retorna zero se a lista de entrada estiver vazia.
    if not lista:
        return []

    # Procura por elementos repetidos na lista.
    tabela_frequencia = [0] * m
    duplicatas = []
    for elemento in lista:
        tabela_frequencia[elemento] += 1
        if tabela_frequencia[elemento] > 1:
            duplicatas.append(elemento)

    # A saída do algoritmo é a lista de elementos repetidos.
    return duplicatas

elementos_duplicados = encontra_elementos_duplicados_frequencia([1, 1, 20, 3, 3, 80, 7, 2, 25, 99, 75, 80], 100)
print("Elementos duplicados: ", elementos_duplicados)
Elementos duplicados:  [1, 3, 80]

Façamos uma análise dessa nova solução.

Note que usamos uma estrutura de dados adicional, a tabela_frequencia. O modo como construímos essa tabela pode parecer estranho a princípio, mas o que ele faz é criar uma lista de tamanho m com todas as posições preenchidas com o valor 0. Esta é uma forma bastante pythonica de se criar e inicializar uma lista com todos os elementos iguais.

O uso de uma estrutura de dados adicional nos permitiu reduzir a complexidade assintótica do nosso algoritmo. Nossa solução anterior possuía complexidade $O(n^2)$, ao passo que a solução usando a tabela de frequências possui complexidade $O(n)$. Em muitos casos, é possível usar um pouco de memória adicional para reduzir a complexidade de tempo do algoritmo. Se construirmos uma tabela com as complexidades de tempo e espaço das duas soluções veremos este fenômeno mais claramente.

Solução Original Solução Otimizada
Tempo Espaço Tempo Espaço
$O(n^2)$ $O(1)$ $O(n)$ $O(m)$

Da mesma forma como calculamos a complexidade de tempo (relativa ao tempo de execução do algoritmo), podemos calcular a complexidade de espaço (quantidade de memória usada pelo algoritmo). A tabela acima mostra a complexidade de tempo e de espaço para os dois algoritmos discutidos anteriormente.

Exemplo: Inverter um arranjo

Listas em Python possuem o método reverse, que inverte o conteúdo da lista. Sua tarefa é implementar uma função chamada inverte, que possui a mesma funcionalidade básica da função reverse em Python. Por exemplo, dada a lista [1, 2, 3, 4, 5, 6, 7], sua função deve retornar [7, 6, 5, 4, 3, 2, 1].

Assim como nos exemplos anteriores, façamos uma análise preliminar. A entrada do algoritmo é uma lista de números inteiros. A saída do algoritmo é a lista de números invertida.

Agora precisamos pensar em como resolver o problema.

Primeira pergunta: O que devemos fazer se a lista de entrada estiver vazia? Iremos simplesmente retornar uma lista vazia.

E o que fazer se a lista de elementos não estiver vazia?

Se a lista não estiver vazia, precisamos trocar o último elemento com o primeiro, trocar o penúltimo com o segundo, trocar o antepenúltimo com o terceiro, e assim por diante. Este raciocínio nos leva à seguinte solução.

def inverte(nums):
    """Inverte o conteúdo da lista de entrada."""
    inicio = 0
    fim = len(nums) - 1
    while inicio < fim:
        # Note a forma elegante de trocarmos o conteúdo das variáveis.
        nums[inicio], nums[fim] = nums[fim], nums[inicio]
        inicio += 1
        fim -= 1
    return nums


print(inverte([1, 2, 3, 4, 5, 6, 7]))
[7, 6, 5, 4, 3, 2, 1]

Nossa função inverte parece funcionar corretamente. Mas como saber se ela está de fato correta? Basicamente, existem duas formas. A primeira é provarmos matematicamente que a função está correta. Mas isso é tedioso e complexo na maioria dos casos. A segunda, que na verdade não prova a corretude da função, mas que aumenta nosso nível de confiança de que ela esteja certa, é testarmos nossa implementação em um número grande de casos. A função abaixo testa nossa função, comparando o resultado dela com o resultado da função reverse da biblioteca padrão de Python. Na função abaixo, note o uso de asserções.

import random

def confere_inversao(n, m):
    """Checa o resultado da função `inverte` em n listas de tamanho m geradas aleatoriamente."""
    for _ in range(n):
        # Cria uma lista com números aleatórios no intervalo [0, m].
        nums1 = [random.randint(0, m) for _ in range(m)]

        # Cria uma lista com os mesmos elementos de nums1.
        nums2 = list(nums1)

        # Inverte a lista nums1 usando a biblioteca padrão de Python.
        nums1.reverse()

        # Invoca nosso algoritmo para inverter nums2 e confere o resultado.
        assert(inverte(nums2) == nums1)

    print("Sucesso!")

# Checa o resultado do nosso algoritmo em 500 listas geradas aleatoriamente.
confere_inversao(500, 500)
Sucesso!

Na função confere_inversao, usamos a função assert. O que essa função faz é checar se a condição passada como parâmetro é verdadeira. Caso a condição não seja verdadeira, a função assert interrompe o programa prematuramente, gerando um erro. Como a função confere_inversao executou com sucesso, o resultado da nossa função inverte foi o mesmo da função reverse em todos os 500 casos gerados.

Exemplo: Mover zeros

Suponha que lhe seja fornecida uma lista de números. Sua tarefa é mover todos os zeros para o final da lista, preservando a ordem dos números diferentes de zero. Por exemplo, dada a lista [0, 1, 0, 3, 12], seu programa deve retornar [1, 3, 12, 0, 0].

Assim como nos exemplos anteriores, façamos uma análise preliminar. A entrada do algoritmo é uma lista de números. A saída do algoritmo é a lista de números com os zeros movidos para o final e com os números diferentes de zero na mesma ordem em que eles apareciam na lista original.

Agora precisamos pensar em como resolver o problema.

Uma solução simples para esse problema é fazer o seguinte:

  1. Contar o número de zeros.

  2. Mover todos os números diferentes de zero para frente na lista, ignorando quaisquer zeros, uma vez que já sabemos quantos existem.

  3. Preencher as posições no final da lista com o número de zeros obtidos no primeiro passo.

O raciocínio acima nos leva à seguinte solução.

def move_zeros_tres_etapas(nums):
    # Etapa 1: Conta o número de zeros na lista de números.
    zeros = nums.count(0)
    if zeros == 0:
        return nums

    # Etapa 2: Move todos os números diferentes de zero para frente da lista.
    atual = 0
    for i, num in enumerate(nums):
        if num != 0:
            nums[atual] = nums[i]
            atual += 1

    # Etapa 3: Coloca os zeros no final da lista.
    tamanho = len(nums) - 1
    for i in range(zeros):
        nums[tamanho - i] = 0

    return nums

print(move_zeros_tres_etapas([0, 1, 0, 3, 12]))
[1, 3, 12, 0, 0]

A solução acima funciona bem. Mas será que ela é o melhor que podemos fazer? Nossa solução percorre o arranjo de entrada três vezes para realizar a tarefa (relativamente simples) de mover zeros para o final da lista de números. Antes de explicarmos uma solução que percorre a lista de entrada apenas uma vez, precisamos explicar um conceito muito importante: invariantes.

Definição: Um invariante é uma condição que é verdadeira durante a execução de um programa ou trecho de código. Em outras palavras, um invariante é uma relação entre os valores das variáveis que vale no início de cada iteração e não se altera de uma iteração para outra. Essas relações invariantes são usadas para explicar o funcionamento de um algoritmo iterativo e permitem provar, por indução, a corretude do algoritmo.

A definição acima foi adaptada da definição de invariante encontrada aqui.

Um exemplo tornará a definição acima mais clara. Podemos resolver o problema de mover zeros para o final de uma lista de números de entrada de modo eficiente se observarmos os seguintes invariantes:

  1. Todos os elementos antes de um elemento sentinela são diferentes de zero.

  2. Todos os elementos entre o elemento corrente e o sentinela são zeros.

Usando os invariantes acima, podemos usar dois elementos especiais ao percorrer a lista. Um deles é o sentinela, que simplesmente monitora em qual posição da lista está o primeiro zero. Todos os elementos em posições anteriores ao sentinela possuem valores diferentes de zero. O outro elemento especial é o elemento corrente, ou seja, o elemento que estamos examinando naquele momento. Ao percorrer a lista, sempre que encontramos um número diferente de zero, trocamos o número na posição corrente com o número na posição sentinela e movemos o sentinela uma posição em direção ao final da lista de entrada. Ao fazer isso, pegamos um elemento diferente de zero e o colocamos após todos os outros elementos diferentes de zero, e movemos o zero para as posições finais da lista. O raciocínio anterior nos leva à seguinte solução. Nela, imprimimos a lista de números a cada iteração para que fique mais fácil acompanharmos a execução do algoritmo.

def move_zeros(nums):
    sentinela = 0
    for i, num in enumerate(nums):
        if num != 0:
            nums[sentinela], nums[i] = nums[i], nums[sentinela]
            sentinela += 1
        print("Iteração " + str(i) + ": Lista de entrada: " + str(nums))
    return nums

print("Lista final: ", move_zeros([0, 1, 0, 3, 12]))
Iteração 0: Lista de entrada: [0, 1, 0, 3, 12]
Iteração 1: Lista de entrada: [1, 0, 0, 3, 12]
Iteração 2: Lista de entrada: [1, 0, 0, 3, 12]
Iteração 3: Lista de entrada: [1, 3, 0, 0, 12]
Iteração 4: Lista de entrada: [1, 3, 12, 0, 0]
Lista final:  [1, 3, 12, 0, 0]

Perceba que na solução acima os dois invariantes se mantêm. Antes de cada iteração, os elementos antes do sentinela são diferentes de zero. E todos os elementos entre o sentinela e o elemento corrente são iguais a zero. Além disso, de acordo com nossa explicação da solução, sempre que o elemento corrente é diferente de zero, trocamos ele com o sentinela e andamos com o sentinela em direção ao final da lista de entrada. Assim, incrementalmente movemos elementos diferentes de zero para o começo da lista, mantendo a ordem relativa deles, e movemos zeros para o final da lista.

Playground

# Use este espaço para praticar o que você aprendeu nesta seção. # Basta digitar o código no espaço abaixo e clicar 'run'.
Anterior Início Próximo