30/05/2006 Medindo tempo de execução de scripts Python
Numa aula eu estava explicando a técnica de programação “Divisão e Conquista”, que consiste em dividir um problema grande em pequenos subproblemas e resolvê-los separadamente de forma que o resultado deles seja o resultado do problema original. Um exemplo de algoritmo desenvolvido nessa técnica é o de busca binária, onde o espaço de busca é sempre dividido pela metade, diminuindo o tempo de pesquisa. Para ilustrar a diferença desenvolvi dois scripts em Python para mostrar o tempo de execução de um algoritmo de pesquisa usando “força bruta” e a pesquisa binária. Para isso usei o módulo timeit do Python. Com este módulo é possÃvel medir o tempo de execução de pequenos trechos de código. Abaixo os códigos usados:
Pesquisa Binária (Divisão e Conquista)
Comparação dos tempos de execução
Como neste caso são poucos dados a serem pesquisados a diferença de tempo não é tão grande, mas é visÃvel o suficiente para ilustrar aos alunos a diferença.
- 2comentários
- Posted under codes, home, python
Permalink # elton luÃs minetto » Blog Archive » Disciplina interessante disse
[...] Eu sempre me divirto com as disciplinas que ministro. É a chance que tenho de programar algo cientÃfico, coisa que infelizmente não faço em meu dia a dia. Essas disciplinas já renderam alguns textos aqui no meu site também: Web Services – parte 1 e parte 2 Grids Eclipse, PHP e CVS Classe genérica para trabalhar com tabelas Conjuntos em Python Padrões algorÃtmicos em python Medindo tempo de execução de scripts Python Método de Monte Carlo DistribuÃdo Material Curso Python PVFS Monte Carlo DistribuÃdo usando Pyro [...]
Permalink #
Alcemir
disse
Bom gostei do post pois estou desenvolvendo um trabalho para a disciplina Projeto e análise de algoritmos do curso de ciência da computação da universidade federal do piauà e preciso dessa função de medir o tempo.
Porém quando eu fui executar estes códigos, eu obtive o seguinte erro e não consegui resolvê-lo.
Você poderia me enviar uma possÃvel solução??
ps.: caso afirmativo, peço que envie o mais breve possÃvel pois tenho urgência na entrega do trabalho.
~~~~~~~~~~~~
Traceback (most recent call last):
File “C:\Users\asantos\ECLIPSEworkspace\comparacao\src\root\cmp.py”, line 4, in
x = t.repeat() # o repeat vai executar 3 vezes o script e guardar o resultado de cada execucao
File “C:\Python25\lib\timeit.py”, line 188, in repeat
t = self.timeit(number)
File “C:\Python25\lib\timeit.py”, line 161, in timeit
timing = self.inner(it, self.timer)
File “”, line 6, in inner
NameError: global name ‘buscaForcaBruta’ is not defined