Python中的基準測試：爲什麼我的代碼在重複時運行速度較慢？

我有一個簡單Sieve of Eratosthanes執行如下命令：Python中的基準測試：爲什麼我的代碼在重複時運行速度較慢？

# Generate all primes less than k 
def sieve(k): 
    s = [True] * k 
    s[0] = s[1] = False 
    for i in range(4, k, 2): 
     s[i] = False 

    for i in range(3, int(sqrt(k)) + 2, 2): 
     if s[i]:    
      for j in range(i ** 2, k, i * 2): 
       s[j] = False 

    return [2] + [ i for i in range(3, k, 2) if s[i] ]

我被下10M反覆生成素標杆驗證碼：

st = time() 
for x in range(1000): 
    rt = time() 
    sieve(10000000) 
    print "%3d %.2f %.2f" % (x, time() - rt, (time() - st)/(x + 1))

我很困惑，按照試運行的增加所花費的時間顯着：

run t avg 
    0 1.49 1.49 
    1 1.79 1.66 
    2 2.23 1.85 
    3 2.72 2.07 
    4 2.67 2.20 
    5 2.87 2.31 
    6 3.05 2.42 
    7 3.57 2.56 
    8 3.38 2.65 
    9 3.48 2.74 
10 3.81 2.84 
11 3.75 2.92 
12 3.85 2.99 
13 4.14 3.07 
14 4.02 3.14 
15 4.05 3.20 
16 4.48 3.28 
17 4.41 3.34 
18 4.19 3.39 
19 4.22 3.43 
20 4.65 3.49

但是，將每個range的實例更改爲xrange消除了這個問題：

run t avg 
    0 1.26 1.26 
    1 1.23 1.28 
    2 1.24 1.27 
    3 1.25 1.26 
    4 1.23 1.26 
    5 1.23 1.25 
    6 1.25 1.25 
    7 1.25 1.25 
    8 1.23 1.25 
    9 1.25 1.25 
10 1.24 1.25

爲什麼會出現這種情況？它真的都是GC的開銷嗎？在20次運行後3次減速似乎很多...

來源

2012-09-16 verdesmarald

p.s. ['timeit']（http://docs.python.org/library/timeit.html）是更簡單的計時代碼。 – nneonneo

不僅僅是垃圾收集，內存分配以及所有這些範圍。當你不需要列表時使用'range'是很浪費的。這就是爲什麼Python 3的'range'像Python 2的'xrange'那樣工作的原因。那麼，如果你真的需要一個列表，你可以寫'list（range（n））'。 –

在每次運行幫助後都運行'gc.collect'嗎？ – nneonneo

這不是一個答案，而只是一個有組織的實驗的集合。

這真的很吸引人。 Python的內存分配器似乎有一些非常可疑的事情發生。

這裏是我試圖減少測試用例：

def sieve(k): 
    s = [True] * k 

    for i in xrange(3, int(sqrt(k)) + 2, 2): 
     for j in range(i ** 2, k, i * 2): 
      s[j] = False 

    return [ i for i in range(3, k, 2) if s[i] ] 

st = time() 
for x in range(1000): 
    rt = time() 
    sieve(10000000) 
    print "%3d %.2f %.2f" % (x, time() - rt, (time() - st)/(x + 1))

需要注意的是，如果我刪除if s[i]，使內range的xrange，使返回值的發電機，或者在內部for循環pass（或作它s[j] = True），行爲消失，時間平坦。

隨着函數運行，Python的內存使用量穩步增加，最終達到一個平臺（此時運行時間也開始穩定在約250％的初始值）。

我的假設是大量的內存（大小遞減）加上最終數組會導致某種最壞情況的堆碎片，使得很難繼續分配對象。

我的建議是製作一個簡化的測試用例，並將其作爲Python開發人員（bugs.python.org）的一個bug。

來源

2012-09-16 19:12:54 nneonneo

Python中的基準測試：爲什麼我的代碼在重複時運行速度較慢？

回答

相關問題