4

Eu estava brincando com um método para aproximar o numero PI e percebi que o código roda bem lentamente no interpretador Python 3.6, e o processo só está usando 30% do processador.

Teria um jeito de rodar esse script a todo vapor?

from math import sqrt
from random import random

piavg = 0
samples = 10000
scale = 1000
progress = 0
debug_rate = 5
debug_clock = 0



def pis (scale):
    pi = 0
    points = []
    for i in range(scale):
        points.append([random(),random()])
    for p in points:
        if sqrt(p[0] ** 2 + p[1] ** 2) <= 1:
            pi += 1
    pi /= scale
    pi *= 4
    return pi
for i in range(samples):
    cpi = pis(scale)
    progress += 1/samples*100
    if debug_rate > 0 and debug_clock == 0:
        print(str(int(progress)) + "%  encontrado: " + str(cpi))
        debug_clock = debug_rate
    piavg += cpi
    debug_clock -= 1
piavg /= samples

print (piavg)

3 Respostas 3

4

Sem analisar o seu código em profundidade, só batendo o olho rapidamente mesmo, eu já percebi um ponto crítico que pode ser facilmente melhorado: a chamada de sqrt para o cálculo da "distância".

O cálculo da raíz quadrada é bastante custoso, e você o faz com muita frequência. Se você evitá-lo, vai aumentar muitíssimo o desempenho do seu algoritmo. No seu caso é bastante simples porque a sua comparação é com o valor 1, cuja potência de 2 é 1! Logo, basta tirar a chamada de sqrt (caso comparasse com outro valor, você usaria a potência dele na comparação).

Com essa única alteração no código, o tempo de execução já cai pela metade (eu também usei o método de medição de tempo sugerido pelo colega @Miguel na resposta dele).

. . .
def pis (scale):
    pi = 0
    points = []
    for i in range(scale):
        points.append([random(),random()])
    for p in points:
        if (p[0] * p[0] + p[1] * p[1]) <= 1: # <=== Alteração aqui
            pi += 1
    pi /= scale
    pi *= 4
    return pi
. . .

Aqui nos meus testes, a execução do seu código original levou aproximadamente 14.5 segundos e produziu:

. . .
99%  encontrado: 3.188
99%  encontrado: 3.108
99%  encontrado: 3.128
99%  encontrado: 3.008
3.1419439999999845

Enquanto que a execução com a alteração citada levou aproximadamente 8.6 segundos e produziu:

. . .
99%  encontrado: 3.032
99%  encontrado: 3.208
99%  encontrado: 3.144
99%  encontrado: 3.176
3.1421183999999878

P.S.: Esse é só um dos pontos que eu achei mais crítico para o desempenho. Mas vale também seguir as orientações do colega Miguel na resposta dele.

3
  • Muito bem Luiz, que distração não ter reparado nisso.
    – Miguel
    Commented 28/12/2016 às 12:56
  • 1
    Juntando as nossas soluções conseguimos para metade, +- 4 secs, o tempo de execução em relação ao código da pergunta, sendo que a sua sugestão foi a que mais contribuiu
    – Miguel
    Commented 28/12/2016 às 13:01
  • 1
    nossa, eu tinha esquecido dessa propriedade sqrt(xx) < y == xx < y*y, bem pensado!
    – user63500
    Commented 28/12/2016 às 17:28
2

Consegui optimizar, a correr com python 3.5, o tempo de execução em +- 1.2 secs. O que fiz para medir o tempo de excução foi:

from math import sqrt
from random import random
import time

start_t = time.time()

#TODO O TEU CÓDIGO AQUI, fora os imports

print(time.time() - start_t)

Sendo que com o teu código demora entre 8.0 secs e 8.3 secs, com o código que consegui optimizar demora agora entre 6.9 e 7.2, segue o código:

from math import sqrt
from random import random
import time

start_t = time.time()

piavg = 0
samples = 10000
scale = 1000
progress = 0
debug_rate = 5
debug_clock = 0

def pis (scale):
    pi = 0
    points = ((random(),random()) for _ in range(scale)) # points e um gerador em vez de ser uma lista de listas
    for p1, p2 in points: # unpacking points, assim escusamos de estar sempre a aceder aos indices
        if sqrt(p1 ** 2 + p2 ** 2) <= 1:
            pi += 1
    return pi / scale * 4 # tudo numa so expressao

for _ in range(samples): # por convencao se nao se usa o i podemos deixar assim com _ , nao sei se otimiza a performance mas e boa pratica
    cpi = pis(scale)
    progress += 1/samples*100
    if debug_rate > 0 and debug_clock == 0:
        print("{}%  encontrado: {}".format(int(progress), cpi)) # escusas de tranformar em string de formatares assim, menos duas funcoes que executas aqui
        debug_clock = debug_rate
    piavg += cpi
    debug_clock -= 1
piavg /= samples

print (piavg)

print(time.time() - start_t)

O que fiz deixei comentado para perceberes, ainda estou a estudar maneiras de otimizar mas isto já é um bom começo

8
  • Otimização de expressões muito interessante, vou estudar mais sobre isso. mas eu estava procurando um jeito de executar o interpretador usando todo o poder de processamento, visto que ele só está usando 30 por cento da capacidade máxima do meu computador.
    – user63500
    Commented 28/12/2016 às 12:16
  • 1
    Terias de fazer com multiplas threads, isto como está é um só processo @Jeacom. Já te tento ajudar
    – Miguel
    Commented 28/12/2016 às 12:22
  • 2
    Se você deseja usar mais da capacidade do seu computador, remova as chamadas de print durante a execução. O sistema operacional "aproveita" as operações de IO para liberar a CPU para outras tarefas. Assim, além dessas chamadas fazerem o seu programa demorar mais, ela gera interrupções no fluxo de execução (tempo em que sua CPU provavelmente fica ociosa mesmo). É esse o mesmo motivo pelo qual um while infinito sem um sleep (que dá a tal "folga") leva a CPU rapidamente a 100%. Commented 28/12/2016 às 13:26
  • 1
    De todas as formas, não se preocupe com aumentar o uso aparente da CPU. De fato, quanto menor é esse uso aparente, melhor é o seu algoritmo. Commented 28/12/2016 às 13:28
  • @LuizVieira, Eu estou ciente das chamadas de print, por isso que criei a variável debug_rate, que se definida para zero cessa todas a chamadas de print exceto a final e se definida para outro valor, faz com que o script só chame print de tempos em tempos determinado pela variável. mas achei interessante essa do while, então o while usa mais cpu do que um laço for?
    – user63500
    Commented 28/12/2016 às 19:01
1

Obrigado, com a ajuda de vocês consegui chegar a esse resultado:

from random import random

scale = int(input("quantas amostras ? "))
repeat = int(input("quantas repetiçoes ? "))
pi = 0

def pic(sc):
    p = 0
    points = ([random(),random()] for i in range(sc))
    def dist (p1, p2, dist):
        d = p1 ** 2 + p2 **2
        return d - dist

    for p1, p2 in points:
        if dist(p1,p2,1) < 0:
            p += 1
    p = p * 4 / sc
    return p

print("calculando...")

for _ in range(repeat):
    pi += pic(scale)
pi /= repeat
print (pi)

Esse algoritmo é consideravelmente mais rápido que meus anteriores!!

1
  • Faça alguns testes, mas pode ser que ainda melhore se você trocar o operador de potenciação (**) por uma multiplicação simples (isto é, tente trocar p1 ** 2 por p1 * p1). O ganho tende a ser ínfimo em umas poucas chamadas, mas ele pode se tornar considerável em laços mais longos (por exemplo, testando com o %timeit do iPython a diferença média foi de 304 ns com o ** para 76.9 ns com o * em um laço com apenas 1.000 iterações). Commented 4/01/2017 às 19:25

Você deve fazer log-in para responder a esta pergunta.