微信号:grzlwx

介绍:光荣之路官方资讯

程序算法优化,这药不能停

2019-04-08 11:33 好大一颗荔枝

新书

速递

吴老的java版《selenium webdriver 实战宝典》和python版《selenium Webdriver 3.0 自动化测试框架实战指南》出版了,代码拿来就能用。

文 |  好大一颗荔枝

问:要把形如7140229933辣么长的数分解为两个质数相乘,拢共分几步?

答:拢共分三步

第一步:写个算法判断一个数是不是质数

第二步:遍历查找7140229933以内的质数

第三步:判断7140229933能被哪个质数整除

看起来很简单,于是将上面的思路逐步转换为代码。

小白鼠版:

import  time


prime=[]

def  is_prime(x):

    if x <= 1:

        return False

    else:

        for i in range(2, x+1):

            if x % i == 0:

                return False             

        return True


def  prime_factorization(n):

    try:

        start=time.time()

         t_s=time.strftime('%H:%M:%S',time.localtime(time.time()))

        print('程序开始执行时间:%s'%t_s)

        for i in range(2,n):

            if is_prime(i):

                prime.append(i)

        for i in prime:

            if n%i ==0:

                print('%s=%s*%s'%(n,i,n//i))

        end=time.time()

        print('程序耗时:%ss'%round((end-start),2))

        return

    except:

         t_e=time.strftime('%H:%M:%S',time.localtime(time.time()))

        print('程序终止执行时间:%s'%t_e)


prime_factorization(7140229933)

运行起来好像也没报错,但是为啥一直不输出结果呢?嗯,因为它再循环。那我先等等。。。

千年等一回,我无悔啊啊~~~

眼睛一闭一睁,6分钟过去了hao~~

我真的不能再给你一首歌的时间,ctrl+c终止吧。求计算机心理阴影面积。。。

看来程序需要优化,判断是否是质数的程序好像蛮复杂的样子。那就从它先入手。

判断质数其实没有必要全部循环小于待判断数本身的数,通过math.sqrt求平方根,循环2到它的平方根+1,其实也一样可以满足需求。

如果一个数是合数,那么它的最小质因数肯定小于等于它的平方根。合数是与质数相对应的自然数,如果它不是合数,那它一定是质数。所以判断一个数是否是质数,只需判断它是否能被小于它开根后的所有数整除即可。

同理,prime_factorization函数中的查找某一范围内的全部质数,也没有必要全部循环。

优化版:

import  math

import  time


prime=[]

def  is_prime(x):

    if x <= 1:

        return False

    else:

        for i in range(2,  int(math.sqrt(x+1))):

            if x % i == 0:

                return False             

        return True


def  prime_factorization(n):

    try:

        start=time.time()

         t_s=time.strftime('%H:%M:%S',time.localtime(time.time()))

        print('程序开始执行时间:%s'%t_s)

        for i in  range(2,int(math.sqrt(n+1))):

            if is_prime(i):

                prime.append(i)

        for i in prime:

            if n%i ==0:

                print('%s=%s*%s'%(n,i,n//i))

        end=time.time()

        print('程序耗时:%ss'%round((end-start),2))

        return

    except:

        t_e=time.strftime('%H:%M:%S',time.localtime(time.time()))

        print('程序终止执行时间:%s'%t_e)


prime_factorization(7140229933)

执行一下,感觉真是的神清气爽~~~

秉承着“更高,更快,更强”的奥林匹克精神,我决定继续使用我小学六年级的数学功底挖掘程序优化点。

质数的最大特点是从除了1与它自己本身,不能被其他数整除。所以质数这个大家庭中除了2这个偶数之外,其他的数都是奇数。

所以循环的时候,可以把除了2之外的偶数,全部过滤掉。这样又能节省一半的时间。

惊奇版:

import  math

import  time


prime=[2]

def  is_prime(x):

    if x<= 1:

        return False

    elif x==2:

        return True

    else:

        for i in range(3,  int(math.sqrt(x)+1),2):

            if x % i == 0:

                return False             

        return True


def  prime_factorization(n):

    try:

        start=time.time()

         t_s=time.strftime('%H:%M:%S',time.localtime(time.time()))

        print('程序开始执行时间:%s'%t_s)

        for i in  range(3,int(math.sqrt(n)+1),2):

            if is_prime(i):

                prime.append(i)

        for i in prime:

            if n%i ==0:

                print('%s=%s*%s'%(n,i,n//i))

        end=time.time()

        print('程序耗时:%ss'%round((end-start),2))

        return

    except:

         t_e=time.strftime('%H:%M:%S',time.localtime(time.time()))

        print('程序终止执行时间:%s'%t_e)


prime_factorization(7140229933)


执行耗时结果:

程序算法优化其实也没有那么难,关键是如何能够跳出固有的思维模式,优化不必要的操作和执行。从而提高执行效率~

欢迎留言分享

测试人员的财富自由之路

金三银四跳槽季 面试经验分享你-前篇

金三银四跳槽季 面试经验分享你-后篇

来自测试人的困惑与思考

大龄 | 手工 | 自动化逆袭

【appium实战】appium混合页面点击方法tap的使用

实战:微信小程序+appium测试实例

实战:微信公众号+appium测试实例

使用LR编写windows sockets协议xml报文格式脚本

Python实战:file tell()返回的指针怎么就不一样?

互联网架构的演变

爬虫之我与正则的甜蜜约会

草根在测试行业如何杀出一条血路(8)

软件测试行业现状2018年度报告

2018web测试开发培训一年期周六班!

喜马拉雅app搜索并收听“光荣之路”电台
光荣之路
招聘|征稿|合作 |QQ群
735821166@qq.com
python群:457561756
性能群:415987441
招聘群:203715128
爱我,请给我好看
 
光荣之路 更多文章 金三银四跳槽季 面试经验分享你-前篇 软件测试的痛点有哪些? 面试基础(7) 疑难问题排查方法之“埋点法” 图解django框架下简单接口的实现
猜您喜欢 第 0 期技术微周刊,从经典的 Linux 命令系列开始 职场上,哪类人会更讨喜呢? Hadley Wickham 采访节选(一) Spring框架在数据处理方面的进化史 陶哲轩对数学学习的一些建议