00:00
好,我们继续啊,经过一个漫长的等待啊,我们这个终于执行完了,那这个呢,我们先记下时间,执行的是170.645秒。170.645秒。哎,有同学说这东西也挺慢的呀,哎,对,确实是很慢,但是它比我们在优化前已经快多了,为什么呀,优化前我们压根就没有结果呀,而在我们第一次优化以后,好歹它能执行了,虽然很慢,好歹能出结果了,那接下来呢,我们来看一下我们能不能再做一个进一步的优化,再做一个进一步的优化,那这里我们就要说一个问题了,现在我们这道题呢,整体做了一个思路是,哎,当这个数是100的时候,我就干嘛,哎,我就把它的所有的这个这个所有可能成为它因数的这些数取出来,当它是100的时候,我就取二到99,当它是99的时候,我就取二到98,当它是98的时候,我是不是就去取二到97啊?哎,是这么一个,当这个呢,范围明显有点大了,那比如。
01:17
不说,哎,比如说我们100,如果是100的话,取到的是二到99,那我们说了,这时候有没有必要取这么多,哎,完全没有必要,其实没这个数太多了,你像99有没有可能成为100的因数啊,哎,基本上是不可能的,哎同学说老师,那你刚才不是已经不break了吗?Break以后实际上取不到99了,对吧?对,100的确是取不到99了,但是我们还有一些其他数,比如说97 97很明显它是一个质数,当我们I是97的时候,我们接的范围是二一直到96,啊,二一直到96,那现在问题就来了,稍微有点脑子你就知道,我问你96可不可能整除97 96可不可能是97的因数?
02:08
哎,很明显这个是不可能的,哎,你96除97那是不可能的,对吧,那所以我们就想了,那既然96不可能,95可不可能啊,94可能能这些都是不可能的,也就是说我们这个街的范围,我能不能给它缩小一点。如果把接的范围缩小了,我们这个性能是不是又是一个大很大的提升啊,因为你现在如果接是1万,你就要循环1万次,接是1000,你就要循环1000次,如果把这范围缩小了,我们就能很大程度的提高我们这个性能啊,那怎么办?那怎么办?那这里我们就要看一下我们这个数的这个因数的一个规律,那这里啊,我们不能拿97举例子了,因为97它是个质数,它因数就一个97,对吧,我们要说一个,我们拿一个。
03:00
偶数拿一个非质拿一个合数去举例子,然后我们再说这个问题,那我们来看啊,我们拿一什么举例子呢?我们在这儿举吧,我们拿一个36来举例子,36。36的因数,我们来看看三十一六有哪些因数,36首先最小的一和36对吧?一和三六不说了,除了一和它本身是吧,二和18,二乘以18还有什么呀?哎,三乘以12啊,三乘以12还有谁呀?哎,还有我们这个四九三十六啊,四九三十六,然后还有谁呀?哎,还有我们的五都没了,对吧?哎,我没,然后是什么呀?六六三十六,这是我们36的因数,那我问你,我再往后找,再往后找还有没有新的因数?还有没有新的技术了,很明显这个时候就没有了,因为再往后七不是八不是到九,九对谁呀,九对四,那这个东西上边我们是不是已经找过了,再往下十没有,11没有,十二十二对三是不是也找过了,再往下就是18对二了,你会发现我们这个因数它都是一对一对的,如果我们画一个数轴表示。
04:14
因数,诶,这是36因数,前边有一个一,后边一定会有一个36,前边有一个二,后边一定会有一个什么呀,18,前边如果有一个三的话,后边一定会有一个什么呀,哎,12,诶,然后前边有一个四,后边一定有一个什么呀,有一个这个九,然后到六,这是中间啊,哎,这就是我们这个六,你会发现我们的因数实际上都是一对一对的,前边有一个,后边一定会有一个对应的,如果前边没有,后边肯定也没有,因为它都是一对一对,所以你会发现到某个位置以后,实际上我们再找的因数都是重复的,没有新的了,到哪个位置,实际上是不是就到这个位置,到他这如果没有因数啊,你假设36在123456这都没有因数,那六往后还有没有可能有了,是不是也不可能有了,因为它都。
05:14
不是一对一对的,前边有一个,后边一定有一个和它对应的,如果前边没有,后边是不是一定也没有啊,所以如果我们要找一个数的因数,实际上我用不用从二一直找35,不用,我们是不是只要找到六就已经获取到36的所有因数了?哎,找到六,那同理,对于97来说,我用不用一直找到一到96用不用,很明显二到96啊,很明显也是不用的,我们是不是也只需要找到它中间那个位置,如果到这个位置没有,后边是不是都没有了?哎,都没有了,那问题来了,这个位置是哪儿啊?这个位置是哪啊?哎,我们说了六是什么?六六三十六是不是正好到一个两个数相同的位置,也就是说它的位置实际上正好是什么?是根号下36,也就是说给36的开方吧,36的这个平方根,那同理,如。
06:14
如果我们要找97的话,我们用不用一直找到96,不用,实际上对于我们来说,直接找到根号下97,我们求出97的平方根,它最大最大就到这平方根了,平方根如一直到平方根都没有,后边是不是全都没有了,哎全都没有了,所以这个位置我们在这儿用不用接小于I,哎不用,我们是不是只需要小于根号下I就行了呀?哎,根号下I怎么表示啊,那其实非常简单,我们就是什么呀?哎,I的这个零点五次方,那是不是就它的平方根呀,之前我们讲这个次幂运算的时候,我们说了0.5就是给它开方啊,给它开方,那这个时候我们再看它的性能啊,性能我们先看一下,性能一直行,诶,你看0.66是不是速度非常快啊,哎,速度非常非常快,但是这个时候还是我们又改了一种。
07:07
规则了,那这个时候我们就要确定一下算的到点对不对,还是我先改成100啊先改成100,然后呢,我先看一下结果对不对,我这一执行234,诶完了结果这个速度确实快,但是结果不对了,这不小心多了一个什么,多了一个四,哎,多了一个四,为什么会多了个四,哎,因为我们这改的时候有一种情况,我们没有考虑到哪种情况。哪种情况就是当我们的这个数只有一个因数啊,这个数除了一和它本身只有一个因数,而这个因数正好是它的平方根,而我们这在判断的时候有没有包括等于的情况,没有,所以是不是就会导致把它这个因数给它错过呀,比如说四,四的话,根号下四是不是就是二啊,好,我这接小于二了,接的初始值就是接小于二,这个循环是不是压根就不执行啊,哎,不执行我们就错过了二这个因数,所以在这我们就会认为四是质数啊,四是质数,所以为了处理四这种特殊情况,我们这应该是皆小于等于,也就说我要把它那个平方根是不是也包括进去啊,也包括进去,这样我们来看这时候结果才对的,235 71 13 17 19,这时候是不是才对呀,诶这时候才对,那这个时候我们再去测性能才更准确一点啊,更准确点,所以这个时候我把打印一句还是去掉啊,还是去掉。
08:38
然后呢,我把这改成1万啊,改成1万,我们来看速度执行一下,是不是0.107呀,哎,0.107,那按道理来讲,我们这种测试应该多次测量啊,多次测试取这个什么呀,平均值啊,多次去测试取平均值,你会发现速度是不是更又快了,哎,0.068,我们就记它吧,哎,那这个是我们的第二次优化,第二次优化哎,我们还是1万个数,哎,1万个数0.068秒,那你会发现这是不是快很多了,68毫秒之前是一点几秒,对吧,一点几秒速度已经是非踌非踌啊,非常非踌,好,我们再来看10万个数,10万个数第一优化前是不行的,第一次优化是170秒,我们来看第二次优化走一个。
09:26
哎,1.677秒啊,我们再来执行一下,看看速度走一个。1.646秒啊,1.646秒啊,我们这是12345,这是10万个数。10万个数,这是多少啊?1.646秒。哎,1.646秒,那这就很明显了,对吧?哎,这就很明显了,我们也就是说从我们这个三次优化,第一次10万个数是不行的,第二个数是170秒执行了这个什么呀,将近三分钟啊,将近三分钟,而第三第二次优化我们干嘛了,只需要一点多秒就完成了,那这个代码,这一段很简单的代码,那其实对我们的性能提升是非常非常的大的啊,非常非常大,所以这个代码对我们的性能是非常非常的重要啊,非常非常重要的,所以注意以后咱们在工作时,或者自己在做什么东西的时候,我们性能的优化是没有止境的,我们总是要想,我们能不能用一些特殊的算法来让我们程序运行的更快,程序运行的更快,性能的越好,性能越好,就意着意味着我们这个程序,我们这个代码,我们这个算法编写的就更加的合理,但是这种东西如果你是第一次写的话,你很有可能是想不到的啊,想不到的。所以往往这些。
10:47
你都是对我们平时的知识的一些积累,你的数学的知识,你的这个分析问题能力一个积累,所以现在想不出来,还是先不要着急,慢慢来,你现在先把这个东西给它理解了,随着我们以后的深入学习,这种点会越来越多,难度也会越来越大啊,越来越大,好,我们还是先停一下。
我来说两句