Tempo de execução & Optimização de código

A forma como obter um mesmo resultado utilizando um programa só está limitada pela imaginação do programador.

Contudo, embora o resultado numérico seja o mesmo, o tempo de execução pode ser muito diferente.

Esta diferença pode ser importante e deste modo limitadora da excutabilidade de determiada ideia ou processo.

Vamos utilizar como exemplo o cálculo de um

Integral pelo método de Monte Carlo

O valor médio de uma função (<f>) no intervalo a, b é dado por $$ <f> = \frac{1}{b-a}\int_a^bf(x)dx$$ Por outro lado um valor médio pode ser calculado como $$<f>=\frac{1}{N}\sum_if(x_i)$$ Então temos que um integral pode ser aproximado a $$(b-a)\frac{1}{N}\sum_if(x_i)\simeq\int_a^bf(x)dx$$ Os valores de x devem ser uniformemente distribuídos entre a e b. O seu número (N) e o seu valor vão influenciar o resultado do integral.

Deste modo, vamos calcular muitas vezes (M) o integral e ver qual o valor mais frequente fazendo um histograma para representar a distribuição de valores.

Para distinguirmos a velocidade de cada metodologia utilizada para calcular um integral, é preciso o tempo de execução, que vamos optar, total. Assim, este notebook serve também de exemplo a

Como medir o tempo de execução de um programa

Para isso o python dispõe da função time.

In [21]:
# Vamos precisar dos seguintes módulos/ funções
#
from scipy import random
import numpy as np
import matplotlib.pyplot as plt

from termcolor import colored
In [22]:
# Método escrito sem preocupações de tempo de execução
#
import time
start_time = time.time()

a = 0
b = np.pi
N = 1000    # Número de áreas a calcular
M = 1000    # Número de pontos para calcular o integral

def func(x):
    '''Função integranda'''
    return np.sin(x)

areas = np.zeros(M)

for j in range(M):
    xrand=np.zeros(N)
    for i in range(N):
        xrand[i] = random.uniform(a,b)
    
    integral = 0.0   
    for i in range(N):
        integral += func(xrand[i])
    answer = (b-a)/N*integral
    areas[j]=answer

plt.title("Distribuição de frequências (histograma)")
plt.hist(areas,bins = 30, ec = 'black')
plt.xlabel("Áreas")
plt.ylabel("Frequência")
plt.show()

print("%i integrais, calculados com %i pontos cada um, demoram "%(M,N)+
      colored('%.3f s', 'red')%((time.time() - start_time)))

1000 integrais, calculados com 1000 pontos cada um, demoram 2.953 s
In [23]:
# Método escrito com algumas preocupações de tempo de execução
#
import time
start_time = time.time()
a = 0
b = np.pi
M = 1000
N = 1000

areas = []
for j in range(M):
    xrand = random.uniform(a,b,N) 
    integral=sum(np.sin(xrand))
    answer = (b-a)/N*integral
    areas.append(answer)

plt.title("Distribuição de frequências (histograma)")
plt.hist(areas,bins = 30, ec = 'black')
plt.xlabel("Áreas")
plt.ylabel("Frequência")
plt.show()

print("%i integrais, calculados com %i pontos cada um, demoram "%(M,N)+
      colored('%.3f s', 'red')%((time.time() - start_time)))

1000 integrais, calculados com 1000 pontos cada um, demoram 0.336 s

Conclusão & Desafios

A principal razão de se conseguir diminuir o tempo de execução em mais de 10 X's foi principalmente substituir N chamadas da função func por uma facilidade existente no Numpy.

Essa facilidade do Numpy é a sua capacidade de executar funções sobre matrizes, neste caso o cálculo do sin.

Tal aceleração deve-se ao facto do python ser semi-interpretado, isto é, as funções são compiladas, o código que as chama é que é interpretado.

Outra aceleração obtida, mas menos importante, foi a substituição de array's do Numpy por listas do python.

Consegue fazer mais rápido ainda? Para melhorar a precisão pode-se aumentar N ou M. Como aumenta a diferença entre os tempos de execução? Qual o melhor N? ou M?

Para ver a importância deste assunto, tempo de execução e optimização de código, responda aos desafios sugeridos com ambos os programas. Verá que para N = 10000 e M = 10000 será dificil de esperar pelo primeiro programa.