python的性能问题

贝壳最近在一个朋友的网站上看到了关于SICP零钱兑换问题的python求解，使用了记忆机制，然后他给出了代码。然而他的代码计时上有点小问题，也没有用包装器(奇怪的是，有写)，而且python的栈深度有限。因此贝壳做了几个修改的版本，需要测试下性能，下面就是关于性能的几个问题和过程。
本文详细论述了python语言下和C++语言下使用各种方法测试代码性能的方法，以及粗略的关于两种语言不同算法性能对比。
原始的python代码是这样的：
def change_coins(money):
first_denomination = {
1:1, 2:5,
3:10, 4:25,
5:50,
}
def cc((amount, kinds_of_coins)):
if amount == 0:
return 1
elif amount < 0 or kinds_of_coins == 0:
return 0
else:
return cc((amount, kinds_of_coins - 1)) \
+ cc((amount - first_denomination[kinds_of_coins], kinds_of_coins))
print "change_coins return %s" % cc((money, 5));
return ;
利用记忆原理包装后是这样的：
def memoiza(fun):
cache = {}
def proc ( *arg ):
if cache.has_key(arg):
return cache[arg]
else:
x = fun( *arg )
cache[arg] = x
return x
return proc

def decorator_change_coins(money):
first_denomination = {
1:1, 2:5,
3:10, 4:25,
5:50,
}
@memoiza
def cc(amount, kinds_of_coins):
if amount == 0:
return 1
elif amount < 0 or kinds_of_coins == 0:
return 0
else:
return cc(amount, kinds_of_coins - 1) \
+ cc(amount - first_denomination[kinds_of_coins], kinds_of_coins)
print "decorator_change_coins return %s" % cc(money, 5);
return ;
不记忆，利用栈模拟递归展开是这样的：
def native_change_coins(money):
first_denomination = {
1:1, 2:5,
3:10, 4:25,
5:50,
}
stack = [(money, 5)];
rslt = 0;
while len (stack) > 0:
param = stack.pop ();
if param[0] == 0:
rslt += 1;
continue;
elif param[0] < 0 or param[1] == 0:
continue;
else:
stack.append ((param[0], param[1] - 1));
stack.append ((param[0] - first_denomination[param[1]], param[1]));
continue;
print "native_change_coins return %s" % rslt;
return ;

贝壳主要需要测试上面三个代码的执行效率和瓶颈，所以贝壳用的主代码是这样的：
import time
import timeit
import profile

def test_func(f):
f (300);

if __name__ == "__main__":
t = timeit.Timer("test_func (change_coins)", "from __main__ import *");
print min(t.repeat (5, 1));

t = timeit.Timer("test_func (decorator_change_coins)", "from __main__ import *");
print min(t.repeat (5, 1));

t = timeit.Timer("test_func (native_change_coins)", "from __main__ import *");
print min(t.repeat (5, 1));

profile.run("test_func (change_coins)");
profile.run("test_func (decorator_change_coins)");
profile.run("test_func (native_change_coins)");

下面是部分结果：
change_coins return 9590
1.22809910198
decorator_change_coins return 9590
0.00217178440277
native_change_coins return 9590
2.69215193551

以上是时间测试结果，使用timeit模块来测试运行时间，重复5次，取最小值。具体原理可以看dive into python，详细请看上面的代码。从结果中我们可以看到，使用记忆技术后，性能提升了500多倍，这是符合规律的。然而使用了集合模拟栈之后，性能大幅下降。下面我们看看为什么。

change_coins return 9590
1292596 function calls (6 primitive calls) in 13.591 CPU seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.059 0.059 0.059 0.059 :0(setprofile)
1 0.000 0.000 13.533 13.533 :1()
1 0.000 0.000 13.533 13.533 amount.py:102(test_func)
1292591/1 13.531 0.000 13.531 13.531 amount.py:11(cc)
1 0.001 0.001 13.533 13.533 amount.py:5(change_coins)
0 0.000 0.000 profile:0(profiler)
1 0.000 0.000 13.591 13.591 profile:0(test_func (change_coins))

decorator_change_coins return 9590
2494 function calls (881 primitive calls) in 0.027 CPU seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
873 0.004 0.000 0.004 0.000 :0(has_key)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 0.027 0.027 :1()
1 0.000 0.000 0.027 0.027 amount.py:102(test_func)
1 0.000 0.000 0.000 0.000 amount.py:51(memoiza)
873/1 0.013 0.000 0.026 0.026 amount.py:53(proc)
1 0.001 0.001 0.027 0.027 amount.py:62(decorator_change_coins)
742/1 0.009 0.000 0.026 0.026 amount.py:68(cc)
0 0.000 0.000 profile:0(profiler)
1 0.000 0.000 0.027 0.027 profile:0(test_func (decorator_change_coins))

native_change_coins return 9590
3877778 function calls in 38.798 CPU seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
1292590 5.824 0.000 5.824 0.000 :0(append)
1292592 5.960 0.000 5.960 0.000 :0(len)
1292591 6.076 0.000 6.076 0.000 :0(pop)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 38.798 38.798 :1()
1 0.000 0.000 38.798 38.798 amount.py:102(test_func)
1 20.938 20.938 38.798 38.798 amount.py:80(native_change_coins)
0 0.000 0.000 profile:0(profiler)
1 0.000 0.000 38.798 38.798 profile:0(test_func (native_change_coins))
以上是白盒分析结果，使用profile测试，主要分析函数的调用花费。具体可以参考http://www.sqlite.com.cn /MySqlite/11/480.Html。从上面的报表中，我们可以看出，最初的函数执行时间全消耗在了cc上。而记忆后，则是proc和cc基本对半，有的时候has_key测试也花点时间。这表示cc花费的时间大幅下降，记忆技术则花了比较多的时间。而模拟的呢？大部分时间都花在了 append,len,pop这三个函数上！这说明原始集合的效率严重制约了模拟效率。如果要提升性能的话，使用其他的集合吧。
另外贝壳又用C++写了一个，如下：

const int coin_map[] = {
1, 5, 10, 25, 50
};
const int coin_count = 5;

int cc (int amount, int kind_of_coins)
{
if (amount == 0)
return 1;
if (amount < 0 || kind_of_coins <= 0)
return 0;
return cc (amount, kind_of_coins - 1) + cc (amount - coin_map[kind_of_coins - 1], kind_of_coins);
}

int dd (int amount, int kind_of_coins)
{
if (amount == 0)
return 1;
if (amount < 0 || kind_of_coins <= 0)
return 0;
int rslt = 0;
for (int i = 0; i <= amount / coin_map[kind_of_coins - 1]; ++i)
rslt += dd (amount - i * coin_map[kind_of_coins - 1], kind_of_coins - 1);
return rslt;
}

class keys{
public:
int amount;
int kind_of_coins;
keys (int amount_p, int kind_of_coins_p):
amount(amount_p), kind_of_coins(kind_of_coins_p)
{}
bool operator == (const keys & k) const{
return (amount == k.amount && kind_of_coins == k.kind_of_coins);
}
bool operator < (const keys & k) const{
if (kind_of_coins == k.kind_of_coins)
return amount < k.amount;
return kind_of_coins < k.kind_of_coins;
}
};

map mCache;

int ee (int amount, int kind_of_coins)
{
if (amount == 0)
return 1;
if (amount < 0 || kind_of_coins <= 0)
return 0;
keys k (amount, kind_of_coins);
map::iterator iter = mCache.find(k);
if (iter != mCache.end ())
return iter->second;
int rslt = 0;
for (int i = 0; i <= amount / coin_map[kind_of_coins - 1]; ++i)
rslt += dd (amount - i * coin_map[kind_of_coins - 1], kind_of_coins - 1);
mCache.insert(pair(k, rslt));
return rslt;
}

int _tmain(int argc, _TCHAR* argv[])
{
const int loop_times = 300;
clock_t s = clock();
printf ("kind of coins: %d\n", cc (loop_times, coin_count));
printf ("times:%d\n", clock () - s);

s = clock();
printf ("kind of coins: %d\n", dd (loop_times, coin_count));
printf ("times:%d\n", clock () - s);

s = clock();
printf ("kind of coins: %d\n", ee (loop_times, coin_count));
printf ("times:%d\n", clock () - s);
return 0;
}
注意到主函数中，使用的是clock来计量时间。如果C++下要做白盒性能测试就比较麻烦，需要用精确计时函数和宏。需要的可以单独和我联系。下面是部分计算结果，cc的和ee的，没有dd的。
300的计算结果
kind of coins: 9590
times:62
kind of coins: 9590
times:46
1000的计算结果
kind of coins: 801451
times:15953
kind of coins: 801451
times:11000
单位，ms。
原生的效率差异是20倍，用了缓存后性能只有略略上升？！反而是python比较快？
看来C++下的map效率也不高，要用hash_map才好。
倒是栈长度好很多，贝壳估计是131072次调用，大约是16384分。

运气真好

昨天晚上吃完晚饭，觉得应该勤快点，还指不定什么时候回去呢，把衣服洗了。刚刚把衣服放进去，电话过来，说系统出问题了，要赶快去看看。于是，贝壳赶快出门，去看看系统有什么问题。
进去被一顿狂说，怎么这么不稳定，怎么解决。贝壳一个头两个大。马上去看看什么问题，一看把我气个半死。原来新华社的稿件都是一个xml，一个txt，一个图片，主文件名一样，贝壳的程序也是基于这个原理写的。现在到好，只有图片没有xml，或者只有xml没有图片。这叫贝壳做个P啊！据说是因为新华社要推新格式，所以老格式不怎么支持了。问题是，上面说保奥保奥，居然奥运期间来这手，这不是要整死人么？而且通知都没有的，要不过来看，黑锅就我背定了。
抱怨归抱怨，贝壳还是赶快改程序，做了个入新格式的。进度还挺快，虽然差异一堆，但是做到早上三点半基本就做好了。到实验机器上一跑，全部通过。然后到生产环境中一炮——全部报错。
OK，下面可就是贝壳无能为力的了。毕竟数据库那里应该都是一样的，而且也不是贝壳写的，无法调试。于是今天只有这样，回去睡觉。走到电梯里面，贝壳觉得不对，味道不对，一股臭脚的味道。这种味道只有两种可能，一种是中国男足来过了，一种是下雨。出门一看，果然，大雨滂沱。最要命的是，贝壳只带了两套衣服，还有套正在水池里面泡着～～～
于是贝壳一路狂奔，跑过去没两步，哗的一声，贝壳就不知道陷到什么里面去了。吓了一跳，赶快站直，包举高。仔细看看，原来前面马路修路，旁边的土还没有填完整，给水一冲就变成了泥浆坑。贝壳就是陷到这里去了，水刚好漫过小腿肚。
慢慢爬上来，然后贝壳就不敢跑了。前面毕竟还是有几个没有完成的井的。万一掉里面去，连申诉都不会有人管的，毕竟那是还没修好的工地。于是慢慢慢慢走回去，到宾馆的时候全身湿透，外带两脚泥。而且两套衣服全报销了，连第二天吃饭怎么出门都不知道～～～
奥运期间，这个运气还真是——无敌了。

最近悟到了一个道理

贝壳问上帝，中国房价什么时候下来。上帝说，通涨结束，或者居民消费上去就下来了。
贝壳问上帝，中国居民消费什么时候上去。上帝说，全民保障体系搞好就上去了。
贝壳问上帝，中国什么时候结束通涨，搞好全民保障体系呢？上帝哭着说，我看不到那天了。

上面是拿中国足球的玩笑改的一个玩笑，不过贝壳真的悟到了房价高的原因。通涨乱高无比，保障一塌糊涂，赚了钱不敢花，也不能放，当然只有买房了。房价上涨，通涨更加高高高。

程序员入门的12个问题

以下题目是应一个朋友问而写的，适用于刚刚入门有志或者有需要做程序的朋友的题目。题目脱胎于日常编程中常见的一些问题，很多是贝壳实际碰到问题的变形。题目不注重所用语言，每道题目可以用不同语言解决。有意思向计算机方向发展的可以试试用不同语言来解决，看看哪种语言最方便解决这种问题。如果打算增加难度的话，请使用C++来做，并且尽量抽象复用。在这个过程中积累下来的可复用代码会对以后编程有很大帮助。

1.读出文件中的以下格式内容，计算逆矩阵，并按照同样格式输出。
1 2 4.5
3 0 1
9 5 2
数字间以空格分割，行以回车分割。
难点：
输入和输出应当可以选择是键盘输入还是文件输入，输出到屏幕还是输出到文件。
逆矩阵计算中有可能求不出，出现除零。设法避免直接的报错。
评价：
很中规中矩的一个问题，有点竞赛的味道。只要做过程序的人一般不会失手。

2.某个XML，其中记录了一些信息。信息是按照时间-地点-人物的顺序记录的，例子如下：



...



现在需要你颠倒一下，变成这样的：



...



难点：
看看能想出多少解决问题的方法。
试试尽量减小内存消耗。
评价：
解决问题的方法很多，比较一下这些方法的优劣。
有一年以上程序经验的就可以最终解决，但要解决的比较完善需要两到三年经验。

3.下载google的首页，跟踪二级连接(二级连接，就是首页中连接指向的页面，上面连接指向的页面)。
并计算其中所有页面，显示出的非空白字符的个数。(显示的文字中的非空白字符)
难点：
试试看跟踪js脚本链接。
登陆后的google首页是不一样的，包括提示，语言类型，设法统计登陆后的首页。
如果是多级呢？
评价：
宽度优先和深度优先算法的应用，对集合运算有一定要求。
重点在于获取和处理html页面的方法。
一年以上即可解决，完善程度和技术水平关系不大。

4.运行两个程序，A和B，将A的输出输入到B中。
难点：
需要等待A的输出和B的输入，以及程序的终止条件。
评价：
需要对系统熟悉，知道管道和用法。知道进程间交互的API。
需要研究过系统，程序水平没有要求。

5.遍历某个目录，找出其中的特定图片文件。
难点：
怎么分析图片文件？文件名是比较粗略的方法，更好的是使用文件签名分析。
下次遍历的时候速度怎么提高(假定文件不变化)。
评价：
还是深度和宽度搜索题目，分析文件是难点。
扩展要求对于数据缓存有一定要求。
一年以上即可解决，文件签名分析看个人水平。

6.监视某个目录的变化，将新加入的mp3的相关信息(IDv3)邮件发给我。
难点：
怎么监视目录变化？
怎么提取MP3的内容？
怎么发邮件？
怎么保证不漏内容。
评价：
要对系统熟悉，了解mp3格式或者能够自行寻找库扩展语言。
了解邮件发送协议，或者能使用系统库发送邮件。
两年以上可解决，完善需三年以上水准。

7.写一个程序，可以计算加减乘除，支持括号。
难点：
让你的程序算算1+2*3，看看是多少。正确应当是7，设计不良是9。
看看你的程序，2/6*3得多少，是不是1.0(最好是1)。
让你的程序设法支持乘方和函数。
评价：
对数据结构和算法要求很高。
一年以上可解决，要扩展支持算符和算法，需要三年水准。

8.画一只乌龟，保存为图片。
难点：
让用户动手画？
试试保存为各种格式的图片。
评价：
实用项目，按照书本教程最多12小时就可以掌握。
然而需要自行解决并做好，至少一年以上。

9.写一个小桌球程序，让一个白球设法打落一个黑球。
难点：
注意屏幕闪烁。
写个9球游戏如何？
评价：
对物理知识有一定要求，对游戏常识(双缓冲)有一定了解。
扩展要求了解桌球规则。
两年以上水准。

10.写个小的管帐系统，告诉我这个月你钱是怎么花出去的。
难点：
随时记账。
评价：
系统并不难做，然而考虑实用性后，很少有系统能得到好成绩。

11.写一个小程序，向一个文件的第11字节写一个A，并将程序编译好后的大小控制在2K以内。(不得使用虚拟，脚本语言完成)
难点：
控制大小。
评价：
对可执行程序的结构和优化，系统库结构有相当了解，这是为C++语言设计的题目。
三年以上水准。

12.写个小阅读器。
难点：
能读HTML么？繁体呢？
小心编码问题。
ZIP包内的文件能读么？
评价：
最终的实用项目。
一年就可以做，但是做好至少要三年以上水准。