Python 计算从1 |
您所在的位置:网站首页 › 求互素数的个数 › Python 计算从1 |
Python 计算从1-N(N可以任何数)内的素数(算法优化、并行计算、多线程优化计算)
1、项目介绍1.1研究背景1.2题目介绍
2.项目优化过程2.1 源代码2.2 优化1 - 数理的角度优化2.3 优化2 - 数理的角度优化2.4 优化3 - 引入列表2.5 优化4 - 加入列表后数理的角度优化2.6 优化5 - 数理的角度优化2.7 优化6 - 多线程优化2.8 优化7 - jit技术优化2.9 优化8 - Python cache缓存优化
3.总结4、附文件下载地址
1、项目介绍
1.1研究背景
随着深度学习的高速发展,大数据技术的普及,尽管大数据处理越来越流行,但是少不了本地python处理大量数据的场景,这时候单线程处理效率较低。接下来紧接的会普及发展的想必就是硬件层面的配合,而GPU无疑是最重要的趋势。 1.2题目介绍并行计算与GPU编程的大作业我选择的是质数运算方面的项目,通过Python实现查找N以内(N随意赋值)的质数个数的程序代码,因为质数统计运算一直是非常经典的问题,也通过这个问题深入优化算法代码去践行“简化计算,提高效率”的原则,进一步地去探究Python运算能力的多样性以及便利性。 2.项目优化过程 2.1 源代码按照质数的定义,我编写的源代码如下: 我首先从数理的角度出发对代码进行优化,我们知道所有大于10的质数中,除了5以外,其余能被5整除的都是合数,加上这个排除条件之后效率有所提高,这样可以进一步简化代码,我们具体来看一下会有多少提升。 修改后的代码如下: 我们继续从数理层面入手去完善代码!因为偶数除了2都不是质数,去除偶数相当于去掉一半运算量,效率提高差不多一半,这样代码可以进一步被优化,修改后的代码如下: 合数一定可以分解为几个质数的乘积;质数一定不能整除1和本身之外的整数;用列表实现,修改后的代码如下: 在引入列表后,我们继续结合数理方面的概念,因为合数一定可以分解为几个质数的乘积,质数一定不能整除1和本身之外的整数,我们构造一个列表,初值都是1,每发现一个素数,我们把所有它的倍数都置为False,直到发现下一个为1的数为素数。这就是书中提到的埃氏筛法。修改后的代码如下: 进一步细化一下数理概念,看还有没有优化的空间,我的想法是例如像15、33、39等这样的数字被称为合数,合数是由两个质数相乘得出的所以只需要计算到一半就可以排除了,同理可知其他数字也适用这一条件;相当于去掉了一半的计算量,效率又一定程度上提高了。 修改后的代码如下: 接下来,运用学习到的多线程基础对这两个新的判断质数代码进行测试,修改的代码如下: 用pypy的jit技术实现 使用Python cache 缓存,给需要缓存的函数加一个修饰器。 第一次调用时,正常执行,并缓存计算结果。 使用相同的参数,第二次调用时,不执行,直接加载计算结果 通过三周的学习,我从课上学会了如何使用Numpy、Numba、多线程、集群和队列等一系列手段对代码进行优化,还懂得了用cProfile来查看代码的内存运行情况以及可视化输出,虽然这四周的内容很多,但通过不断的尝试和实验,我最终还是熟稔于心,也明白了高阶程序员究竟是如何优化算法的,对其原理也熟练的进行了掌握,总的来说受益匪浅。 4、附文件下载地址Python 计算从1-N(N可以任何数)内的素数(并行计算、多线程优化计算) |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |