2

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

问题：

64000000 的时间是 32000000 的 6 倍，但在此之前，时间只是翻了一番。为什么这样 ？

4

3 回答 3

6 
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)会随着列表的增长为列表分配额外的空间，这种情况只会变得更糟。

于 2013-10-16T16:04:08.643 回答
4

根据effbot：

将一个项目附加到列表所需的时间是“摊销常数”；每当列表需要分配更多内存时，它会为一些项目分配比实际需要更多的空间，以避免在每次调用时重新分配（这假设内存分配器很快；对于大型列表，分配开销可能会推动对O(n*n))的行为。

（我的重点）。

当您将更多项目附加到列表中时，重新分配器将尝试保留越来越多的内存。一旦你消耗了所有的物理内存 (RAM) 并且你的操作系统开始使用交换空间，数据从磁盘到 RAM 或反之亦然的洗牌将使你的程序非常慢。

于 2013-10-16T13:56:28.470 回答
0

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

重新运行最后一个测试，同时注意它的内存使用和/或页面错误的数量。

于 2013-10-16T13:50:56.057 回答