Snowing in my world

Number of View: 514

这篇post的主要由来是某次算法作业误用Python做了无用功，性能完全达不到要求，后来换用Java才搞定。作业是一个经典的算法问题：求最近点对，要求的输入数量级达到百万。Java做出来的结果大约是5秒左右，Python的话就完全废了，原因是其中涉及到庞大的list的new操作。

Python list VS Java array

首先做一个简单的实验，分别计算用Python和Java新建一个list的时间。

Python代码：

li = []
for i in range(size):
    li.append(0)

Java代码:

int[] li = new int[size];

结果对比如下：

size	Python(ms)	Java(ms)
10	0.012	0.002
100	0.045	0.002
1000	0.347	0.005
10000	4.011	0.034
100000	34.541	0.304
1000000	353.420	3.749

二者的时间复杂度都是O(n)，但在常数上相差两个数量级。究其原因，
The time needed to append an item to the list is “amortized constant”; whenever the list needs to allocate more memory, it allocates room for a few items more than it actually needs, to avoid having to reallocate on each call (this assumes that the memory allocator is fast; for huge lists, the allocation overhead may push the behaviour towards O(n*n)).
也就是说，Python中list的append操作仅当空间不够时才另分配一块新的空间，根据平摊分析(Amortized Analysis)原理,创建一个长度为n的list的时间为c*n（c为平摊常数）。而Java的数组的new操作是一次分配一整快空间，这就不难解释为何两者的性能差异如此之大了。

For loop vs List comprehension

实际上，Python提供了另一种更快地创建list的方法：List Comprehension。List comprehensions run a bit faster than equivalent for-loops (unless you’re just going to throw away the result).

li = [ 0 for i in range(size) ]

size	append(ms)	list comprehension(ms)
10	0.012	0.009
100	0.045	0.026
1000	0.347	0.214
10000	4.011	2.228
100000	34.541	21.701
1000000	353.420	221.127

Python list vs Java Vector

Python的list与Java的Vector有些类似，再做一个对比：

Vector list = new Vector();
for(int i=0;i<size;i++)
    list.add(i)

size	Python list(ms)	Java Vector(ms)
10	0.012	0.741
100	0.045	0.778
1000	0.347	1.1108
10000	4.011	3.6601
100000	34.541	21.008
1000000	353.420	81.820

在默认构造函数中，Vector的初始存储能力是10个元素，如果新元素加入时存储能力不足，则以后存储能力每次加倍。每次扩展存储能力时，所有现有的元素都要复制到新的存储空间之中。add操作有可能做了额外的优化，因为时间复杂度曲线并非纯线性的。

总之，在注重性能并需要多次创建较大的list的应用中，Python并不适用。

注：实验环境：
软件：Archlinux(Kernel2.6.32)+Python2.6.4
硬件：CPU 2Ghz*2，RAM 2GB

Refrence:
1. An Introduction to Python Lists
2. PythonSpeed/PerformanceTips