7

我有一个简单的 Eratosthanes 筛实现，如下所示：

# 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 倍似乎很多......

4

1 回答 1

1

这（还）不是一个答案，而只是一个有组织的实验的集合。

这很迷人，真的。似乎 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]，使内部rangean xrange，使返回值成为生成器，或者pass在内部for循环中（或 make it s[j] = True），则行为消失并且时间平缓。

Python 的内存使用随着函数的运行而稳步增加，最终达到一个平台期（此时运行时间也开始平台期，大约为初始值的 250%）。

我的假设是，大量的内部ranges（大小减小），加上最终的数组，会导致某种最坏情况下的堆碎片，使得继续分配对象变得非常困难。

我的建议是制作一个简化的测试用例并将其作为一个错误提交给 Python 开发人员 (bugs.python.org)。

于 2012-09-16T19:12:54.143 回答