• [活动分享] 【重磅发布】海思首批星闪开发者体验官招募,星闪手机等你拿!
    参加活动详情:https://developers.hisilicon.com/postDetail?tid=02102154262223765013                                                    指导单位:国际星闪无线短距通信联盟                                                                    主办单位:华为技术有限公司、海思技术有限公司                                                          协办单位:江苏润和软件股份有限公司
  • [交流分享] 基于 MPI 实现埃拉托斯特尼筛法及性能优化
    本次课程项目通过对埃拉托斯特尼筛法的原理分析,将其与MPI并行运算结合,大大降低了运算时间和时间复杂度。埃拉托斯特尼筛法(sieve of Eratosthenes),简称埃氏筛,也称素数筛,是简单且历史悠久的筛法,用来找出一定范围内所有素数。在寻找整数N以内的素数时,古希腊数学家埃拉托斯特尼采用了一种与众不同的方法:先将2-N的各数写在纸上:在2的上面画一个圆圈,然后划去2的其他倍数;第一个既未画圈又没有被划去的数是3,将它画圈,再划去3的其他倍数;现在既未画圈又没有被划去的第一个数是5,将它画圈,并划去5的其他倍数…… 依此类推,一直到所有小于或等于N的各数都画了圈或划去为止。这时,画了圈的以及未划去的那些数正好就是小于N的素数。以25为例,详细列出算法如下:列出2以后所有数: 2, 3 ,4 ,5, 6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 ,19, 20 ,21 ,22, 23, 24 ,25标记第一个质数2标记2的倍数如果最大数不大于最后一个标出的素数的平方,那么剩下的所有的数都是质数,否则回到第二步本例中,25大于2的平方,返回第二步;2之后第一个质数是3,标记3的倍数;得到的质数是2、3,25仍大于3的平方,再次返回第二步;3之后第一个质数是5,标记5的倍数;得到的质数是2、3、5,25是5的平方,筛选完毕。去掉标记的数,25以内的质数是$$ 2\text{,}3\text{,}5\text{,}7\text{,}11\text{,}13\text{,}17\text{,}19\text{,}23 $$给出其C语言串行实现:int prime[100005]; bool is_prime[1000005]; int eratosthenes(int n) { int p = 0; for (int i = 0; i <= n; i++) { is_prime[i] = true; } is_prime[0] = is_prime[1] = 0; for (int i = 2; i <= n; i++) { if (is_prime[i]) { prime[p++] = i; if (1ll * i * i <= n) { for (int j = i * i; j <= n; j += i) { is_prime[j] = 0; } } } } return p; }下面使用并行计算加快这一筛法将数组分为p个连续的块,每个块大小基本相等。平衡负载要给每个进程分配$ \lfloor \frac{n}{p} \rfloor $或$ \lceil \frac{n}{p} \rceil $ 个元素,我们考虑下面这种不同的实现方法:进程i控制的第一个元素是$ \lfloor in/p \rfloor $,最后一个元素是 $ \lfloor \left( i+1 \right) n/p \rfloor -1 $,对于特定元素j,控制他的进程是$ \lfloor \left( p\left( j+1 \right) -1 \right) /n \rfloor $。我们将数组2,3,……n 分配给p个进程,令$$ low_value=2+\lfloor id*\left( n-1 \right) /p \rfloor $$ $$ high_value=1+\lfloor \left( id+1 \right) *\left( n-1 \right) /p \rfloor $$我们用进程0来储存步骤中用于筛选的k(即2到$\sqrt{n}$的质数),所以程序运行的前提必须要求$$ 2+proc0_size>=(int)sqrt((doubt)n) $$ 对每一个进程都要提供一个marked[size]这样的数组,prime保存当前用于筛选的质数,first表示进程id中第一个要被筛掉的数对应的marked数组的下标。index用于步骤中找到比prime大的未被标记的数中最小的那个数,index为0进程专属。核心部分的程序为:if(!id) index=0;//0进程专属 prime=2;//最开始用2去筛选 do{ //找到第一个被prime筛掉的数 if(prime*prime>low_value) first=prime*prime-low_value; else if(!(low_value%prime)) first=0; else first=prime-(low_value%prime); //筛数,筛掉的数对应marked数组相应位置赋值为1,做标记 for(i=first;i<size;i+=prime) marked[i]=1; //在0进程中找到比prime大的未被标记的数中最小的那个数,用这个质数做新的prime去筛选。 if(!id){ while(marked[++index]); prime=index+2;//marked[0]对应自然数2 } //把0进程找到的新的prime更新其他进程的prime的值 MPI_Bcast(&prime,1,MPI_INT,0,MPI_COMM_WORLD); }while(prime*prime<=n);结合MPI并行运算分析可能的几种并行化改造方案:特定线程剔除特定数:优点:直观;缺点:2的倍数最多,3的倍数次多,前几个 进程几乎决定了总的运算时间,成为瓶颈。按照可用进程数分段: 将待筛选的数字分为不同的段,每个段包含连续的一部分数字。 首先,每个进程独立地筛选其分配到的段中的素数。 接下来,进程间进行通信,共享各个进程的筛选结果,以便确定进一步筛选的范围。重复上述步骤,直到完成筛选过程。在此基础上,我们又将时间复杂度具体化,分析了各部分对于时间复杂度的影响,由此提出了删除偶数和消除广播两种降低时间复杂度的方法,在1E5、1E7、1E9、1E10四个量级的数据上基本都能降低一半的运行时间。根据最终运行时间图像可以发现,在一定规模的数据量下,随着进程数量的增加,运行时间是逐渐减小的,同时在1E9和1E10规模的图像中发现,去除偶数的算法耗费的时间略高于优化通信的时间,说明任务在线程中通信花费的时间较多,在1E5规模下时间随进程增大也能说明这一结论。
  • [版主交流] 【华为云社区外部版主】2023年8月激励评比结果已公布!
    各位亲爱的版主们,大家好!经过大家一个月的努力角逐,8月外部版主激励评比结果已出炉,数据公示如下,请查看!(在新标签页打开图片可查看清晰大图/见附件)·外部版主激励规则:点击了解更多转正礼/基础任务/额外任务(在线时长15小时+,主题帖15+,回帖30+,技术长文5+/原创技术干货1+,合集1+,有效回复问题求助帖10+,话题互动1+,完成这4项指标可获对应价值的代金券/实物礼品)请完成任务获得激励的版主,点击填写激励发放意愿统计问卷反馈截止时间:2023年9月10日,以便小编进行相应的激励发放。注:在线时长数据达标后,才会再去考察达标版主的三项任务完成情况;主题数+回帖数达标后,才会再去考察达标版主的技术长文数量情况。
  • [分享交流] 有偿寻找设计师设计华为GT3手表表盘
    如题,寻找一名设计师
  • [版主交流] 【博客】+ 世界几个主要的思想家们不同观点
    用户没有删除功能,需要删除该如何操作?
  • [HDC2024] 博客发文的码豆没有计入吗
    博客发文有如下说明,奖励办法成功发表一篇原创博文,可获得150码豆,每天最多可获得300码豆。→码豆中心发文博客文章后,实际进入码豆中心,码豆并没有增加。
  • [活动公告] 创造HuaweiCloud Tookit 体验活动,反馈领好礼!
    【创造Huawei Cloud Toolkit体验活动】遇见Toolkit,解决开发运维痛点使开发者部署效率提速6倍。与华为云其他产品无缝集成围绕其产品能力向开发者桌面上的延伸打通华为云到开发者的最后一公里。华为云Toolkit致力于为开发者提供更稳定、快速、安全的编程体验。快速、高效集成华为云API深度融合支持用户检索API、查看API文档、调试API。编程过程中支持SDK代码片段补全加速用户集成华为云应用支持快速部署,一键部署到ECS、CCI提供业界规范检查支持一键格式化和代码自动修复。Huawei Cloud Toolkit除了提供以上产品能力以外,还支持包括微服务工程搭建等在内的诸多能力。为了感谢所有为Huawei Cloud Toolkit迭代做出贡献的开发者,Huawei Cloud Toolkit推出【创造Huawei Cloud Toolkit体验活动】,欢迎提出您的反馈建议,我们将记录每一份贡献,从而共同定义一款真正好用的华为云开发者生态工具。产品建议有礼:即日起至【6月18日】登录华为云账号访问Toolkit产品页面,并在【云声】上提交Toolkit的产品改进建议提出关于Toolkit产品新特性需求,提出产品改进建议和用户体验,或者上报bug,并被采纳可以获得建议好礼(活动详情请戳)~3.推广插件,包括发朋友圈、发表文章、推荐给朋友等。截图并联系我们,可免费获取华为云技术领域干货电子书,同时问题被采纳可参与华为云周边礼包抽奖!
  • [问题求助] 如何选择最新的excel表格
    其他部门每天都会新建一个新的excel表格上传,名字后会有“月日”,在选择数据上传是如何做到选择今天的excel来上传
  • 猫很高冷很可爱wo'hen'
  • [其他] 少女
    蓝色眼睛,金色头发,jiao'qiao
  • [热门活动] 昇腾社区年度用户满意度调研,惊喜好礼等您来拿!
    昇腾社区:www.hiascend.com昇腾论坛自建啦:www.hiascend.com/forum/问卷链接:昇腾社区用户满意度调研问卷昇腾论坛活动帖:满意度调研论坛活动帖
  • [热门活动] 鲲鹏社区年度用户满意度调研,惊喜好礼等您来拿!
    鲲鹏社区:www.hikunpeng.com鲲鹏论坛自建啦:www.hikunpeng.com/forum/问卷链接:鲲鹏社区用户满意度调研问卷鲲鹏论坛活动帖:满意度调研论坛活动帖
  • [热门活动] 【活动福利】华为开发者大赛中国区·南部赛区线下技术沙龙,领免费入场券!(限前30名)
    华为开发者大赛中国区·南部赛区线下技术沙龙,免费入场券30张!(最新改期)共建新生态,共创新价值!在这场技术沙龙,你将会学到云上最前沿的技术!你能和华为云专家面对面交流!还有各大代表企业现场切磋,机会难得!大会时间:9月27日 14:00-17:30 (因疫情原因,原定8月31日的活动延期到9月27日)大会地点:广州市天河区正佳广场万豪酒店大宴会厅A(场地有可能临时变动,请注意留意帖子更新)领取方式:微信扫码,添加小助手,领取入场券(限前30名)注:限完成【HCSD实训营——零代码云上开发体验季】活动报名用户参加,先到先得,限前30名,领完即止!>>>>>>>>点击报名【HCSD实训营——零代码云上开发体验季】<<<<<<<<<<
  • [热门活动] Python编程创造营“瓶瓶罐罐”小结实验任务(1)
    当前有以下需求: 实现一个用于计算(包括加减乘除)的小程序:  接受用户输入的计算式(如:3*4+1.1);  计算值;  将计算过程中涉及到的符号存储在元组中;  将计算中涉及到的值去重后存在列表里面(由大到小排列); 最后将计算过程存在字典里面(如 {"3*4+1.1":13.1} ) 本小白的代码是:numbers_count = input("请输入计算式:")print("您的结果为:", eval(numbers_count))symbol = {"+", "-", "*", "/", "%", "//", "**"}symbol_count = set({})for i in numbers_count:    if i in symbol:        symbol_count.add(i)symbol_tuple = tuple(symbol_count)print(symbol_tuple)numbers_all = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "0"}numbers = set({})for i in numbers_count:    if i in numbers_all:        numbers.add(i)numbers_list = list(numbers)numbers_list.sort(reverse=True)print(numbers_list)numbers_dic = {numbers_count : eval(numbers_count)}print(numbers_dic)输入:5*3+3/4-3-4-5输出结果:请输入计算式:5*3+3/4-3-4-5您的结果为: 3.75('/', '*', '+', '-')['5', '4', '3']{'5*3+3/4-3-4-5': 3.75}本小白的思路是:1.为达成接受用户输入的计算式,需使用input函数2.为计算用户输入值,需使用eval 函数3.为计算过程中涉及到的符号存储在元组中,先创建一个包含所有符号的集合和一个空的集合。通过for和if,遍历用户输入的计算式的每个元素,并判断其是否在包含所有符号的集合中4.为计算中涉及到的值去重后存在列表里面(由大到小排列),与上面的方法类似。但是需额外使用numbers_list.sort(reverse=True),对数字进行排序&为了实现去重,可以将出现的数字放入集合中,最后再将集合转为列表。5为计算过程存在字典里面,需创建字典。作者使用的是x = {'a':'A','b':"B",'c':3}方法,除此之外课上还教了X = dict(a='A',b="B", c=3)和x = dict([("a", "A"),("b", "B"),("c",3)])方法。代码说明:numbers_count = input("请输入计算式:")#获得用户输入值print("您的结果为:", eval(numbers_count))#通过eval函数直接算出结果symbol = {"+", "-", "*", "/", "%", "//", "**"}#创建包含所有符号的集合symbol_count = set({})for i in numbers_count:    if i in symbol:        symbol_count.add(i)#以上为遍历+判断symbol_tuple = tuple(symbol_count)#转为元组类型print(symbol_tuple)numbers_all = {"1", "2", "3", "4", "5", "6", "7", "8", "9", "0"}numbers = set({})for i in numbers_count:    if i in numbers_all:        numbers.add(i)numbers_list = list(numbers)numbers_list.sort(reverse=True)#使用sort函数进行排序print(numbers_list)numbers_dic = {numbers_count : eval(numbers_count)}print(numbers_dic)写在最后,作者本科商科,从未碰过代码。因,研究生专业为区块链技术,不得已开始自学编程。以上帖子仅为作者对该任务的一些粗浅认识,如果其中文字或者代码有误,希望各位大神/大佬/前辈不吝赐教,谢谢!!!
  • [热门活动] Python编程创造营“如果”和“复读机”小结实验任务(2)
    任务:计算猴子吃桃问题。猴子第 1 天摘了若干个桃子,当即吃了一半零一个;第 2 剩下的吃了一半零一个,一次循环。到第十天时想吃就剩下一个桃子。求第一天摘了几个桃子?本小白的代码是:j = 1for i in range(1,10):    j = (j+1)*2print(j)输出结果为:1534 本小白的思路是:属于数学的递归问题,在高中一个用数列的方式解决(也许)。但是,在Python中,可以利用for in range进行循环。D9=X/2-1=D10,因此推导出,D9=2*(D10+1),即f{x+1}=2[f(x)+1]所以,j = (j+1)*2。写在最后,作者本科商科,从未碰过代码。因,研究生专业为区块链技术,不得已开始自学编程。以上帖子仅为作者对该任务的一些粗浅认识,如果其中文字或者代码有误,希望各位大神/大佬/前辈不吝赐教,谢谢!!!
总条数:24 到第
上滑加载中