优化Python代码

Question

我一直在研究InterviewStreet.com上的编码挑战之一,我遇到了一些效率问题.任何人都可以建议我可以在哪里更改代码,以使其更快,更有效？

这是代码

如果您有兴趣,这是问题陈述

Answer 1

如果你的问题是关于优化python代码(我认为它应该是这样的话),那么你可以做各种各样的无法解决的事情,但首先:

你可能不应该痴迷优化python代码!如果您正在使用最快的算法来解决您正在尝试解决的问题,并且python没有足够快地执行它,您可能应该使用不同的语言.

也就是说,你可以采取几种方法(因为有时你真的想让python代码更快):

简介(先做这个!)

有许多方法可以分析python代码,但我会提到两个:(cProfile或profile)模块,和PyCallGraph.

CPROFILE

这是你应该实际使用的,虽然解释结果可能有点令人生畏.它的工作原理是记录何时输入或退出每个功能,以及调用功能是什么(以及跟踪异常).

你可以在cProfile中运行一个函数,如下所示:

import cProfile
cProfile.run('myFunction()', 'myFunction.profile')

然后查看结果:

import pstats
stats = pstats.Stats('myFunction.profile')
stats.strip_dirs().sort_stats('time').print_stats()

这将显示大部分时间花费在哪些功能上.

PyCallGraph

PyCallGraph提供了一个最漂亮,也许是最简单的分析python程序的方法 - 它是一个很好的介绍,可以了解程序中的时间花费在哪里,但它会增加大量的执行开销

要运行pycallgraph:

pycallgraph graphviz ./myprogram.py

简单!你得到一个png图形图像作为输出(也许一段时间后......)

使用库

如果你试图在python中做一些模块已经存在(甚至可能在标准库中),那么请使用该模块!

大多数标准库模块都是用C语言编写的,它们的执行速度比二等分搜索的等效python实现快几百倍.

让口译员尽可能多地完成您的工作

解释器会为你做一些事情,比如循环.真？是! 您可以使用map,reduce以及filter关键字显著加快紧凑循环:

考虑:

for x in xrange(0, 100):
    doSomethingWithX(x)

VS:

map(doSomethingWithX, xrange(0,100))

很明显,这可能会更快,因为解释器只需要处理一个语句,而不是两个,但这有点模糊......实际上,这有两个原因:

• 所有流量控制(我们已完成循环...)在解释器中完成
• doSomethingWithX函数名称只解析一次

在for循环中,每次循环python都必须检查doSomethingWithX函数的确切位置!即使有缓存,这也是一个开销.

请记住,Python是一种解释语言

(请注意,本节实际上是关于微小的优化,你不应该影响你的正常,可读的编码风格!)如果你来自编译语言的编程背景,如c或Fortran,那么关于不同python语句的性能可能会令人惊讶:

try:价格便宜,if价格昂贵

如果您有这样的代码:

if somethingcrazy_happened:
     uhOhBetterDoSomething()
else:
     doWhatWeNormallyDo()

而doWhatWeNormallyDo()将抛出如果有什么疯狂的事例外,那么这将是更快的这样的安排你的代码:

try:
    doWhatWeNormallyDo()
except SomethingCrazy:
    uhOhBetterDoSomething()

为什么？口译员可以直接潜入并开始做你通常做的事情; 在第一种情况下,每次执行if语句时,解释器都必须查找符号,因为该名称可能引用自上次执行语句以来的不同内容!(以及名称查找,特别是如果somethingcrazy_happened它global可以是非常重要的).

你的意思是谁？

由于名称查找的成本,在函数中缓存全局值也可以更好,并将简单的布尔测试烘焙到这样的函数中:

未经优化的功能:

def foo():
    if condition_that_rarely_changes:
         doSomething()
    else:
         doSomethingElse()

优化的方法,而不是使用变量,利用解释器正在对函数进行名称查找的事实!

当条件成立时:

foo = doSomething # now foo() calls doSomething()

当条件变为假时:

foo = doSomethingElse # now foo() calls doSomethingElse()

PyPy

PyPy是一个用python编写的python实现.当然这意味着它将运行代码无限慢？好吧,不.PyPy实际上使用Just-In-Time编译器(JIT)来运行python程序.

如果您不使用任何外部库(或您使用的库与PyPy兼容),那么这是一种非常简单的方法(几乎可以肯定)加速程序中的重复性任务.

基本上,JIT可以生成代码,这些代码将执行python解释器所能实现的功能,但速度要快得多,因为它是针对单个案例生成的,而不是必须处理每个可能的合法python表达式.

在哪里看下一个

当然,你应该看到的第一个地方是改进你的算法和数据结构,并考虑诸如缓存之类的东西,或者甚至你是否需要首先做这么多,但无论如何:

• python.org wiki的这个页面提供了很多关于如何加速python代码的信息,尽管其中一些有点过时了.

• 这是关于优化循环的BDFL本人.

有很多东西,即使是我自己错过的有限经验,但这个答案已经足够长了!

这完全基于我自己最近使用的一些python代码的经验,这些代码还不够快,我想再次强调,我并不认为我所建议的任何内容实际上是一个好主意,有时候不过,你必须......