Python列表附加时间

Question

cat /proc/meminfo

MemTotal: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

题:

64000000的时间是32000000的6倍,但在此之前,时间只是倍增.为什么这样 ？

Answer 1

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

我在盒子上运行了不同大小的程序.结果如下

/usr/bin/time ./test.py 16000000
2.90user 0.26system 0:03.17elapsed 99%CPU 513480maxresident
0inputs+0outputs (0major+128715minor)pagefaults

/usr/bin/time ./test.py 32000000
6.10 user 0.49 system 0:06.64 elapsed 99%CPU 1022664maxresident
40inputs (2major+255998minor)pagefaults

/usr/bin/time ./test.py 64000000
12.70 user 0.98 system 0:14.09 elapsed 97%CPU 2040132maxresident
4272inputs (22major+510643minor)pagefaults

/usr/bin/time ./test.py 128000000
30.57 user 23.29 system 27:12.32 elapsed 3%CPU 3132276maxresident
19764880inputs (389184major+4129375minor)pagefaults

• User time程序作为用户运行的时间.(运行用户逻辑)
• System time程序作为系统执行的时间.(即在系统调用中花费的时间)

• Elapsed time程序执行的总时间.(包括等待时间..)

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

• Major Page Fault 当内存页不在RAM中并且必须从硬盘等辅助设备获取时发生.

• 16M列表大小:列表主要在内存中.因此没有页面错误.

• 32M列表大小:列表的一部分必须换出内存.因此,经过一段时间的精确两倍增加就会产生一点点冲击.
• 64M列表大小:由于22个主要页面错误,经过时间的增加超过两倍.
• 128M列表大小:经过的时间从14秒增加到超过27分钟!等待时间差不多是26分钟.这是由于大量的页面错误(389184).另外请注意,由于大量的等待时间,CPU使用率从99%下降到3%.

由于unutbu指出python解释器O(n*n)为列表分配额外的空间,因为它们的增长情况只会恶化.