这篇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
Sunng (8)
wubuntust (8)
LIGHT (5)
mr.q (5)
aegiryy (4)
花在allocate上的时间很多
[Reply]
pipitu Reply:
February 21st, 2010 at 12:23
是啊，内存分配的确慢
[Reply]
ruby1.8，1.9的如何？
[Reply]
try this:
2
3
size = 100000
a = array.array('i',[0 for i in range(size)])
[Reply]
pipitu Reply:
February 24th, 2010 at 14:12
这个不是显然比list comprehension还慢么……
[Reply]
Sunng Reply:
February 24th, 2010 at 19:39
貌似还真没有能够直接开辟数组的API
可以试试numpy了
[Reply]
consider zeros() function in jython and numpy
[Reply]
这个不是显然比list comprehension还慢么……
[Reply]
楼猪不厚道，一个是动态添加，一个是静态数组，把两件不一样的事情进行比较，能比出结果吗？
你试试这个
li=[0]*n
[Reply]
pipitu Reply:
May 25th, 2010 at 14:12
我擦汗，把这个给忘了…
不过java的vector也是动态添加的说～
[Reply]
li=[0]*n
[Reply]
楼猪不厚道，一个是动态添加，一个是静态数组，把两件不一样的事情进行比较，能比出结果吗？
你试试这个
li=[0]*n
[Reply]