KEEP MOTIVATED

这篇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];

结果对比如下：
[table id=1 /]
二者的时间复杂度都是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) ]

[table id=2 /]

Python list vs Java Vector

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

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

[table id=3 /]
在默认构造函数中，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