2

以下程序（在函数 prime 内）的运行时间为 110.726383227 秒

如果我运行相同的程序而不将其包装在一个函数（素数）中，它的运行时间是 222.006502634 秒

通过将其包装在一个函数中，我实现了显着的性能改进。

还有没有可能提高这个程序的效率？

# This is a program to find sum of prime numbers till 2 billion

def prime():
import time
start_time = time.clock()

num = 2
j=1
tot_sum = 0

for num in xrange(2,2000000): 
    count = 0
    for j in xrange(1,int(num**0.5)+1): # checking from 1 to sqrt(n)+1
        if(num % j == 0):
            count = count+1

    if(count == 1):
        tot_sum = tot_sum + num

print "total sum is %d" % tot_sum

print time.clock() - start_time, "seconds"
4

2 回答 2

1

如果您想在没有外部库的情况下解决它，您可以进行一些明显的改进：

def prime():
    import time
    start_time = time.clock()

    tot_sum = 2

    for num in xrange( 3, 2000000, 2 ): 
            isPrime = True
            for j in xrange(3, int( num ** 0.5 ) + 1, 2 ):
                if( num % j == 0 ):
                    isPrime = False
                    break

            if isPrime:
                tot_sum = tot_sum + num

    print "total sum is %d" % tot_sum

    print time.clock() - start_time, "seconds"

prime()

不检查大于 2 个偶数，如果找到一个则不检查所有除数。您的原始代码在我的机器上运行时间为 172.924809 秒，而我的运行时间为 8.492169 秒。

如果允许使用外部库，我建议gmpy2：

def prime():
    from gmpy2 import is_prime
    import time
    start_time = time.clock()

    print "total sum is %d" % (sum(filter(is_prime, xrange(3,2000000,2)))+2)

    print time.clock() - start_time, "seconds"

prime()

这在 1.691812 秒内运行

于 2013-10-13T19:25:07.760 回答
0

这可能与 python 如何解析变量有关。粗略地说，当你输入一个函数时，python 会创建一个新的命名空间，它本质上映射到该函数本地的所有变量。然后 Python 可以使用命名空间来确定程序员正在访问的所有变量的值。变量名解析顺序如下：

  • 在本地命名空间中查找变量名
  • 在全局命名空间中查找变量名
  • 在 python 的内置函数中查找名称。

执行查找可能会很昂贵，Python 中的一般性能提示是出于这个原因使用局部变量：至少，它将避免执行两次查找而不是一次查找。此外，较新的 python 编译器似乎也在进行额外的优化，以删除对本地命名空间的单一查找，但只是将变量视为立即值。

测试这种优化是否仅仅因为命名空间查找而发生的一种好方法可能是（除非我不知道其他优化）将所有逻辑包装在一个函数中，但使您使用的所有变量都是全局的。如果一切都变慢了，您可能会猜到是命名空间查找花费了这么多时间。

于 2013-10-13T19:15:24.243 回答