Python列表附加计时

Question

cat /proc/meminfo

内存总计：3981272 kB

我用python运行了这个简单的测试

#!/usr/bin/env python
import sys
num = int(sys.argv[1])
li = []
for i in xrange(num):
    li.append(i)


$ time ./listappend.py 1000000

real    0m0.342s
user    0m0.304s
sys 0m0.036s

$ time ./listappend.py 2000000

real    0m0.646s
user    0m0.556s
sys 0m0.084s

$ time ./listappend.py 4000000

real    0m1.254s
user    0m1.136s
sys 0m0.116s

$ time ./listappend.py 8000000

real    0m2.424s
user    0m2.176s
sys 0m0.236s

$ time ./listappend.py 16000000

real    0m4.832s
user    0m4.364s
sys 0m0.452s

$ time ./listappend.py 32000000

real    0m9.737s
user    0m8.637s
sys 0m1.028s

$ time ./listappend.py 64000000

real    0m56.296s
user    0m17.797s
sys     0m3.180s

问题：

比之前的六百六十万倍翻了一番。为什么？在

Answer 1

根据effbot：

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)).

（我的重点）。在

当您向列表添加更多项时，reallocator将尝试保留更大的内存量。一旦您用完了所有的物理内存（RAM），并且您的操作系统开始使用交换空间，数据从磁盘到RAM的洗牌（反之亦然）将使您的程序非常缓慢。在

Answer 2

TL;DR - Due to RAM being insufficient & the memory being swapped out to secondary storage.

我用不同大小的盒子运行程序。这是结果

^{pr2}$

• User time程序以用户身份运行的时间。（运行用户逻辑）
• System time程序作为系统执行的时间。（即系统调用所花费的时间）

• Elapsed time程序执行的总时间。（包括等待时间….）

  Elapsed time = User time + System Time + time spent waiting
  

• 当内存页不在RAM中时发生Major Page Fault必须从辅助设备（如硬盘）中获取。

• 16M列表大小：列表大部分在内存中。因此没有页面错误。

• 32M列表大小：部分列表必须从内存中交换出来。因此，所用时间的确切增加了两倍。在
• 64M列表大小：由于22个主要页面错误，运行时间增加了两倍多。在
• 128M列表大小：运行时间从14秒增加到超过27分钟！！等待时间将近26分钟。这是由于大量的pagefaults（389184）造成的。还要注意，由于大量的等待时间，CPU使用率从99%下降到3%。在

正如unutbu指出的，python解释器在列表增长时为列表分配一个O(n*n)额外空间，这种情况只会恶化。在

Answer 3

我强烈怀疑您的Python进程耗尽了可用的物理RAM，并开始交换到磁盘。在

重新运行上一个测试，同时注意内存使用情况和/或页面错误数。在