玩蛇网提供最新Python编程技术信息以及Python资源下载!

python运行效率同函数功能有关系吗?

打印1-200000以内素数,我测试了两段代码。 第一种采用函数调用的方式花了1.87s,第二种把函数体写到循环体里面执行,反而花了2.25s。这是为什么呢?

(1)

def isPrime(n):     
    if n <= 1:     
        return False
    if n == 2:     
        return True
    if n % 2 == 0:     
        return False
    i = 3
    while i * i <= n:     
        if n % i == 0:     
            return False
        i += 2
    return True

for n in range(1, 200000):
    if isPrime(n):     
         print n  

(2)

for n in range(1, 200000):
    if n <= 1:     
        continue
    if n == 2:
        print n
        continue
    if n % 2 == 0:     
        continue
    i = 3
    flag = True
    while i * i <= n:     
        if n % i == 0: 
            flag = False
            break
        i += 2
    if flag:
        print n

因为第二种算法是错的,多打印出了许多东西。break 之后合数还是被打印出来了。

PS: 利用 Python 3.2+ 的 functools.lru_cache,可以轻松实现更好的算法。


来,修正后的第二种算法为什么还是比较慢:

>>> time python2 a.py > /dev/null
python2 a.py > /dev/null  1.15s user 0.01s system 99% cpu 1.165 total
>>> time python2 b.py > /dev/null
python2 b.py > /dev/null  1.66s user 0.01s system 99% cpu 1.677 total
>>> time python2 c.py > /dev/null
python2 c.py > /dev/null  1.03s user 0.00s system 99% cpu 1.035 total
>>> time python2 a.py > /dev/null
python2 a.py > /dev/null  1.06s user 0.02s system 98% cpu 1.092 total
>>> time python2 b.py > /dev/null
python2 b.py > /dev/null  1.70s user 0.02s system 99% cpu 1.721 total
>>> time python2 c.py > /dev/null
python2 c.py > /dev/null  1.05s user 0.00s system 99% cpu 1.058 total

第三种算法如下:

def t():
  for n in range(1, 200000):
      if n <= 1:
          continue
      if n == 2:
          print n
          continue
      if n % 2 == 0:
          continue
      i = 3
      flag = True
      while i * i <= n:
          if n % i == 0:
              flag = False
              break
          i += 2
      if flag:
          print n

t()

查找全局变量比查找局部变量慢。

找素数最少判断个数应该采用的策略是,6N+1和6N-1应该比单独判断奇数要少1/3时间。

我在这里凑个热闹,python 写的打印素数,没别的,只是速度很快。

3.py 是上面@依云 写的 4.py 是我的:

import math

N = 200000
M = int(math.sqrt(N));
a = [1]*N

for i in range(3, M, 2):
    for j in range(i+i, N, i):
        a[j]=0

print 2
for i in range(3, N, 2):
    if a[i] == 1:
        print i

算法是逆向思考,从3开始,3的倍数肯定都不是素数,全部排除,5也同理。。最后输出剩下的就好了。

严格的说 M 应该是int(math.sqrt(N)) + 1

玩蛇网文章,转载请注明出处和文章网址:https://www.iplaypy.com/wenda/wd20047.html

相关文章 Recommend

玩蛇网Python互助QQ群,欢迎加入-->: 106381465 玩蛇网Python新手群
修订日期:2017年05月24日 - 20时29分21秒 发布自玩蛇网

您现在的位置: 玩蛇网首页 > Python问题解答 > 正文内容
我要分享到:

必知PYTHON教程 Must Know PYTHON Tutorials

必知PYTHON模块 Must Know PYTHON Modules