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.
- escreva os números de $0$ até $n -1$.
- risque os números $0$ e $1$, que não são primos
-
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$
-
se o número $p$ não estiver riscado
- 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:
- a lista de números que te dou estará ordenada;
- 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ênciais. 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:
-
conheçamos limitantes inferiores e superiores para a posição de alguma estrutura procurada;
-
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.