<!--
Introdução à Programação - 2017 - Prof. Leoônidas de Oliveira Brandão
Introdução à eficiência de algoritmos
LInE (Laboratory of Informatics in Education) - http://www.usp.br/line
IME - USP
Material didático
Pode usar livrevemente este material para fins não comerciais, devendo sempre fazer referência à autoria.
Sugestões/apontamento são bem vindos: leo@ime.usp.br (favor indicar no assunto "material de introducao 'a programacao")
Prof. Leônidas de Oliveira Brandão
http://www.ime.usp.br/~leo
http://line.ime.usp.br
http://www.matemtica.br
-->
<meta http-equiv='Content-Type' content='text/html; charset=UTF-8'>
<meta name='keywords' content='mac0122, material, professores, leonidas de oliveira brandao'>
<link rel='stylesheet' type='text/css' href='css_img_js_conf/all.css'>
<link rel='stylesheet' type='text/css' href='css_img_js_conf/line_introducao_programacao.css'>
<script src="css_img_js_conf/defineLInE.js"></script> <!-- para referencias 'a documentos internos -->
<div class="pagina">
<p class="secao">Introdução à eficiência de algoritmos</p>
<center><p>[
<a href="#precisao" title="Problema de precisao numerica">Precisão</a> |
<a href="#tempo" title="Eficiencia em relacao ao tempo de execucao">Velocidade</a> |
<a href="#cosseno" title="Eficiencia: examinando a funcao transcendente <i>cosseno</i>">Cosseno</a> |
<a href="#muitoingenuo" title="Uma primeira solucao nada eficiente para a funcao <i>cosseno</i>">Solução ineficiente</a> |
<a href="#ingenuo" title="Uma segunda solucao para a funcao <i>cosseno</i>: ainda ineficaz">Solução</a> |
<a href="#eficiente" title="Uma solucao eficiente para a funcao <i>cosseno</i>">Solução eficiente</a>
]</p>
</center>
<!--
<p>
<b>Alterações</b>: //2017 <i>C</i> e <i>Python</i>)
</p>
-->
<p>
Nesta seção examinaremos uma questão essencial à computação, se o algoritmo é ou não eficiente para resolver o problema de interesse.
Sobre isso existem vários aspectos que podem ser considerados, aqui examinaremos dois: a <b>precisão</b> e a <b>velocidade</b>.
<center>
<img src="img/img_precisao_x_velocidade.png" title="Gráfico ilustrando que geralmente precisão varia inversamente com a velocidade"/>
<br/>
<i>Fig. 1. Representação de que maior velocidade de execução geralmente implica em menor precisão numérica.</i>
</center>
</p>
<p>
A <b style="color:#0000aa;">precisão</b> diz respeito à "qualidade" da resposta, é necessário que ela seja
<b style="color:#00aa00;">suficientemente próxima da real solução</b> para o problema considerado.
Para ilustrar podemos considerar um exemplo <i>numérico</i>, por exemplo, tentar encontrar a raíz para determinada
função <i>f(.)</i>, ou seja, encontrar (se existir) algum <i>x</i> para o qual <i>f(x)=0</i>.
Nesse caso, se o interesse estiver em pontos dentro do intervalo <i>[0, 1]</i>, seria inútil se o ponto devolvido
tivesse um <i style="color:#aa0000;" title="pois se a resposta foi 1/2, na verdade a raíz poderia ser desde o ponto 0 até o ponto 1!">erro
maior que <i>0,5</i></i> (i.e., <i>|f(x)| > 0,5</i>).
<br/>
Outro exemplo numérico é computar uma
<a href="https://pt.wikipedia.org/wiki/Fun%C3%A7%C3%A3o_transcendente" target="_blank"
title="função que não pode ser escrita com operações algébricas - ver na WikiPedia">função transcendente</a> como o <i>cosseno</i> de valor real.
Uma vez as operações que um computador digita consegue efetivamente realizar são aquelas diretamente derivadas da soma, é preciso encontrar um
algoritmo que compute uma <i>boa aproximação</i> para o <i>cosseno(x)</i>, qualquer que seja o valor real <i>x</i>.
Neste texto examinaremos as implementações para as funções <i>seno</i> e <i>cosseno</i> empregando o conceito matemático
<a href="https://pt.wikipedia.org/wiki/S%C3%A9rie_de_Taylor" target="_blank">
<b style="color:#00aa00;"
title="um somatório com infinitos termos que aproxima a função por meio de um
polinômio cuja propriedade é que suas derivadas, de todas as ordens,
coincidem com as derivadas da função aproximada no ponto dado">série de Taylor</b></a>. <!-- " -->
</p>
<p>
Quanto à <b style="color:#0000aa;">velocidade</b>, ela diz respeito ao <i>tempo que o algoritmo leva para computar a resposta</i>.
É preciso que o tempo seja viável para o contexto, quer dizer que ao obter a resposta, essa ainda seja útil.
Para ilustrar podemos considerar novamente o exemplo <i>numérico</i> da determinação da raíz da função <i>f(.)</i> (se existir, encontrar
algum <i>x</i> para o qual <i>f(x)=0</i>).
Digamos que o interessado seja uma industria de produção de tintas e que a raíz representa o melhor momento para interromper a
produção de cada um de seus 300 pigmentos distintos.
Nesse caso, se a resposta para cada função/pigmento demorar cerca de 10 minutos, então o método empregado é
inviável, pois seria <i style="color:#aa0000;" title="pois levaria mais de 2 dias para obter a produção ideal para aquele dia!">necessário
cerca de 50 horas para obter as 300 raízes</i> (<i>50 x 10 min = 3000 min</i>).
<br/>
Um exemplo de outra natureza seria o contexto de planejamentos de pousos e aterrissagens em um grande aeroporto, após a ocorrência
de algum evento não esperado, deve-se gerar uma nova escala para as próxima
aterrissagens e decolagens muito rapidamente, antes que acabe o combustível de alguma aeronave em sobrevoo.
</p>
<a name="precisao">
<p class="secao">Problema de precisão numérica</p>
</a>
<p>
Como discutido no <a href="#" onclick="trocaPagina('introducao_float.html')" title="examinar o texto sobre ponto flutuante">texto sobre
<i>ponto flutuante</i></a>, o problema de precisão numérica inicia-se na impossibilidade de representar valores
<i style="color:#00aa00;" title="Impossível representar todos os dígitos de Pi (pois são infinitos)!">irracionais</i>
e mesmo
<i style="color:#00aa00;" title="Impossível representar todos os dígios de 1/3 (pois são infinitos)!">dizimas periódicas</i> que precisam
ser <b style="color:#0000aa;" title="Por exemplo, representar 1/3 por 0,3333 (truncando na quarta casa decimal)">truncados</b>.
Mas existe outra questão de eficiência, que é a precisão numérica do algoritmo utilizado para o cômputo.
Um exemplo ilustrativo é acumular valores que crescem muito rapidamente (como funções exponenciais ou fatoriais) ou
dividir por valores que aproximam-se de zero, ambos podem produzir resultados "ruins":
<b style="color:#0000aa;" title="estourar o maior valor que o computador tem capacidade para representar (overflow)">estouro</b>
(ou <i>transbordamento</i>).
</p>
<p>
Como citado acima, um problema computacional é conseguir implementar funções que não podem ser escritas a partir de operações elementares
de soma e multiplicação, com é o caso da função <i>cosseno</i> (que por isso é transcendental).
Hoje, este não parece ser um problema, pois qualquer computador de bolso tem uma calculadora implementada que é capaz de computar boas
aproximações para a função <i>cosseno</i>.
Entretanto, isso só é possível por implementarem algum algoritmo eficiente, a partir de somas e multiplicações.
No caso das <i>funções trigonométicas</i>, isso é feito usando a técnica matemática da
<i title="Na verdade com um truque para tratar todos os períodos">série de Taylor</i>.
Isso será ilustrado nas tabelas <a href="#solucaoruim" title="seguir para implementação ruim">1 (implementação ineficiente)</a>
e <a href="#solucaoboa" title="seguir para implementação boa">2 (implementação eficiente)</a>.
</p>
<a name="tempo">
<p class="secao">Eficiência em relação ao tempo de execução</p>
</a>
<p>
Existem problemas que sabidamente são intratáveis no sentido de sabermos, matematicamente, que é impossível existir
um algoritmo que consegue resolvê-lo (como o <i>problema da parada</i>: não existe algoritmo que possa decidir se um algoritmo qualquer pára ou
após um tempo finito de execução).
</p>
<!--p class="sabermais" title="Para quem deseja saber um pouco mais 'como funciona'"-->
<p><sabermais title="Para quem deseja saber um pouco mais 'como funciona'">
Existem outros tipos de problemas que supomos <b style="color:#aa0000;">não</b> ser possível resolvê-los eficientemente, ou seja,
todas suas soluções conhecidas são ineficientes
(tempo proporcional à uma função exponencial, de base maior que a unidade).
Um exemplo nessa categoria, que denominada
<a href="https://en.wikipedia.org/wiki/NP-completeness" target="_blank" title="Examinar texto na WikiPedia em Inglês">NP-Completo</a>, é o
<a href="https://pt.wikipedia.org/wiki/Problema_de_satisfatibilidade_booliana" target="_blank"
title="examinar a explicação na WikiPedia sobre o problema da satisfatibilidade"><i>problema da satisfatibilidade</i></a>:
encontrar valores para cada uma de suas variáveis, que são <i>booleanas</i>, de modo a tornar a expressão lógica verdadeira,
como em <i>f(b<sub>1</sub>, b<sub>2</sub>, b<sub>3</sub>) = b<sub>1</sub> E (b<sub>2</sub> OU não b<sub>3</sub>)</i>.
Para esse caso, por ser uma instância pequena do problema, é fácil perceber que a resposta é <i>sim</i>, basta tomar
<i>b<sub>1</sub></i> e <i>b<sub>2</sub></i> como <i>verdadeiro</i> (não importando o valor de <i>b<sub>3</sub></i>
pode ser <i>verdadeiro</i> ou <i>falso</i>).
A solução conhecida para a <i>satisfatibilidade</i> é tentar todas as <i>2<sup>n<sup></i> possibilidades para as <i>n</i>
variáveis! Se o <i>n</i> for grande, é inviável esperar por uma resposta.
Exemplo para <i>n=3</i>: testar com
<codigo2> <i>f(verdadeiro,verdadeiro,verdadeiro)</i>, <i>f(verdadeiro,verdadeiro,falso)</i>,
<i>f(verdadeiro,falso, verdadeiro)</i>, <i>f(verdadeiro,falso, falso)</i>,
<i>f(falso, verdadeiro,verdadeiro)</i>, <i>f(falso, verdadeiro,falso)</i>,
<i>f(falso, falso, verdadeiro)</i>, <i>f(falso, falso, falso)</i>.</codigo2>
</sabermais>
</p>
<p>
Na seção seguinte examinaremos um particular problema, conseguir um valor aproximado para a função trigonométrica <i>cosseno</i>,
explorando tanto a questão da eficiência numérica (precisão) quanto a de tempo de execução (velocidade).
</p>
<a name="cosseno">
<p class="secao"><i>Série de Taylor</i> e a função <i>cosseno</i></p>
</a>
<p>
A função <i>cosseno</i>, assim como várias outras, não pode ser computada de modo exato em um computador digital,
em razão de ser uma
<a href="https://pt.wikipedia.org/wiki/Função_transcendente" title="sobre funcao transcendente">função <i>transcendente</i></a>
(basicamente, significa que não pode ser computada a partir de somas).
Então usamos uma
<a href="https://en.wikipedia.org/wiki/Taylor_series" target="_blank"
title="examinar a explicação na WikiPedia sobre séries de Taylor">teoria matemática apresentada em 1715</a>,
aproximá-la por uma função polinomial que tem como propriedade ter todas as derivadas
coincidindo com as derivadas da função a ser aproximada, considerando determinado ponto fixado.
Esse polinômio de infinitos termos, recebeu o nome de
<a href="https://pt.wikipedia.org/wiki/S%C3%A9rie_de_Taylor" title="sobre serie de Taylor na WikiPedia"><b>série de Taylor</b></a>,
devido seu proponente Brook Taylor.
</p>
</p>
O <i>polinômio de Taylor</i> que aproxima a função cosseno quando aplicada ao ponto <i>x</i> é:
<center>
<i>cos(x) = 1 - x<sup>2</sup> /2! + x<sup>4</sup> /4! - x<sup>6</sup> /6! + x<sup>8</sup> /8! + ...</i>
</center>
Se estiver interessado entender a Matemática para se construir a demostração desse polinômio, estude o bloco abaixo.
<p>
<p>
<sabermais title="Para quem deseja saber um pouco mais: mas precisa conhecer Cálculo Diferencial">
Como a função <i>cosseno</i> é periódica, de período <i title="letra grega Pi, representa a irracional 3.1415926535897932384626433...">2*Π</i>
e além disso os valores em cada quadrante coincidem em módulo, podemos computar apenas para primeiro caso, para <i>x</i> entre
<i>0</i> e <i>Π/2</i>.
<img class="imgDir" src="img/img_eficiencia_cos_trig.png" title="Imagem (do iGraf) da função trigonométrica cosseno indicando o período 2*Π">
Desse modo, podemos usar um caso particular da <b>série de Taylor</b>, a séria aplicada ao ponto <i>x=0</i>, que neste caso é chamada
de
<a href="https://en.wikipedia.org/wiki/Colin_Maclaurin"
title="sobre serie de MacLaurin na WikiPedia"><b style="color:#0000aa">série de MacLaurin</b></a>.
Fixado um valor real <i>x</i> entre <i>0</i> e <i title="letra grega Pi, representa a irracional 3.1415926535897932384626433...">Π/2</i>,
a <i>série de MacLaurin</i> que aproxima o cosseno aplicado ao ponto <i>x=0</i>, <i>cos(x)</i>, é o polinômio (de infinitos termos)
<i>p(x)=a<sub>0</sub>+a<sub>1</sub>x<sup>1</sup>+a<sub>2</sub>x<sup>2</sup>+a<sub>3</sub>x<sup>3</sup>+...</i>
de tal forma que
a <i>k</i>-ésima derivada de <i>p(0)</i> coincide com a <i>k</i>-ésima derivada de <i>cos(0)</i>, ou seja,
<i>cos(0)=p(0)</i>, <i>cos'(0)=p'(0)</i>, <i>cos''(0)=p''(0)</i> e assim por diante.
<br/>
<br/>
Assim, no caso da função cosseno, escrevendo o polinômio candidato
<i>p(x) = a<sub>0</sub> x<sup>0</sup> + a<sub>1</sub> x<sup>1</sup> + a<sub>2</sub> x<sup>2</sup> +...</i>
e estabelecendo as identidades para cada derivada e usando <i>x=0</i> e sabendo que
<i>cos(0)=1</i>, <i>sen(0)=0</i>, que
<i>cos'(x)=-sen(x)</i> e que <i>sen'(x)=cos(x)=</i>, obtém-se
<br/>
<i>p(0)=a<sub>0</sub>
⇒ a<sub>0</sub> = 1<br/>
<i>p'(0)=a<sub>1</sub>+2a<sub>2</sub>x<sup>1</sup>+3a<sub>3</sub>x<sup>2</sup>+...</i>|x=0
⇒ p'(0)=a<sub>1</sub>
⇒ a<sub>1</sub> = p'(0)= -sen(0) = 0
⇒ a<sub>1</sub> = 0<br/>
<i>p''(0)=2a<sub>2</sub>+6a<sub>3</sub>x<sup>1</sup>+12a<sub>4</sub>x<sup>2</sup>+...</i>|x=0
⇒ (1/2)p''(0)=a<sub>2</sub>
⇒ a<sub>2</sub> = (1/2)(-cos(0)) = -1
⇒ a<sub>2</sub> = -1/2<br/>
<i>p'''(0)=6a<sub>3</sub>+24a<sub>4</sub>x<sup>1</sup>+...</i>|x=0
⇒ (1/6)p'''(0)=a<sub>3</sub>
⇒ a<sub>3</sub> = (1/6)(cos'''(0)) = (1/3!)(-sen''(0)) = (1/3!)(-cos'(0)) = (1/3!)sen(0) = (1/3!)0
⇒ a<sub>3</sub> = 0<br/>
e assim, por diante, obtendo-se o polinômio aproximador:
<br/>
<i>cos(x) = 1 - x<sup>2</sup> /2! + x<sup>4</sup> /4! - x<sup>6</sup> /6! + x<sup>8</sup> /8! + ...</i>
</sabermais>
</p>
<!--
⇒ = implica
≃ aproximado
✓
-->
<a name="cosseno">
<p class="secao">Eficiência: examinando a função transcendente <i>cosseno</i></p>
</a>
<p>
A implementação da aproximação da função <i>cosseno</i>, próximo do valor nulo, por <i>série de Taylor</i> produz um bom exemplo
para ilustrar <i>ineficiência</i> e <i>eficiência</i> de algoritmos, quanto ao tempo de execução e quanto à precisão numérica.
Uma primeira observação é que é necessário truncar a série por duas razões:
é impossível computar infinitos termos; além disso a partir de determinado termo, todos os seguintes resultam zero (devido à
precisão finita de qualquer computador).
Portanto, devemos <i>truncar</i> a <i>série de Taylor</i>.
</p>
<p>
Analisando o polinômio de Taylor para o <i>cosseno</i>, talvez um aprendiz na arte da programação perceba
que é possível escrever cada termos do somatório com
<i>(-1)<sub>k</sub>(1/2k!)x<sup>2k</sup></i>, <i>k=0,1,2,...</i>.
Ou seja, cada termo tem no numerador um cálculo de exponencial (<i>x<sup>2k</sup></i>) e no denominador um cálculo de fatorial (<i>2k!</i>).
Daí poderia-se desenhar um laço acumulando cada um desses termos.
<br/>
Entretanto, essa solução tem um claro problema (que aparecerá no primeiro teste):
o computo de exponencial (se maior que um) e de fatorial, ambos crescem muito rápido!
Isso resultará em valores nada próximos do esperado.
Isso é ilustrado abaixo.
</p>
<a name="taylor">
<p class="secao">Uma primeira solução nada eficiente para a função <i>cosseno</i></p>
</a>
<p>
A partir da série de Taylor para o cosseno, percebe-se que pode-se elaborar um laço que a cada passo computa um dos termos da série, primeiro
<i>1=x<sup>0</sup>/0!</i>, depois <i>x<sup>2</sup>/2!</i> e assim por diante, para um passo genérico <i>k</i> seria,
<i>-1<sup>k</sup>x<sup>2k</sup>/(2k!)</i>.
</p>
<p>
Desse modo uma primeira solução, seria implementar duas funções auxiliares, uma para computar a potência (<i>pot</i>) e uma para o
fatorial (<i>fat</i>), a cada passo invocando as funções auxiliares.
Vamos simplificar a condição de parada, fixando a <i>priori</i> o número de termos calculados, digamos <i>NT=10</i>.
<center>
<a name="solucaoruim">
<i>Tab. 1. Uma implementação muito ineficiente para a Série de Taylor que aproxima <i>cosseno</i>.</i>
</a>
<br/>
<table class="tbCodeLinCol">
<tr class="tbCodeLinColH"><th colspan="2">Algoritmo muito ineficiente para cômputo do cosseno</th></tr>
<tr><th>C </th> <th>Python</th></tr>
<tr valign="top"><td><table class="tbCode">
<tr><td><pre>i = 0;
while (i<2*NT) { <cyan>// Ineficiente! Nao implemente assim!</cyan>
soma = soma + pot(-1, 2*i) * pot(x, 2*i) / fat(2*i);
i += 2;
}</pre></td></tr>
</table></td>
<td><table class="tbCode"><pre>i = 0;
while (i<2*NT) : <cyan># Ineficiente! Nao implemente assim!</cyan>
soma = soma + pot(-1, 2*i) * pot(x, 2*i) / fat(2*i);
i += 2;
return soma;</pre></td></tr>
</table></td></tr>
</table></center>
<p>
<p>
Testando-se o algoritmo acima, percebe-se rapidamente que o método não é eficiente. Por exemplo, examinando a tabela 1, na qual listamos
os resultados para vários valores de <i>x</i> empregando o método acima, um método eficiente (vistao abaixo) e a função <i>cosseno</i>
da biblioteca da linguagem.
Nota-se que já na segunda linha, para <i>x=0.05</i>, o método ineficiente gera o valor <i>1.0012</i> enquanto o eficiente e a biblioteca
<i>0.9988</i>, uma diferença nada desprezível.
Isso vai piorando com o aumento de <i>x</i>, para o último tabelado, <i>x=0.45</i>, a diferença já está em quase <i>0.2</i>!
</p>
<p>
<b>Ineficiência 1</b>.
Fazendo um rápido exame da solução notamos um primeiro item de ineficiência:
computar <i>pot(-1, 2*i)</i> a cada passo.
Isso é completamente desnecessário, pois de um passo ao outro deve-se apenas inverter o sinal, então bastaria usar uma variável
<tt>sinal</tt>,
que a cada passo fizesse <tt>sinal = -sinal</tt>.
</p>
<p>
<b>Ineficiência 2</b>.
Note que a mesma ineficiência do sinal ocorre com <tt>pot</tt> e <tt>fat</tt>, pois a cada passo ignora-se que uma potência e um fatorial
parcial já foi computado, calculando tudo desde o primeiro valor.
Se ainda não está claro que pode ser melhorado, vamos examinar os passos <tt>k=2</tt> e <tt>k=3</tt>:
<br/>
- <tt>k=2</tt>: computa-se <tt>pot(x, 2*2)=pot(x, 4)</tt> e <tt>fat(2*2)=fat(4)</tt>; e<br/>
- <tt>k=3</tt>: computa-se <tt>pot(x, 2*3)=pot(x, 6)</tt> e <tt>fat(2*3)=fat(6)</tt>.<br/>
Mas, se usarmos uma variável <tt>pot1</tt> para manter a potência e <tt>fat1</tt> para manter o fatorial,
<!--
<i>x<sup>2k</sup></i> (<tt>pot(x, 2*k)</tt>) e
<tt>fat1</tt> para manter <i>2k!</i> (<tt>fat(2*k)</tt>),
-->
então, ao final do passo <tt>k=2</tt>,
<tt>pot1</tt> estaria com o valor <i>x<sup>2k</sup>=x<sup>4</sup></i> e <tt>fat1</tt> com o valor <i>2k!=4!=24</i>.
<br/>
Portanto, no passo <tt>k=3</tt>, bastaria fazer:
<center>
<tt>pot1 = pot1 * x * x</tt> e <tt>fat1 = fat1 * 5 * 6</tt>,
</center>
pois dessa forma, conseguiríamos
<center><!-- ⇒ = implica -->
<tt>pot1 ← pot1 * x * x ⇒ pot1 ← x<sup>4</sup> x<sup>2</sup> = x<sup>6</sup></tt> e
<br/>
<tt>fat1 ← fat1 * 5 * 6 ⇒ fat1 ← 4! * 5 * 6 = 6!</tt>.
</center>
</p>
<p>
Outro problema da solução da tabela 1 é que potência e fatorial crescem muito rápido
(se <i>x > 1</i>, mas se <i>x < 1</i>, então decresce muito rápido).
Isso também pode resultar ineficiência numérica.
</p>
<p>
Portanto, esta solução 1 é muito ineficaz, tanto em termos de velocidade quanto de precisão.
A discussão da razão de sua ineficácia já indica um caminho de melhoria, examinado a seguir.
</p>
<a name="ingenuo">
<p class="secao">Uma segunda solução para a função <i>cosseno</i>: ainda ineficaz numericamente</p>
</a>
<p>
Uma solução um pouco melhor, mas numericamente ainda ingênua, seria eliminar a grande ineficiência citada acima, a cada passo
aproveitando a potência e o fatorial anterior.
Usando como critério de parada que as diferenças entre o cômputo do termo da série seja menor que um dado limiar <i>Lim</i>,
o código pode ficar como o mostrado abaixo. Suporemos a existëncia de uma função que devolve o módulo de um valor "flutuante", de nome <i>valor_absoluto</i>:
<center>
<a name="solucaomedia">
<i>Tab. 2. Uma implementação não tão ineficiente para a Série de Taylor que aproxima <i>cosseno</i>.</i>
</a>
<br/>
<table class="tbCodeLinCol">
<tr class="tbCodeLinColH"><th colspan="2">Algoritmo ineficiente para cômputo do cosseno</th></tr>
<tr><th>C </th> <th>Python</th></tr>
<tr valign="top"><td><table class="tbCode">
<tr><td><pre><verm>float</verm> cossInef (<verm>float</verm> x) {
<verm>float</verm> pot = 1, soma = 0;
<verm>float</verm> termo0 = 2, termo = 1;
<verm>int</verm> fat = 1, i = 1, sinal = 1;
while (valor_absoluto(termo0-termo)>Lim) {
soma = soma + termo;
pot *= x * x; <cyan>// compute potencia 2i de x</cyan>
fat *= (i+1) * (i+2); <cyan>// compute fatorial de 2i</cyan>
termo0 = termo;
termo = sinal * pot / fat;
i += 2;
sinal = -sinal;
}
return soma;
}</pre></td></tr>
</table></td>
<td><table class="tbCode"><pre><verm>def</verm> cossInef (x) :
pot = 1; soma = 0;
termo0 = 2; termo = 1;
fat = 1; i = 0; sinal = 1;
while (valor_absoluto(termo0-termo)>Lim) :
soma = soma + termo;
pot *= x * x; <cyan># compute potencia 2i de x</cyan>
fat *= (i+1) * (i+2); <cyan># compute fatorial de 2i</cyan>
termo0 = termo;
termo = sinal * pot / fat;
i += 2;
sinal = -sinal;
return soma;</pre></td></tr>
</table></td></tr>
</table></center>
</p>
<p>
Rodando este algoritmo e comparando-o com a implementação interna das linguagens <b>C</b> e <b>Python</b>, mesmo para valores
próximos de zero (como <i>0.1</i>) nota-se uma diferença significativa de <i>0.01</i> (veja a tabela abaixo onde comparamos o algoritmo
acima, sua versão mais eficiente e a implementação interna da linguagem).
Isso indica que o método acima <b>não</b> é eficiente.
</p>
<p>
Analisando-se o algoritmo, percebe-se que o potencial problema é que a variável <i>termo</i> é resultado da divisão de 2 valores que tem
tem potencial de crescimento enorme (as variáveis <i>pot</i> e <i>fat</i> - com valor <i>x</i> próximo de zero, <i>pot</i> na verdade
aproxima-se muito rápido é do zero).
<p>
</p>
Outra observação importante: a diferença entre 2 passos no laço para a variável <i>termo</i> é multiplicar por <i>x * x / (i+1)*(i+2)</i>.
Assim, poderia-se tentar a cada passo multiplicar diretamente por esta "diferença" e não acumular a potência e o fatorial!
</p>
<a name="eficiente">
<p class="secao">Uma solução eficiente para a função <i>cosseno</i></p>
</a>
<p>
Usando esta ideia produz-se o algoritmo seguinte que é bem mais eficiente. Nele aproveitamos para ilustrar o uso
de medição de tempo de execução tanto em <b>C</b> quanto em <b>Python</b>,
<center>
<a name="solucaoboa">
<i>Tab. 3. Uma implementação bem eficiente para a Série de Taylor que aproxima <i>cosseno</i>.</i>
</a>
<br/>
<table class="tbCodeLinCol">
<tr class="tbCodeLinColH"><th colspan="2">Algoritmo eficiente para cômputo do cosseno - comparação com o ineficiente e o interno</th></tr>
<tr><th>C </th> <th>Python</th></tr>
<tr valign="top"><td><table class="tbCode">
<tr><td><pre><cyan>// Leo^nidas O. Brandao - 2017/06/19</cyan>
<cyan>// cos(x) = 0! x^0 - x^2 /2! + x^4 /4! - x^6 /6! + x^8 /8! + ...</cyan>
<cyan>// = 1 - x^2 /2! + x^4 /4! - x^6 /6! + x^8 /8! + ...</cyan>
<cyan>// gcc -lm -o introducao_eficiencia_algoritmos_cosseno introducao_eficiencia_algoritmos_cosseno.c</cyan>
<incl1>#include</incl1> <stdio.h>
<incl1>#include</incl1> <math.h> <cyan>// cos(x)</cyan>
<incl1>#include</incl1> <time.h> <cyan>// clock_t, clock()</cyan>
<def>#define</def> Lim 0.001
<verm>float</verm> valor_absoluto (<verm>float</verm> x) {
if (x>=0) return x;
return -x;
}
<cyan>// Cosseno implementado de modo ineficiente</cyan>
<verm>float</verm> cossInef (<verm>float</verm> x) { ... } <cyan>// copiar aqui o codigo C do ineficiente acima</cyan>
<cyan>// Cosseno implementado de modo mais eficiente</cyan>
<verm>float</verm> cossEfic (<verm>float</verm> x) {
<verm>float</verm> pot = 1, soma = 0;
<verm>float</verm> termo0 = 2, termo = 1;
<verm>int</verm> i = 0, sinal = 1;
while (valor_absoluto(termo0-termo)>Lim) {
soma = soma + termo;
termo0 = termo;
termo *= -1 * x * x / ((i+1) * (i+2)); <cyan>// compute potencia 2i de x e fatorial de 2i</cyan>
i += 2;
}
return soma;
}
<verm>int</verm> main (void) {
<verm>float</verm> x, cosx, auxcI, auxcE;
<verm>int</verm> i;
clock_t tempo_inicial = clock(); <cyan>// "dispara o cronometro"...</cyan>
<verd>printf</verd>(" x | ineficiente | eficiente | math cos(x) | dist inef. | dist efic.\n");
x = 0.0;
for (i=0; i<10; i++) {
cosx = cos(x);
auxcI = cossInef(x);
auxcE = cossEfic(x);
<verd>printf</verd>(" %3.2f | %11.4f | %9.4f | %11.4f | %10.4f | %10.4f\n",
x, auxcI, auxcE, cosx, valor_absoluto(auxcI-cosx), valor_absoluto(auxcE-cosx));
x += 0.05;
}
clock_t tempo_final = clock();
<verd>printf</verd>("Tempo em segundos: %f\n", (double)(tempo_final - tempo_inicial) / CLOCKS_PER_SEC);
return 1;
}</pre></td></tr>
</table></td>
<td><table class="tbCode"><pre><cyan># Leo^nidas O. Brandao - 2017/06/19</cyan>
<cyan># cos(x) = 0! x^0 - x^2 /2! + x^4 /4! - x^6 /6! + x^8 /8! + ...</cyan>
<cyan># = 1 - x^2 /2! + x^4 /4! - x^6 /6! + x^8 /8! + ...</cyan>
<cyan># Invocar execucao com linha de comando: python introducao_eficiencia_algoritmos_cosseno.py</cyan>
<incl1>import</incl1> math; <cyan># para cos(x)</cyan>
<incl1>import</incl1> time; <cyan># para tempo 'time.time()'</cyan>
Lim = 0.001
<verm>def</verm> valor_absoluto (x) :
if (x>=0) : return x;
return -x;
<cyan># Cosseno implementado de modo mais eficiente</cyan>
<verm>def</verm> cossInef (x) : <cyan># Copiar aqui a implementacao de cosseno ineficiente</cyan>
...
<cyan># Cosseno implementado de modo mais eficiente</cyan>
<verm>def</verm> cossEfic (x) :
pot = 1; soma = 0;
termo0 = 2; termo = 1;
i = 0; sinal = 1;
while (valor_absoluto(termo0-termo)>Lim) :
soma = soma + termo;
termo0 = termo;
termo *= -1 * x * x / ((i+1) * (i+2)); <cyan># compute potencia 2i de x e fatorial de 2i</cyan>
i += 2;
return soma;
<verm>def</verm> main () :
tempo_inicial = time.time(); <cyan># "dispara o cronometro"...</cyan>
<verd>print</verd>(" x | ineficiente | eficiente | math cos(x) | dist inef. | dist efic.");
x = 0.0;
for i in range(0, 10) :
cosx = math.cos(x);
auxcI = cossInef(x);
auxcE = cossEfic(x);
<verd>print</verd>(" %3.2f | %11.4f | %9.4f | %11.4f | %10.4f | %10.4f" %
( x, auxcI, auxcE, cosx, valor_absoluto(auxcI-cosx), valor_absoluto(auxcE-cosx) ));
x += 0.05;
tempo_final = time.time();
<verd>print</verd>("Tempo em segundos: %f\n" % (tempo_final - tempo_inicial));
main();</pre></td></tr>
</table></td></tr>
</table></center>
</p>
<p>
Experimente rodar em sua máquina o código acima (completanto com o código da função <i>cossInef</i>, implementada na tab. 1).
Na máquina usada em 2017 para o primeiro teste desse código, tanto rodando <i>C</i> quanto <i>Python</i>, produzem como resultado a tabela abaixo.
Note que a medida
que o <i>x</i> se afasta da origem, aparece mais erro, entretanto os erros são consistentemente maiores ao usar
a implementação ingênua.
<center>
<i>Tab. 4. As saídas geradas pelos códigos ineficientes e eficientes (da tabela 3) para aproximar <i>cosseno</i>.</i>
<pre> x | ineficiente | eficiente | math cos(x) | dist inef. | dist efic.
0.00 | 1.0000 | 1.0000 | 1.0000 | 0.0000 | 0.0000
0.05 | 1.0012 | 0.9988 | 0.9988 | 0.0025 | 0.0000
0.10 | 1.0050 | 0.9950 | 0.9950 | 0.0100 | 0.0000
0.15 | 1.0112 | 0.9888 | 0.9888 | 0.0225 | 0.0000
0.20 | 1.0199 | 0.9801 | 0.9801 | 0.0399 | 0.0000
0.25 | 1.0311 | 0.9689 | 0.9689 | 0.0622 | 0.0000
0.30 | 1.0447 | 0.9553 | 0.9553 | 0.0893 | 0.0000
0.35 | 1.0606 | 0.9394 | 0.9394 | 0.1213 | 0.0000
0.40 | 1.0789 | 0.9211 | 0.9211 | 0.1579 | 0.0000
0.45 | 1.0996 | 0.9004 | 0.9004 | 0.1991 | 0.0000</pre></center>
</p>
<p>
Os resultados numéricos são os mesmos comparando o executável a partir do código <i>C</i> ou a interpretação do <i>Python</i>,
Entretanto, os tempos de execução diferem,
sendo significativamente menores utilizando a versão compilada (compilador <b>Gnu GCC</b>).
Usando a mesma máquina (um PC com 2 processadores AMD Phenom II rodando Linux/Debian 8.8),
os menores resultados de tempo de execução (dentre 100 testes) para o executável via <i>C</i> e o interpretado
<i>Python</i>: <center><pre>
C Python
Tempo em segundos: 0.000079 0.000220</pre></center>
</p>
<p>
Em novos testes, desta vez usando um computador de dois núcleos com processador <i>Intel Core i5-6400 CPU @ 2.70GHz</i>,
com sistema <i>Debian GNU/Linux 9.12</i>, rodando 400 vezes, eliminando-se as linhas com comando de impressão
(pois as saídas poderiam uniformizar os resultados por serem significativamente mais lentas),
os resultados numéricos do executável (compilação <i>Gnu GCCC</i>) mostra um bastante superior ao interpretador <i>Python</i>.
Os tempos médios das 400 rodadas, do menor tempo de execução e do maior tempo, para a versão compilada e interpretada foram
(em segundos):
<center><pre>
C Python
Tempo medio: 0.000520 0.008276
Tempo minimo: 0.000016 0.000076
Tempo maximo: 0.000945 0.016031</pre></center>
</p>
<!--
2020/08/13 - /proc/cpuinfo = 2 x Intel(R) Core(TM) i5-6400 CPU @ 2.70GHz
C
-->
<p>
Este é apenas um resumo para apresentar o assunto de eficiência de algoritmos, seu aprofundamente demanda muito mais tempo.
Por exemplo, no IME-USP existe um curso (usualmente de segundo ano) cujo objeto de estudo é precisamente
discutir efeciência de algoritmos, o curso
<a href="http://uspdigital.usp.br/jupiterweb/obterDisciplina?sgldis=MAC0122&verdis=2"
title="ver ementa">MAC0122 - Princípios de Desenvolvimento de Algoritmos</a>.
No programa de Verão do IME-USP temos o curso
<a href="http://www.ime.usp.br/verao/index.php/turmas/apresentacao.php"
title="ver lista de cursos do ultimo Verao">Tópicos de Programação</a>.
</p>
<p class="autoria">
<a href="https://www.ime.usp.br/~leo" target="_blank" title="seguir para a pagina do prof. Leônidas">Leônidas de Oliveira Brandão</a><br/>
<a href="http://www.ime.usp.br/~leo" target="_blank" title="seguir para a página do LInE">http://line.ime.usp.br</a>
</p>
<p class="rodape">
<b>Alterações</b>:<br/>
2020/08/15: novo formato, pequenas revisões<br/>
2020/08/13: ampla revisão (introdução nova, com imagem), novo formato;<br/>
2019/04/24: primeira versão
</p>
</div>