| 算法学习（15）哥德巴赫猜想（多种解法，效率差了4千倍……） | 您所在的位置：网站首页 › 哥德巴赫猜想是谁发明的 › 算法学习（15）哥德巴赫猜想（多种解法，效率差了4千倍……） |
算法学习（15）哥德巴赫猜想（多种解法，效率差了4千倍……）
|
1. 前言
在研究哥德巴赫猜想这个问题的时候，再次让我感受到了这些问题的意义！多种程序表达方式都能求得结果，但是效率千差万别！这次是让我感受最深的一次，因为最好的算法和最差的算法，效率差距是4万倍…… 2. 问题验证100万以内，歌德巴赫猜想是正确的 2.1 名词解释歌德巴赫猜想，每个大于6的偶数，都可以写成两个素数之和，例如， 6 = 3 + 3 6=3+3 6=3+3, 18 = 11 + 7 18=11+7 18=11+7 3. 编程解决（三种方法，从慢到快） 3.1 方法1 3.1.1编程思路 先利用求素数的素数筛方法 (传送门)，找出10万内的所有素数，并单独储存起来遍历10万内大于6的偶数 n u m num num在素数数组里面抽素数当减数 j j j判断 n u m − j num-j num−j在不在素数数组里 3.1.2 实现代码 #!/usr/bin/env python # -*- coding: utf-8 -*- # @Date : 2019-04-15 14:33:13 # @Author : Promise ([email protected]) # @Link : ${link} # @Version : $Id$ import time import math # 输出1000氛围内偶数是否等于两个素数和 # 输入最大范围，返回素数列表 def getPrimeNumer(maxLimit): rawList = [1]*maxLimit # 默认认为都是素数的数组 for i in range(2, int(math.sqrt(maxLimit) + 1)): if rawList[i] == 1: # 确认除数是素数 for j in range(i*2, maxLimit, i): rawList[j] = 0 # 倍数肯定不是素数 # 把素数挑出来 primeList = [0]*(maxLimit//2) # 素数的规模，肯定不到一半的数字 j = 0 for i in range(2, maxLimit): if rawList[i] == 1: primeList[j] = i # 对应为1的索引，肯定为1， j += 1 return primeList, j # 遍历大于6的偶数，减数从primeList里面找,列出每个表 def Test(maxLimit, primeList, lenth, rawList): for i in range(6, maxLimit, 2): notFound = True for j in primeList[:lenth]: # 建这个数组可以减少遍历的次数 if i > j: # 这个可以试着去掉， 这个大小比较，比下面的比较要快…… if (i - j) in primeList[:lenth]: # 这里换成查找看看 # print(i, '=', j, '+', i-j) notFound = False break # 已经找到，可以退出 if notFound: print(i, '没法拆分') 3.1.3 运行效果
关键改动： if rawList[i - j] == 1: # 1 表明是素数, 实践表明，至少对于Python语言，根据数组索引读取某个位置的数，时间是可用忽略不计的，不管数组多长（最后这句话不严谨，但你懂我意思~） 3.3 方法3 (无心插柳的结果) 3.3.1 编程思路 方法2多用了一个素数数组，其实也可以直接就用判断素数的原数组来操作，代价就是增加了一个剔除合数的过程尝试之前，我心里是坚信，这种方法肯定没法比方法2快，我想看看它慢多少 3.3.2 实现代码 def getPrimeNumer(maxLimit): rawList = [1]*maxLimit # 默认认为都是素数的数组 for i in range(2, int(math.sqrt(maxLimit) + 1)): if rawList[i] == 1: # 确认除数是素数 for j in range(i*2, maxLimit, i): rawList[j] = 0 # 倍数肯定不是素数 return rawList # 尝试不挑数据，但是计时表明，生成素数数组，很快的 # 不管快或慢，把能想到的东西实现出来啊！ # 如果执行的时候，只有一个rawList,那么遍历的规模就太大了 def test3(rawList, maxLimit): for num in range(6, maxLimit, 2): notFound = True for i in range(2, num-1): # 采用原始数组的唯一优点，索引对应数字 if rawList[i] == 1: # 确定是素数 if rawList[num - i] == 1: # 进来说明找到了 # print(num, '=', i, '+', num - i) notFound = False break if notFound: print(i, '没法拆分') 3.3.3 运行效果
1.54 s → 0.09 s 1.54s\rarr 0.09s 1.54s→0.09s, 两个数量级的提升…… 3.3.4 代码分析（这里尝试分析速度快的原因） 方法三省去了一个单独装素数的数组，虽然之前测试过，单独挑出素数花费时间不多，但现在一比较，挑数据出来要花 0.0015 s 0.0015s 0.0015s, 是这里总运行时间的九分之一了，还多占用了内存，所以取消挺好for i in range(2, num-1): # 采用原始数组的唯一优点，索引对应数字， 因为减数不可能比要检验的数字 n u m num num大，于是，省去了方法1和2中， i ; j i;j i>j的判断。直觉上这个方法，要判断的素数比方法2的多，但可能因为有 b r e a k break break 语句在，这里的for循环，都不是时间久的关键。唯一增加了 if rawList[i] == 1: # 确定是素数, 从运行结果来看，增加了这个判断，对速度影响不大。 4. 运行效率大比拼其实一开始，我先写完第一个方法，然后测试了 100 万，你们猜运行了多久…… 铛铛铛……
我们来看看方法2，理论上是 40 倍的效率提升
上面我撒谎了……其实我是直接见证了 165.4 s → 0.9 s 165.4s\rarr 0.9s 165.4s→0.9s的飞跃…… 又是三个数量级的提升…… 5. 总结 处理 if 语句， 可能得区分复杂和简单的情况，对于方法1的第二个 if 判断，既有减法，还有查找，可能因此执行速度就慢了；第一个 if 只有 大小判断，可能因此快一点；实验结果是二者差距不大至少在Python中，查找比判断快，系统自带的 in 运算符，里面其实涉及很多判断，很耗时间，尽量少用。这就是方法2 比 方法 1 快40倍的原因永远不要觉得自己的程序是完美的，即使直觉上觉得改动没有用，也不要拒绝尝试方法 3 比 方法 2 快，==很大一个原因应该是少了一个单独装素数的数组，==所以，世界上有时真的有免费午餐，用更少的空间，还有更快的速度并不是所有的 for循环都是可怕的，这里 方法2 和 方法3 也包含了很大范围的循环，不过结合问题的特殊性（找到一个小的质数因子，就可以 break 整个循环），于是，这里的for循环不拖时间。方法1到3，实现同样的功能，但是选择了Python语言里不同的语句去实现，效率千差万别，知道最快的操作是哪些，很关键，对于将来构建大型程序很有意义，这也是我坚持这些练习的原因强调，从 4439 s → 0.9 s 4439s\rarr 0.9s 4439s→0.9s, 确实是约4千倍的提速合理利用空间换时间的诀窍，才能真正提高运行速度，方法2就是错误运用了“空间换时间”的原则，吃力不讨好不盲目追求并行运算，在我找到方法2的时候，我已经很满意了……毕竟有了40倍的提升，于是我兴奋发了朋友圈，有一朋友建议考虑并行。而当我找到方法3的时候，我才意识到，不要急于寻求并行的帮助！ 要让并行发挥最好的效果，最好是让串行执行的速度提高到最好先啊！二者是相辅相成的 6. 最后的拓展意外发现方法三的时间复杂度是 O ( n ) O(n) O(n) 求解 10 万 |
结果有点令人失望，10万的数，判断就需要整整
40
s
40s
40s ……
很遗憾，测试打脸了……给我的启示是，并不是所有地方，少一个 if 就一定会运行更快，得综合判断且实测。
好像找对方向了！ 时间从
41.125
s
→
1.54
s
41.125s\rarr 1.54s
41.125s→1.54s, 这时候，编程开始让人觉得是一门艺术了！约40倍的提升了哦！
啊！！！！！什么鬼，我理解你现在的心情，我那时吃惊的下巴快掉了？？？
你没看错，
4439
s
4439s
4439s, 当时我点了运行，就去吃饭，后来都忘了这件事…… 一个程序运行了1小时12分啊！！！
还真是！ 虽然当时足足运行了2分多钟，但我已经对这个结果很满意，我也不觉得能更快了……直到4.17号早上，我逼着自己再写了一个方法……于是，见证奇迹的时刻到了……
是的，我当时按了F1，瞬间出结果……吓得我连忙检查是不是数字规模写错了……
问题的规模每次增加10，耗时也增加10~ 有趣~【本文地址】