3

我有以下程序：

def main():
    print "Running"
    primes = sieve(100000)
    print "Sieve is done"

def sieve(n):
    print "starting sieve"
    primes = []
    times = 0

    numbers = range(2, n):
    print "sieve array filled"

    while len(numbers) > 0:
        current = numbers[0]
        primes.append(current)
        numbers.remove(current)

        times = times + 1
        if (times % 10 == 0):
            print str(times) + "th prime is " + str(current)

        # Remove every multiple
        for i in numbers:
            if (i % current == 0):
                numbers.remove(i)

当找到一个大数的所有素数（比如说一万个）时，我希望能够通过查看输出来了解程序有多远。所以我决定每十个素数打印一次。但是，当打印出来时，它会等到程序的最后才打印它。我在sys.stdout.flush()打印语句之后立即添加，但没有任何区别。然后我尝试运行脚本，python -u <file name>但仍然没有任何区别。

这就是我得到的输出：

Running
starting sieve
sieve array filled

然后大约一分钟后，立即显示其余的输出。

为什么我不能关闭缓冲区？我正在尝试尽可能少地修改代码。

4

3 回答 3

3

测试了一些东西后，我不确定您的问题实际上是输出缓冲，这只是您的算法的行为。尝试在循环current顶部附近打印while，您会发现早期的数字需要很长时间才能完成，然后随着numbers越来越短，每个新值的current处理速度都会更快，您会开始看到素数弹出。

尝试：

while len(numbers) > 0:
    current = numbers[0]
    print current
    primes.append(current)
    numbers.remove(current)
于 2012-11-29T00:23:30.630 回答
2

这么慢的原因是您从数字中删除元素的循环：

    # Remove every multiple
    for i in numbers:
        if (i % current == 0):
            numbers.remove(i)

每次删除一个数字时，Python 都必须将删除的那个数字后面的所有元素移回一个位置。每次删除都是 O(n)*，并且您执行 O(n) 次删除，因此此步骤的每次迭代都需要 O(n^2) 时间。

如果你用列表推导替换它，那么 Python 从旧列表构建一个新列表——不涉及移动——这是一个 O(n) 操作。这是我执行该步骤的方式：

    # Remove every multiple
    numbers = [i for i in numbers if (i % current) != 0]

通过此更改，您的代码对我来说运行得更快。它在 5 秒内完成，并且没有输出缓冲问题。

*这里有一个很好的 Python 列表操作的时间复杂度表。

于 2012-11-29T00:38:28.493 回答
0

尝试使用sys.stdout.write而不是print. 这应该更好地与sys.stdout.flush.

于 2012-11-29T00:10:17.840 回答