Unidade 9 - Eficiência de algoritmos

Se compararmos os primeiros computadores digitais com os computadores de hoje, iremos descobrir que os supercomputadores antigos, que ocupavam várias salas de um andar de um prédio são muito mais lentos do que os celulares que hoje seguramos em nossas mãos. Isso é um feito extraordinário, que merece ser contemplado. O computador em que escrevo este texto tem na verdade quatro processadores, cada um executando 1,8 bilhão de instruções elementares por segundo. Esse número é tão grande, que a ideia de que o poder computacional das máquinas atuais é ilimitado é bastante sedutora.

A realidade, no entanto, não demorou em bater na nossa porta e nem precisamos tentar resolver problemas muito complicados para descobrir que, mais vezes sim do que não, os nossos programas demoram mais do que gostaríamos. Foi assim quando tentamos estimar o número de passos no programa da tartaruga e descobrimos que melhor que ela more perto de casa. Foi assim quando percebemos que procurar uma palavra em uma lista de tamanho moderado não é uma tarefa trivial. Vai ser assim quando você tentar ordenar mais do que umas centenas de números com os algoritmos que já aprendemos, vai ser assim quando você tentar realizar alguma operação em uma matriz que representa uma imagem de alta resolução…

Ao relembrarmos o que estudamos desde o início do semestre, vamos perceber que sempre repetimos as mesmas atividades: dado um problema, com entrada e saída bem definidas, primeiro queremos escrever um algoritmo que resolva o problema e, depois, queremos implementar esse algoritmo em uma linguagem de programação. Pode ser frustrante, portanto, descobrir que isso não é suficiente para encontrar uma solução do problema.

Por mais que nosso algoritmo esteja correto e que tenhamos uma implementação impecável desse algoritmo, não resolveremos um problema se o programa implementado precisar de mais memória do que temos disponível, ou se ele gastar vários anos executando. Se quisermos controlar e utilizar os computadores eficientemente, precisamos compreender e identificar quais problemas nossos algoritmos podem resolver — e quais eles não podem. Para isso, precisamos descobrir de que recursos nossos que algoritmos precisam e estimar em que quantidades eles são necessários. Em seguida, vamos começar a estudar o principal recurso utilizado por um algoritmo: o tempo.

Uma lista de números primos

Para discutir melhor sobre o tempo de execução, vamos voltar a um tema recorrente na nossa disciplina.

Escreva um programa que, dado um número inteiro $n$, liste e conte todos os números primos que estão entre $0$ e $n - 1$.

A primeira missão é dar uma estimativa grosseira de quanto tempo é necessário para resolver o problema. Antes disso, precisamos construir e implementar algum algoritmo. Se não conhecermos algum algoritmo, não haverá muito o que discutir. Já conversamos várias vezes sobre como decidir se um número é primo ou não, então eu omitirei o algoritmo em português.

def eh_primo(p):
    if p == 0 or p == 1:
        return False

    tem_divisor = False
    for divisor in range(2, p):
        if p % divisor == 0:
            tem_divisor = True

    if tem_divisor:
        return False
    else:
        return True

def contar_primos(n):
    m = 0
    for p in range(n):
        if eh_primo(p):
            print(p)
            m += 1

    return m

def main():
    n = int(input("Digite o número n: "))
    m = contar_primos(n)
    print(f"Há {m} primos de 0 até {n-1}")

main()

Se testarmos esse programa digitando 10, iremos ver que ele devolve uma resposta imediatamente após pressionarmos enter.

user@notebook:~/ra123456/eficiencia$ python3 primos.py
Digite o número n: 10
2
3
5
7
Há 4 primos de 0 até 9

Como estamos suficientemente confiantes de que esse programa está correto, podemos remover ou comentar a linha print(p). Podemos executar o programa passando valores de $n$ cada vez maiores. Se fizermos isso, o tempo de resposta do programa aumentará sucessivamente, até que consigamos perceber alguma demora.

user@notebook:~/ra123456/eficiencia$ python3 primos.py
Digite o número n: 100
Há 25 primos de 0 até 99
user@notebook:~/ra123456/eficiencia$ python3 primos.py
Digite o número n: 1000
Há 168 primos de 0 até 999
user@notebook:~/ra123456/eficiencia$ python3 primos.py
Digite o número n: 10000
Há 1229 primos de 0 até 9999
user@notebook:~/ra123456/eficiencia$ python3 primos.py
Digite o número n: 100000
^CTraceback (most recent call last):
  File "primos.py", line 32, in <module>
    main()
  File "primos.py", line 28, in main
    m = contar_primos(n)
  File "primos.py", line 19, in contar_primos
    if eh_primo(p):
  File "primos.py", line 7, in eh_primo
    if p % divisor == 0:
KeyboardInterrupt

Para $n = 100000$ a demora do programa é suficientemente grande para que eu tenha perdido a paciência e interrompido a execução. Assim, poderíamos dizer que para valores de $n$ até $10000$ o programa executou rápidamente, enquanto para $n = 100000$ a execução foi lenta. Essa noção de rapidez não é muito melhor do que tentarmos decidir se alguém tem febre encostando a mão em sua testa. Para medir temperatura, usamos um termômetro; para medir tempo, usamos um cronômetro. É claro que o tempo que eu demoro para acionar ou parar um cronômetro é significativo, então vamos utilizar uma ferramenta chamada time, que é um comando comum para executar outros programas e medir o tempo de execução.

user@notebook:~/ra123456/eficiencia$ time python3 primos.py
Digite o número n: 100
Há 25 primos de 0 até 99

real	0m5,203s
user	0m0,026s
sys	0m0,008s

Além da saída normal de nosso programa, o comando time mostra três medidas de tempo. O tempo de sistema (indicado por sys) é o tempo que o sistema operacional utilizou para responder a chamadas de nosso programa; isso inclui, por exemplo, o tempo para carregar o programa na memória. O tempo real é o tempo total gasto, como se de fato tivéssemos utilizando um cronômetro para medir o tempo de execução do programa. Isso inclui o tempo em que gastei para ler a mensagem na tela, digitar o número e apertar a tecla enter. Durante esse tempo, o programa estava parado esperando alguma entrada. O tempo em que de fato instruções de nosso programa estavam sendo executadas corresponde ao tempo indicado por user. Portanto, é essa a medida que iremos utilizar para estimar quanto tempo gasta nosso algoritmo.

Se executarmos outra vez, podemos ter uma surpresa.

user@notebook:~/ra123456/eficiencia$ time python3 primos.py
Digite o número n: 100
Há 25 primos de 0 até 99

real	0m0,833s
user	0m0,052s
sys	0m0,005s

O tempo devolvido por time dobrou, mesmo que a sequência de instruções executadas seja exatamente a mesma. Será que o processador ficou mais preguiçoso? Há muitos fatores que influenciam o tempo de execução medido. Por exemplo, além de nosso programa, há diversos outros processos executando ao mesmo tempo e, como o número de processadores é pequeno, o sistema operacional alterna sucessivamente a lista de processos sendo executados. Isso pode afetar o tempo que cada instrução gasta, por causa do tempo que gastamos para carregar um dado a partir da memória, entre outras razões. Pode ser que a bateria esteja acabando e a velocidade do processador foi reduzida. Muita coisa pode interferir nos valores medidos.

O fato é que time não fornece um tempo preciso. Mas como ele é a única ferramenta que conhecemos até agora, vamos utilizar algumas estratégias experimentais para melhorar nossas medidas. Primeiro vamos substituir o comando input() por uma atribuição n = ..., assim a variação do tempo gasto digitando não irá atrapalhar a medição. Depois, vamos manter constante todos os outros fatores que pudermos controlar (como número de processos executando, etc.) e calcular a mediana dos tempos de três execuções para cada valor de $n$. Poderíamos também usar a média dos tempos, mas a primeira execução de um programa costuma ser muito mais lenta, pois o arquivo precisa ser lido do disco e carregado na memória RAM. Obtemos uma tabela.

n tempo 1 tempo 2 tempo 3 mediana
2000 0,111s 0,104s 0,107s 0,107s
3000 0,234s 0,215s 0,210s 0,215s
4000 0,383s 0,386s 0,365s 0,383s
5000 0,567s 0,554s 0,557s 0,557s
6000 0,825s 0,833s 0,827s 0,827s
7000 1,111s 1,104s 1,078s 1,104s
8000 1,422s 1,409s 1,410s 1,410s
9000 1,787s 1,800s 1,815s 1,815s
10000 2,240s 2,256s 2,215s 2,240s
15000 5,070s 5,175s 5,223s 5,175s

É muito mais fácil entender esses dados plotando um gráfico.

Essa figura se parece muito com uma parábola. É tentador fazer uma regressão sobre esse gráfico, mas adivinhar o tipo de função e ajustar os parâmetros não é uma boa prática. Precismos antes investigar quais elementos afetam o tempo de execução. Só depois de termos evidências podemos dizer que essa função cresce dessa ou daquela maneira.

Como o número de instruções é finito, deve haver algumas que executam muitas vezes. Queremos saber qual instrução executa mais vezes. Já fizemos isso antes e descobrimos que as instruções executadas dentro dos laços são sempre suspeitas. Nesse algoritmo, é fácil descobrir que o teste if p % divisor == 0 é a linha que mais vezes é executada. Em aplicações complexas, pode ser que precisemos utilizar algumas ferramentas chamadas profilers, mas não precisamos delas nessa disciplina.

Vamos tentar contar quantas vezes executamos essa linha. Primeiro, observamos que a função eh_primo é chamada para $p$ variando de $0$ até $n - 1$. Para cada uma dessas chamadas, contamos o número de vezes, começando do $0$.

p 0 1 2 3 4 5 n - 1
# iterações/chamada 0 0 0 1 2 3 n - 3

Olhando a linha de baixo, identificamos uma progressão aritmética (PA) que começa em $1$ e termina em $n-3$. Assim, para descobrir o número de vezes que a linha é executada no total, basta fazer a soma. Podemos consultar a fórmula da soma em uma tabela — ou podemos nós mesmos deduzi-la.

$$ \text{# iterações} = \frac{(n - 3) (n - 2)}{2} = \frac{n^2 - 5 n + 6}{2} \approx \frac{n^2}{2}. $$

O valor exato da soma não interessa; só precisávamos de alguma evidência para que pudéssemos afirmar que o gráfico acima é de fato uma parábola. Se todo o tempo do programa fosse gasto somente nessa linha, então isso era tudo que precisaríamos. Acontece que nosso programa realiza diversas outras atividades. Por exemplo, o interpretador gasta um tempo considerável analisando o código fonte e transformando-o em alguma representação executável pelo processador.

Para que nossa estimativa faça sentido, precisamos garantir que a maior parte do tempo de execução é realmente gasta executando o laço dessa linha em particular. Como os valores testados de $n$ são razoavelmente grandes, temos confiança de que isso é verdade e essa simplificação não é tão ruim assim. Então, podemos dividir o tempo total de execução para um certo $n$ e dividir por $n^2/2$. Isso deve dar uma estimativa (bastante grosseira) de quanto tempo uma iteração da linha if p % divisor == 0 leva para executar. Testamos para o tempo de $n = 15000$:

$$ \text{tempo/iteração} = \frac{\text{tempo}}{\frac{n^2}{2}} = \frac{5{,}175s}{\frac{15000^2}{2}} = 0{,}000000046 s = 46ns $$

Ou seja, o tempo gasto por iteração é cerca de 46 nanosegundos. Agora, se formos executar nosso programa para $n = 30000$, temos pelo menos alguma estimativa de quanto tempo o programa irá levar, mesmo que tenhamos feito diversas simplificações.

$$ \begin{aligned} \text{tempo} &= (\text{# iterações}) \cdot (\text{tempo/iteração}) \\ &= \frac{30000^2}{2} \cdot 46ns = 20{,}7s \end{aligned} $$

Talvez seja mais fácil pensar que, se dobrarmos o valor de $n$, então quadruplicaremos o tempo de execução.

user@notebook:~/ra123456/eficiencia$ time python3 primos.py
Há 3245 primos de 0 até 29999

real	0m20,706s
user	0m20,700s
sys	0m0,004s

Voilà. O fato de termos acertado o tempo exatamente é mera coincidência, juro!

Comparando algoritmos

O algoritmo anterior é bom? Se só conhecermos um algoritmo, então não podemos dizer muito, além de estimar quanto tempo iremos esperar sofrendo. Quando tempo eu iria esperar se não tivesse interrompido a execução quando testei o programa para $n = 100000$?

Só podemos dizer que algoritmo é bom ou ruim, se estivermos comparando com algum outro algoritmo. Pode ser que listar números primos seja um problema tão difícil que podemos sentar resignados de que o algoritmo anterior era o melhor a ser feito. Mas você já deve ter percebido que esse algoritmo é, na verdade, bem ruim. O motivo de sua certeza é que há várias formas de melhorá-lo a fim de torná-lo (muito) mais rápido.

Por exemplo, é claro que um número par maior do que dois não é primo, mas ainda assim a função eh_primo acima insiste em testar números pares. Mais do que isso, já vimos que, se um número não tem divisores maiores que um e menores ou iguais à raiz, então ele só pode ser primo! Nós chamamos esses tipos de alterações de otimizações, porque, em certo sentido, são alterações que deixam o algoritmo mais próximo de “ótimo”. Há muitas outras otimizações possíveis, mas por ora vamos nos concentrar nessas duas.

Sempre que possível, não faça várias otimizações de uma só vez. Ou melhor, nunca tente fazer duas alterações quaisquer no seu programa de uma só vez. É muito mais fácil pensarmos numa coisa só por vez. Se a alteração não der certo, então sabemos exatamente o que aconteceu. Mais importante, fazendo alterações incrementais, podemos medir e verificar se cada uma delas teve o efeito esperado. Primeiro, vamos parar de testar números pares maiores do que dois, adicionado algumas linhas no início da função eh_primo

    if p > 2 and p % 2 == 0:
        return False

Testamos, novamente para $n = 30000$.

user@notebook:~/ra123456/eficiencia$ time python3 primos.py
Há 3245 primos de 0 até 29999

real	0m10,402s
user	0m10,395s
sys	0m0,004s

O tempo praticamente diminui pela metade. Isso era esperado, afinal, deixamos de verificar se metade dos números era primo ou não. Mas esse algoritmo ainda parece insatisfatório, então vamos implementar a segunda otimização sugerida, que parece um pouco mais promissora.

import math

def eh_primo(p):
    if p == 0 or p == 1:
        return False

    if p > 2 and p % 2 == 0:
        return False

    raiz = int(math.sqrt(p))

    tem_divisor = False
    for divisor in range(2, raiz + 1):
        if p % divisor == 0:
            tem_divisor = True

    if tem_divisor:
        return False
    else:
        return True

Na função atualizada, precisamos gastar algum tempo calculando a raiz de $p$, mas a esperança é que esse tempo seja bem menor do que o tempo que economizaremos nas iterações. O motivo de somarmos um à raiz nos limites de range(2, raiz + 1) é que precisamos testar os divisores até a raiz, inclusive.

user@notebook:~/ra123456/eficiencia$ time python3 primos.py
Há 3245 primos de 0 até 29999

real	0m0,104s
user	0m0,101s
sys	0m0,004s

Isso foi rápido! Mas não vamos comemorar ainda. Se os números em que estamos interessados não são muito maiores do 30000, então não há muito mais o que melhorar, vida que segue. Mas se os números forem cem mil, ou, quem sabe, um milhão? Vamos tentar com $n = 1000000$.

user@notebook:~/ra123456/eficiencia$ time python3 primos.py
Há 78498 primos de 0 até 999999

real	0m14,418s
user	0m14,413s
sys	0m0,005s

Comparando algoritmos, não implementações

Sem ideias para melhorar, podemos apelar e reescrever o mesmo algoritmo em uma linguagem de programação “mais rápida”. Mas não podemos misturar bananas com laranjas, ou podemos?

Você deve se lembrar de que Python é uma linguagem interpretada de alto nível. Isso traz algumas vantagens, como a facilidade de uso, tempos de desenvolvimento e teste mais curtos, menos problemas de sintaxe e uma série de outras vantagens.

Enquanto as abstrações de uma linguagem de alto nível são úteis, algumas vezes elas podem sobrecarregar a execução do programa. O motivo é que elas escondem diversas instruções que devem ser executadas, como verificar se índices de uma lista estão dentro dos limites, gerenciar e liberar a memória de objetos etc. Em Python, tudo isso é feito automaticamente. Quando escrevemos em uma linguagem de mais baixo nível, esses detalhes devem ser explicitados. Embora preocupar-se com eles traga mais responsabilidades para o programador — e mais possibilidades de erro, essas diferenças permitem controlar melhor a execução do programa. Em certos casos, evitamos algumas operações desnecessárias e diminuímos o tempo de execução.

Isso quase nunca é verdade para aplicações e algoritmos complexos, mas para algoritmos simples como esse pode fazer diferença. Para tirar à prova, eu reescrevi o algoritmo anterior, dessa vez na linguagem de programação C.

#include <math.h>
#include <stdio.h>

int eh_primo(int p) {
    if (p == 0 || p == 1)
        return 0;

    if (p > 2 && p % 2 == 0)
        return 0;

    int raiz = sqrt(p);

    int tem_divisor = 0;
    for (int divisor = 2; divisor < raiz + 1; divisor += 1) {
        if (p % divisor == 0)
            tem_divisor = 1;
    }

    if (tem_divisor)
        return 0;
    else
        return 1;
}

int contar_primos(int n) {
    int m = 0;
    for (int p = 0; p < n; p++) {
        if (eh_primo(p)) {
            m += 1;
        }
    }
    return m;
}

int main() {
    int n = 1000000;
    int m = contar_primos(n);
    printf("Há %d primos de 0 até %d\n", m, n-1);
    return 0;
}

Você não precisa entendê-lo, mas como esse algoritmo é muito simples, não é difícil vislumbrar o que cada instrução faz. O importante aqui é que esse programa implementa o mesmo algoritmo que o programa anterior. Vamos executá-lo.

user@notebook:~/ra123456/eficiencia$ gcc -o primos primos.c -lm
user@notebook:~/ra123456/eficiencia$ time ./primos
Há 78498 primos de 0 até 999999

real	0m0,799s
user	0m0,799s
sys	0m0,000s

Eita! Para tarefas fundamentais em nossas aplicações, que são realizadas milhares e milhares de vezes, reescrever o algoritmo em uma linguagem de mais baixo nível e evitar os custos escondidos nas abstrações de alto nível pode valer a pena. Mas esse não é o caso de nosso problema. Percebemos isso tão logo tentamos executar o programa para valores de $n$ muito maiores. Mudamos o programa fazendo n = 4000000, compilamos e executamos novamente.

user@notebook:~/ra123456/eficiencia$ gcc -o primos primos.c -lm
user@notebook:~/ra123456/eficiencia$ time ./primos
Há 283146 primos de 0 até 3999999

real	0m6,215s
user	0m6,215s
sys	0m0,001s

É um tempo razoável, mas ainda na ordem de alguns segundos. Se me perguntarem porque o programa demora tanto, já não poderei culpar a linguagem de programação. Terei que admitir que meu algoritmo não é bom.

Podemos ainda fazer várias outras otimizações, mas dessa vez vamos mudar nossa estratégia de contagem. Para isso, perceba que na primeira otimização, evitamos testar múltiplos de 2 maiores de 2. Do mesmo modo, poderíamos evitar múltiplos de 3 maiores que 3 e assim por diante. Isso sugere o seguinte algoritmo, que é chamado de crivo de Eratóstenes desde há muito tempo.

  1. escreva os números de $0$ até $n -1$.
  2. risque os números $0$ e $1$, que não são primos
  3. para cada número $p$ da lista:
    • se o número $p$ não estiver riscado
      • adicione $p$ à lista de primos
      • risque cada múltiplo $2p , 3p, 4p, 5p, \dots$
  4. devolva os números primos encontrados

Para representar os números riscados e não riscados, podemos utilizar uma lista de booleanos. Adicionamos a função seguinte.

def contar_crivo_estatostenes(n):
    m = 0
    riscados = [False] * n

    riscados[0] = True
    riscados[1] = True

    for p in range(n):
        if not riscados[p]:
            m += 1
            for q in range(2*p, n, p):
                riscados[q] = True

    return m

Ajustando a função main e executando o programa em Python,

user@notebook:~/ra123456/eficiencia$ time python3 primos.py
Há 283146 primos de 0 até 3999999

real	0m0,960s
user	0m0,925s
sys	0m0,036s

Muito mais rápido que o algoritmo anterior, mesmo quando comparando com a versão em C. É claro que a linguagem de programação é importante para o tempo que um algoritmo leva, mas a escolha da linguagem de programação não é desculpa para escrever algoritmos ruins.

Jogos

Vamos parar de resolver problemas por um momento e tentar nos entreter com alguns jogos. Sua amiga Diná não está para brincadeira e decide apostar valendo.

Diná pensa em um número e diz:

— Se você acertar o número que estou pensando, ganha R$ 10,00, mas, se errar, paga R$ 1,00.

Você responde:

— Não! Nem sei quais números são permitidos. Se for um número de 0 até 9, então eu jogo.

— Aí também não. Penso em um número de 0 até 99.

— Pode ser. Sou sortudo.

Você é muito insistente, então pensa em jogar até acertar.

Se você deveria ou não apostar em jogos de azar é uma questão. Outra questão é se você ganhará ou perderá com esse jogo. Vamos criar um programa para simulá-lo. Um otimista escreveria o seguinte.

import random

def jogar(numero):
    pago = 0
    recebido = 0
    while True:
        chute = int(input("Qual é seu chute? "))
        if chute == numero:
            recebido += 10
            print(f"O número é o {chute}. Você acertou!")
            break
        else:
            pago += 1
            print(f"Não é o {chute}.")

    return recebido - pago

def main():
    numero = random.randint(0, 99)
    ganho = jogar(numero)
    print(f"Ganhei {ganho} reais!!!")

main()

Eu disse otimista por causa da mensagem de saída. O número pensado por Diná é simulado por um número sorteado aleatoriamente. Vamos ver quanto você irá “ganhar”.

user@notebook:~/ra123456/eficiencia$ python3 adivinhacao.py
Qual é seu chute? 5
Não é o 5.
Qual é seu chute? 86
Não é o 86.
Qual é seu chute? 67
Não é o 67.
Qual é seu chute? 58
Não é o 58.
Qual é seu chute? 65
Não é o 65.
Qual é seu chute? 48
Não é o 48.
Qual é seu chute? 29
Não é o 29.
Qual é seu chute? 99
Não é o 99.
Qual é seu chute? 85
Não é o 85.
Qual é seu chute? 11
Não é o 11.
Qual é seu chute? 15
Não é o 15.
Qual é seu chute? 24
Não é o 24.
Qual é seu chute? 93
Não é o 93.
Qual é seu chute? 72
Não é o 72.
Qual é seu chute? 10
Não é o 10.
Qual é seu chute? 61
Não é o 61.
Qual é seu chute? 78
Não é o 78.
Qual é seu chute? 51
Não é o 51.
Qual é seu chute? 84
Não é o 84.
Qual é seu chute? 69
Não é o 69.
Qual é seu chute? 13
Não é o 13.
Qual é seu chute? 32
Não é o 32.
Qual é seu chute? 83
Não é o 83.
Qual é seu chute? 96
Não é o 96.
Qual é seu chute? 17
Não é o 17.
Qual é seu chute? 1
Não é o 1.
Qual é seu chute? 64
Não é o 64.
Qual é seu chute? 8
Não é o 8.
Qual é seu chute? 35
Não é o 35.
Qual é seu chute? 95
Não é o 95.
Qual é seu chute? 2
Não é o 2.
Qual é seu chute? 75
Não é o 75.
Qual é seu chute? 49
Não é o 49.
Qual é seu chute? 53
Não é o 53.
Qual é seu chute? 70
Não é o 70.
Qual é seu chute? 4
Não é o 4.
Qual é seu chute? 68
Não é o 68.
Qual é seu chute? 14
Não é o 14.
Qual é seu chute? 50
Não é o 50.
Qual é seu chute? 18
Não é o 18.
Qual é seu chute? 34
Não é o 34.
Qual é seu chute? 9
Não é o 9.
Qual é seu chute? 71
Não é o 71.
Qual é seu chute? 28
Não é o 28.
Qual é seu chute? 38
Não é o 38.
Qual é seu chute? 19
Não é o 19.
Qual é seu chute? 37
Não é o 37.
Qual é seu chute? 33
Não é o 33.
Qual é seu chute? 90
Não é o 90.
Qual é seu chute? 42
Não é o 42.
Qual é seu chute? 73
Não é o 73.
Qual é seu chute? 88
Não é o 88.
Qual é seu chute? 22
Não é o 22.
Qual é seu chute? 59
Não é o 59.
Qual é seu chute? 54
Não é o 54.
Qual é seu chute? 97
Não é o 97.
Qual é seu chute? 92
Não é o 92.
Qual é seu chute? 77
Não é o 77.
Qual é seu chute? 0
Não é o 0.
Qual é seu chute? 55
Não é o 55.
Qual é seu chute? 26
Não é o 26.
Qual é seu chute? 27
Não é o 27.
Qual é seu chute? 39
Não é o 39.
Qual é seu chute? 87
Não é o 87.
Qual é seu chute? 82
Não é o 82.
Qual é seu chute? 91
Não é o 91.
Qual é seu chute? 40
Não é o 40.
Qual é seu chute? 81
Não é o 81.
Qual é seu chute? 43
Não é o 43.
Qual é seu chute? 74
Não é o 74.
Qual é seu chute? 56
Não é o 56.
Qual é seu chute? 31
Não é o 31.
Qual é seu chute? 45
O número é o 45. Você acertou!
Ganhei -62 reais!!!

Um belo de um prejuízo. Se o número pensado por Diná é mesmo aleatório, poderíamos muito bem testar cada um dos números de 0 a 99 em ordem que ainda teríamos a mesma chance de acerto.

user@notebook:~/ra123456/eficiencia$ python3 adivinhacao.py
Qual é seu chute? 0
Não é o 0.
Qual é seu chute? 1
Não é o 1.
Qual é seu chute? 2
Não é o 2.
Qual é seu chute? 3
Não é o 3.
Qual é seu chute? 4
Não é o 4.
Qual é seu chute? 5
Não é o 5.
Qual é seu chute? 6
Não é o 6.
Qual é seu chute? 7
Não é o 7.
Qual é seu chute? 8
Não é o 8.
Qual é seu chute? 9
Não é o 9.
Qual é seu chute? 10
Não é o 10.
Qual é seu chute? 11
Não é o 11.
Qual é seu chute? 12
Não é o 12.
Qual é seu chute? 13
Não é o 13.
Qual é seu chute? 14
Não é o 14.
Qual é seu chute? 15
Não é o 15.
Qual é seu chute? 16
Não é o 16.
Qual é seu chute? 17
Não é o 17.
Qual é seu chute? 18
Não é o 18.
Qual é seu chute? 19
Não é o 19.
Qual é seu chute? 20
Não é o 20.
Qual é seu chute? 21
Não é o 21.
Qual é seu chute? 22
Não é o 22.
Qual é seu chute? 23
Não é o 23.
Qual é seu chute? 24
Não é o 24.
Qual é seu chute? 25
Não é o 25.
Qual é seu chute? 26
Não é o 26.
Qual é seu chute? 27
Não é o 27.
Qual é seu chute? 28
Não é o 28.
Qual é seu chute? 29
Não é o 29.
Qual é seu chute? 30
Não é o 30.
Qual é seu chute? 31
Não é o 31.
Qual é seu chute? 32
Não é o 32.
Qual é seu chute? 33
Não é o 33.
Qual é seu chute? 34
Não é o 34.
Qual é seu chute? 35
Não é o 35.
Qual é seu chute? 36
Não é o 36.
Qual é seu chute? 37
Não é o 37.
Qual é seu chute? 38
Não é o 38.
Qual é seu chute? 39
Não é o 39.
Qual é seu chute? 40
Não é o 40.
Qual é seu chute? 41
Não é o 41.
Qual é seu chute? 42
Não é o 42.
Qual é seu chute? 43
Não é o 43.
Qual é seu chute? 44
Não é o 44.
Qual é seu chute? 45
Não é o 45.
Qual é seu chute? 46
Não é o 46.
Qual é seu chute? 47
Não é o 47.
Qual é seu chute? 48
Não é o 48.
Qual é seu chute? 49
Não é o 49.
Qual é seu chute? 50
Não é o 50.
Qual é seu chute? 51
O número é o 51. Você acertou!
Ganhei -41 reais!!!

Agora pelo menos não precisamos anotar os palpites. Só mais uma vez. Estou sentindo que a sorte vai chegar.

user@notebook:~/ra123456/eficiencia$ python3 adivinhacao.py
Qual é seu chute? 0
Não é o 0.
Qual é seu chute? 1
Não é o 1.
Qual é seu chute? 2
Não é o 2.
Qual é seu chute? 3
Não é o 3.
Qual é seu chute? 4
Não é o 4.
Qual é seu chute? 5
Não é o 5.
Qual é seu chute? 6
Não é o 6.
Qual é seu chute? 7
Não é o 7.
Qual é seu chute? 8
Não é o 8.
Qual é seu chute? 9
Não é o 9.
Qual é seu chute? 10
Não é o 10.
Qual é seu chute? 11
Não é o 11.
Qual é seu chute? 12
Não é o 12.
Qual é seu chute? 13
Não é o 13.
Qual é seu chute? 14
Não é o 14.
Qual é seu chute? 15
Não é o 15.
Qual é seu chute? 16
Não é o 16.
Qual é seu chute? 17
Não é o 17.
Qual é seu chute? 18
Não é o 18.
Qual é seu chute? 19
Não é o 19.
Qual é seu chute? 20
Não é o 20.
Qual é seu chute? 21
Não é o 21.
Qual é seu chute? 22
O número é o 22. Você acertou!
Ganhei -12 reais!!!

— Cansei! Vamos jogar outro. Te dou uma sacola com números. Você escolhe um. Eu tenho que acertar.

Diná, indiferente:

— Se você prefere…

Para justificar a indiferença de sua amiga, vamos mais uma vez simular o jogo.

import random

def criar_sacola(n):
    sacola = []
    for _ in range(n):
        sacola.append(random.randint(1, 5000))
    return sacola

def jogar_sacola(sacola, numero):
    pago = 0
    recebido = 0
    for chute in sacola:
        if chute == numero:
            recebido += 10
            print(f"O número é o {chute}. Você acertou!")
            break
        else:
            pago += 1
            print(f"Não é o {chute}.")

    return recebido - pago

def main():
    sacola = criar_sacola(100)
    numero = random.choice(sacola)
    ganho = jogar_sacola(sacola, numero)
    print(f"Ganhei {ganho} reais!!!")

main()

Criamos uma lista com 100 números aleatórios entre 1 e 5000 e depois selecionamos um número aleatório dessa lista com random.choice(sacola). Ele representa o número pensado por Diná. Você deveria ter percebido que a chance de ganhar alguma coisa é a mesma que antes, mas a vontade de jogar é mania incontrolável.

user@notebook:~/ra123456/eficiencia$ python3 adivinhacao.py
Não é o 1353.
Não é o 4843.
Não é o 2722.
Não é o 1692.
Não é o 2487.
Não é o 569.
Não é o 1969.
Não é o 2223.
Não é o 3901.
Não é o 3010.
Não é o 3808.
Não é o 2159.
Não é o 3159.
Não é o 4547.
Não é o 1138.
Não é o 1366.
Não é o 700.
Não é o 1332.
Não é o 2385.
Não é o 4670.
Não é o 3527.
Não é o 3780.
Não é o 1607.
Não é o 4930.
Não é o 1334.
Não é o 1796.
Não é o 1733.
Não é o 1001.
Não é o 2469.
Não é o 1238.
Não é o 1674.
Não é o 510.
Não é o 1079.
Não é o 127.
Não é o 2963.
Não é o 1418.
Não é o 4096.
Não é o 751.
Não é o 4093.
Não é o 3611.
Não é o 77.
Não é o 4378.
O número é o 2557. Você acertou!
Ganhei -32 reais!!!

— Ah… também não gostei. Vou mudar o jogo. Agora temos as seguintes regras:

  1. a lista de números que te dou estará ordenada;
  2. para cada chute, você me dirá se ele é menor ou maior que o número pensado.

— Ok, mas eu mesma irei criar a lista e você deverá adivinhar a posição do número!

— Combinado.

Vacinado, você já sabe que testar todos os números sequencialmente não irá melhorar sua sorte. O fato de não conhecer a lista e ter que adivinhar a posição do número não lhe assusta. Ao menos, agora saberá quando der um bom chute.

import random

def criar_sacola(n):
    sacola = []
    for _ in range(n):
        sacola.append(random.randint(1, 5000))
    sacola.sort()
    return sacola

def jogar_sacola(sacola, numero):
    pago = 0
    recebido = 0
    while True:
        chute = int(input("Em que posição está o número? "))
        print(f"Na posição {chute} o valor é {sacola[chute]}, ", end="")
        if sacola[chute] == numero:
            recebido += 10
            print(f"e pensei nesse número mesmo. Você o encontrou!")
            break
        elif sacola[chute] < numero:
            pago += 1
            print(f"mas pensei em um número maior.")
        else:
            pago += 1
            print(f"mas pensei em um número menor.")
        print()

    return recebido - pago

def main():
    sacola = criar_sacola(100)
    numero = random.choice(sacola)
    ganho = jogar_sacola(sacola, numero)
    print(f"Ganhei {ganho} reais!!!")

main()

Ordenamos a sacola de números antes de começar a jogar. Nesse programa, voltamos a pedir ao usuário que digite um chute; dessa vez, estamos interessados na posição do número pensado. Vamos tentar uma vez, para aprender as regras.

user@notebook:~/ra123456/eficiencia$ python3 adivinhacao.py
Em que posição está o número? 50
Na posição 50 o valor é 2383, mas pensei em um número maior.

Em que posição está o número? 90
Na posição 90 o valor é 4605, mas pensei em um número menor.

Em que posição está o número? 40
Na posição 40 o valor é 2043, mas pensei em um número maior.

Em que posição está o número? 80
Na posição 80 o valor é 4049, mas pensei em um número menor.

Em que posição está o número? 55
Na posição 55 o valor é 2825, mas pensei em um número maior.

Em que posição está o número? 70
Na posição 70 o valor é 3638, mas pensei em um número menor.

Em que posição está o número? 60
Na posição 60 o valor é 3164, mas pensei em um número maior.

Em que posição está o número? 65
Na posição 65 o valor é 3480, mas pensei em um número maior.

Em que posição está o número? 69
Na posição 69 o valor é 3537, e pensei nesse número mesmo. Você o encontrou!
Ganhei 2 reais!!!

O nervosismo pode deixar as pessoas desatentas. Vamos analisar os chutes com cuidado. De nada adiantou tentar a posição 40 no terceiro chute, pois já sabíamos que o número pensado era maior do que o valor da posição 50 e, mais do que isso, que a lista de números estava ordenada. De fato, toda vez que Diná diz maior, descobrimos um limitante inferior para a posição do número pensado e toda vez que Diná diz menor, descobrimos um limitante superior. Isso lhe dá uma ideia para melhorar sua estratégia.

def jogar_sacola(sacola, numero):
    pago = 0
    recebido = 0

    limitante_inferior = 0
    limitante_superior = len(sacola) - 1

    while True:
        chute = (limitante_inferior + limitante_superior) // 2
        print(f"Na posição {chute} o valor é {sacola[chute]}, ", end="")
        if sacola[chute] == numero:
            recebido += 10
            print(f"e pensei nesse número mesmo. Você o encontrou!")
            break
        elif sacola[chute] < numero:
            pago += 1
            print(f"mas pensei em um número maior.")
            limitante_inferior = chute + 1
        else:
            pago += 1
            print(f"mas pensei em um número menor.")
            limitante_superior = chute - 1
        print()

    return recebido - pago

Repare como escolhemos a posição de chute como uma posição intermediária entre os limitantes conhecidos. Observe também como atualizamos os limitantes sempre que fazemos algum chute. Parece que sua sorte finalmente está mudando. Vamos jogar.

user@notebook:~/ra123456/eficiencia$ python3 adivinhacao.py
Na posição 49 o valor é 2591, mas pensei em um número maior.

Na posição 74 o valor é 3733, mas pensei em um número menor.

Na posição 61 o valor é 3109, mas pensei em um número maior.

Na posição 67 o valor é 3324, mas pensei em um número maior.

Na posição 70 o valor é 3450, mas pensei em um número maior.

Na posição 72 o valor é 3548, e pensei nesse número mesmo. Você o encontrou!
Ganhei 5 reais!!!

Diná se estremece.

— Também quero mudar.

— Como?

— Simples, a lista agora terá 1000 números.

Já sem dinheiro na carteira, melhor você pensar duas vezes antes de aceitar essa proposta. Você aceitará?

Buscas

Os jogos acima ilustram duas tarefas muito comuns em computação. A primeira tarefa corresponde ao problema de, dada uma lista de valores, encontrar um determinado elemento. A segunda tarefa corresponde ao problema de, dada uma lista de valores ordenada, encontrar um determinado elemento.

Busca sequencial

Em diversas situações precisamos fazer buscas sequências. Já fizemos isso várias vezes, como quando tivemos que procurar uma palavra em um conjunto de palavras, ou quando procuramos a posição de inserção no vetor para o algoritmo insertion-sort. Recorrentemente, uma função que implementa uma busca sequencial será parecida com a seguinte.

def busca_sequencial(lista, valor_procurado):
    for i, valor in enumerate(lista):
        if valor == valor_procurado:
            return i
    return None

Nessa função, devolvemos None quando não existe um elemento na lista de valor valor_procurado. Dependendo da situação, pode ser mais conveniente levantar uma exceção quando isso acontece.

def busca_sequencial(lista, valor_procurado):
    for i, valor in enumerate(lista):
        if valor == valor_procurado:
            return i
    raise ValueError(f"Valor {valor_procurado} não existe na lista.")

A diferença é que, na segunda versão, faz parte das premissas da função que o valor procurado esteja de fato na lista.

Na verdade, não necessariamente realizamos buscas sequenciais apenas em dados armazenados em uma lista. Por exemplo, para encontrar o máximo de vários números digitados no teclado, não conhecemos todos os números a priori e nem temos controle sobre quais valores serão digitados.

def descobrir_maximo(n):
    maximo = int(input())
    for _ in range(1, n):
        numero = int(input())
        if numero > maximo:
            maximo = numero
    return maximo

Enquanto muitas vezes queremos buscar o valor de um elemento, em outras vezes estamos interessados no índice em que o elemento está. Também, pode ser que não queiramos encontrar um valor exato, mas o primeiro elemento da lista que é maior ou igual a esse número. São diversas as tarefas que resolvemos percorrendo linearmente uma lista de elementos.

Quanto tempo gastamos para procurar um elemento sequencialmente em uma lista depende de quantos elementos há na lista e de onde esse elemento está na lista. Quando temos azar, pode ser que o elemento não esteja presente ou que ele esteja apenas na última posição. Nesses casos, que chamamos de piores casos, temos que acessar todos os elementos.

Busca binária

Algumas vezes temos alguma informação adicional sobre a lista da entrada e sabemos que os elementos estão ordenados. Nesses casos, não precisamos necessariamente acessar todos os elementos da lista para descobrir a posição de um algum valor.

def busca_binaria(lista, valor_procurado):
    limitante_inferior = 0
    limitante_superior = len(lista) - 1
    while limitante_inferior <= limitante_superior:
        m = (limitante_inferior + limitante_superior) // 2
        if lista[m] == valor_procurado:
            return m
        elif lista[m] < valor_procurado:
            limitante_inferior = m + 1
        else:
            limitante_superior = m - 1
    return None

Não tem nada em particular nesse código que nos restrinja a números. A única restrição é de que os elementos sejam comparáveis. Assim podemos comparar strings, tuplas, ou mesmo utilizar uma função particular para comparação como discutido quando falamos de ordenção.

Quanto tempo gasta a função busca_binaria quando passamos uma lista de tamanho $n$? Se você prestar atenção, perceberá que toda vez que atualizamos um limitante, descartamos pelo menos metade das possibilidades. Quantas vezes podemos dividir uma lista em $2$ para que reste apenas um elemento? Essa é justamente a definição do logaritmo na base $2$. Portanto, o número de vezes que testamos alguma posição até encontrar o elemento procurado é no máximo $\log_2 n$. Você pode agora decidir com mais tranquilidade se aceita ou não a última proposta de Diná.

Na verdade, a busca binária é apenas um exemplo de uma estratégia mais geral bastante útil. Para utilizar busca binária em uma sequência, basta que:

  1. conheçamos limitantes inferiores e superiores para a posição de alguma estrutura procurada;

  2. dada uma posição, podemos decidir se existe uma estrutura antes ou depois dessa posição.

Um exemplo dessa ideia pode ser encontrado no chamado método da bissecção, cujo objetivo é encontrar uma aproximação de uma raiz de uma função contínua $f(x)$. Suponha que sabemos que $f(a) < 0$ e que $f(b) > 0$. Como $f$ é contínua, deve haver algum valor $x$ tal que $f(x) = 0$. A função metodo_bisseccao a seguir encontra um valor $y$ tal que $f(y)$ está muito muito próximo de $0$.

ERRO = 0.00000001

def f(x):
    return x**2 - 2

def metodo_bisseccao(a, b, funcao):
    while b - a > ERRO:
        m = (a + b) / 2
        if funcao(m) < 0:
            a = m
        else:
            b = m
    return m

def main():
    a = 0.0
    b = 4.0
    y = metodo_bisseccao(a, b, f)
    print(f"f({y}) = {f(y)}")

main()

Para a função $f$ definida nesse exemplo, uma solução é $\sqrt{2}$. Esse programa nos dá uma aproximação dessa raiz.

user@notebook:~/ra123456/eficiencia$ python3 bisseccao.py
f(1.4142135605216026) = -5.236811428943611e-09

Um outro exemplo de aplicação de busca binária é dado no exercício sobre os sentidos das ruas na lista de exercícios de fixação.