2

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 倍ですが、それ以前は単純に 2 倍になっています。なんでそうなの ？

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 のリスト サイズ: リストの一部をメモリからスワップする必要があります。したがって、経過時間の正確な 2 倍の増加からの少しの隆起。
  • 64M リスト サイズ: 22 の主要なページ フォールトにより、経過時間の増加は 2 倍以上になります。
  • 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) を消費し、OS がスワップ領域を使用し始めると、ディスクから RAM へ、またはその逆にデータをシャッフルすると、プログラムが非常に遅くなります。

于 2013-10-16T13:56:28.470 に答える
0

あなたの Python プロセスが利用可能な物理 RAM を使い果たし、ディスクへのスワップを開始したのではないかと強く思います。

メモリ使用量やページ フォールトの数を監視しながら、最後のテストを再実行します。

于 2013-10-16T13:50:56.057 に答える