欢迎来到人人文库网! | 帮助中心 人人文库renrendoc.com美如初恋!
人人文库网
首页 人人文库网 > 资源分类 > DOC文档下载

嵌入式linux实验报告-三种排序算法的在linux和arm上执行速度比较.doc

  • 资源大小:100.27KB        全文页数:10页
  • 资源格式: DOC        下载权限:游客/注册会员/VIP会员    下载费用:9
游客快捷下载 游客一键下载
会员登录下载
下载资源需要9

邮箱/手机号:
您支付成功后,系统会自动为您创建此邮箱/手机号的账号,密码跟您输入的邮箱/手机号一致,以方便您下次登录下载和查看订单。注:支付完成后需要自己下载文件,并不会自动发送文件哦!

支付方式: 微信支付    支付宝   
验证码:   换一换

友情提示
2、本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器)
3、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

嵌入式linux实验报告-三种排序算法的在linux和arm上执行速度比较.doc

嵌入式LINUX设计实验报告项目概要名称三种排序算法的在LINUX和ARM上执行速度比较具体内容和实验要求三种或三种以上排序算法在ARMLINUX上执行速度的比较例如可以随机产生1000个数,在排序过程开始前计下系统时间,结束后再计下系统时间,算出时间差即为算法执行时间,每种算法需要多重复几次取平均值。项目分工需求分析共同完成概要设计和详细设计(李春元)负责整个程序的框架设计和具体函数的实现即代码注释;调试和改进(李红)代码调试,包括调试实例的设计,功能的扩展和补充;实现(共同完成)从VISUALC调试成功,移植到LINUX系统下的相关改进(库的变化等等),挂载到ARM9上的过程,比较三种环境下运行时间的差异。项目需求分析由实验要求可知,首先是确定三种排序算法,这个容易解决,我们选择的是快速排序,冒泡排序,简单排序;接着是随机数的产生;然后是怎样计下系统时间,最后是怎样用系统时间来计算多次排序的平均值,这里又会涉及到数据类型的强制转换。所以要实现这些要求,包括的函数主要有MAIN函数,冒泡排序函数,简单排序函数,快速排序函数,排序时间计算函数。代码的框架和具体的实验代码(概要设计和详细设计)由李春元同学完成。概要设计包括系统整体软硬件流程图,各个功能子模块的划分和描述;产生随机数简单排序冒泡排序快速排序时间统计调试结果与改进方案工程框架//MAIN主程序完成题目要求MAIN{//产生随即数RANDOMNUMBERBEFORESORTRANDOMNUMBER//根据题目要求计算所需时间并比较COST1//TIMECOSTINTBEFORESORT,INTMODECOST2COST3}//运行时间计算DOUBLETIMECOSTINTBEFORESORT,INTMODE{记住系统时间CURRENT0FORITERATION1N//N为排序算法多次执行的次数CASEMODE1SORT1INTBEFORESORTCASEMODE2SORT2INTBEFORESORTCASEMODE3SORT3INTBEFORESORTEND记住系统时间CURRENT1COSTCURRENT1CURRENT0/N;RETURNCOST;}//排序算法,任意找三种SORT1INTBEFORESORT{//ALGORITHM1}SORT2INTBEFORESORT{//ALGORITHM2}SORT3INTBEFORESORT{//ALGORITHM3}代码完成第一步测试随即数函数是否正确,随机数产生由函数SRANDUNSIGNEDTIMENULL实现,在这代码后添加显示函数PRINTFTHOUSANDRANDOMNUMBERSFROM0TO2000\N\N;FORI0;IN;/输出显示格式的设置,每行显示14个数,共1000个数/{FORJ0;J13;J{RJIKEYRAND2000;R1IKEYRIKEY;PRINTF6D,RJIKEY;}PRINTF\N;II13;}以观察随机数是否正确,这里开始处理点小问题,因为本实验要用同一排序法对同一组数据进行排序,每次排序后要恢复原待排序的数组,所以定义了两个同样的数组类型RECDTYPERN1,R1N1,后者用于恢复时使用。首先每产生一个随机数放到R和RL中,开始忘了这点,并没有R1IKEYRIKEY;这句,结果排序时间均为零(太小了)。第二步分析各排序算法的时间复杂度,用于验证程序是否正确。简单排序根据循环体计算其时间复杂度NN1/2ON2,移动次数和比较次数依具体待排数而定,空间复杂度O1,不稳定;冒泡排序根据循环体计算其时间复杂度NN1/2ON2,移动次数和比较次数依具体待排数而定,空间复杂度O1,稳定;快速排序根据循环体计算其时间复杂度ONLOGN,移动次数和比较次数依具体待排数而定,空间复杂度OLOGN,当待排序数有序时,退化为冒泡排序,不稳定;第三步测试三种排序的正确性,单独验证其正确,放在一个单独的程序中验证,只是验证一次排序的移动次数和比较次数,以及排序的的稳定性,测试的数据换成只有十个比较简单的数(0到20),这里就体现出了为什么李春元同学为什么要用一个结构体来表示每个数据,结构体中既包含了关键字的大小,也包括了每个关键字的位置信息,便于判断排序算法是否稳定,但是实验中并没有体现这点,这是考虑到了这个可能。这部分比较简单,没出大问题。第四步对计算运行时间的函数的验证和整个程序的验证是一起进行的,总要是通过看三种排序所花的平均时间的大小来判断程序是否正确。预计的是快速排序(冒泡排序,简单排序)。后两者基本相同。第五步为了更好的体现个排序算法的优劣,还加入了记录移动次数和比较次数的变量,当待排序数很多和排序次数很大时影响也会很大,所以要验证移动次数和比较次数,这个和第三步共同进行。第六步在LINUX系统上运行时要注意两者的兼容性,开始时李春元同学用了C的输出输入流来显示输出,这在LINUX的编译环境下是不支持的,最后都改成了C中的PRINTF语句以及MAIN函数返回值不能为VOID。还要注意的是文件的后缀是C。在LINUX上实现后,挂载到ARM上再通过终端显示。实验结果同1000个数经100次排序后的平均数据A)WINDOW上运行结果B)LINUX上运行结果运行时间(S)数据移动次数比较次数简单排序0028049450500292605冒泡排序003004945050010838124快速排序0019042276168218790C)(ARM)终端上运行结果运行时间(S)数据移动次数比较次数简单排序10460049450500292605冒泡排序1215004945050010838124快速排序7330042276539218741存在的问题和改进的方法;程序中并没有涉及到判断排序是否是稳定的,这是需要改进的地方,这在前面也提到了,在设计结构体TYPEDEFSTRUCT{KEYTYPEKEY;/定义关键字类型/ELEMTYPEDATA;/定义元素中其他数据项/}RECDTYPE;/定义元素结点类型/想到了这点,但没有深入下去,其实到这里也算是做到了,只需在初始化时对DATA赋初始值,标记每个数据的位置,移动时整个节点一起移动,最后每个节点完整输出,看KEY相同但DATA值不同的节点相对位置是变化了,没变则是稳定的,反之不稳定。参考文献【1】数据结构(C语言版)严蔚敏吴伟明编著,清华大学出版社;【2】C语言程序设计谭浩强著清华大学出版社;【3】嵌入式设计及LINUX驱动开发指南基于ARM9处理器孙天泽,袁文菊,张海峰,北京电子工业出版社;【4】嵌入式LINUX应用开发详解孙琼等北京人民邮电出版社;源代码INCLUDESTDLIBHINCLUDESTDIOHINCLUDETIMEHCONSTINTN1000;/待排序的数据个数常量/TYPEDEFINTKEYTYPE;/关键字数据类型定义/TYPEDEFINTELEMTYPE;/元素节点其他数据项数据类型定义/TYPEDEFSTRUCT{KEYTYPEKEY;/定义关键字类型/ELEMTYPEDATA;/定义元素中其他数据项/}RECDTYPE;/定义元素结点类型/TYPEDEFSTRUCT{LONGINTCP;/记录比较次数/LONGINTMV;/记录移动次数/}CPMV;/R为待排序列的数组//N为待排序列元素的个数//CM用于记录关键字的比较和移动次数/VOIDSIMPLESORTRECDTYPER,INTN,CPMVCM/简单选择排序法由小到大排列/{INTI,J,K;RECDTYPET;FORI0;IN1;I{KI;FORJI1;JN;J{IFRJKEYRKKEYKJ;CMCP;/比较一次,比较次数加一/}IFKI{TRI;RIRK;RKT;CMMV3;/交换次数加3/}}}INTBUBBLESORTRECDTYPER,INTN,CPMVCM/冒泡排序/{INTI,J,COUNT0;INTFLAG;FORI1;IN1;I{FLAG0;JN;WHILEJI1{IFRJKEYRJ1KEY/RJ与RJ1比较/{/RJ与RJ1进行交换/R0RJ;/R0作为暂存器,实现交换/RJRJ1;RJ1R0;FLAG1;/如果有记录交换发生,则置交换标志为1/CMMV3;/关键字移动次数加3/}CMCP;/执行IF语句,比较次数加1/J;}/如果无记录交换发生,则退出循环/COUNT;}RETURNCOUNT;}/S为排序区间的起始点//T为排序区间的终止点/VOIDQUICKSORTRECDTYPER,INTS,INTT,CPMVCM/快速排序/{INTLOWS;INTHIGHT;R0RS;/将基准记录移至R0中/WHILELOWHIGH{WHILELOWHIGHR0KEYRHIGHKEY{HIGH;/HIGH指针向前搜索/CMCP;/循环执行一次,计较次数加1/}CMCP;/最后一次比较,次数加1/IFLOWHIGH{RLOWRHIGH;/将HIGH所指向的记录后移/CMMV;/关键字移动次数加1/LOW;}WHILELOWHIGHRLOWKEYR0KEY{LOW;/LOW指针向后搜索/CMCP;/循环执行一次,比较次数加1/}IFLOWHIGHCMCP;/比较次数加1/IFLOWHIGH{RHIGHRLOW;/将LOW所指向记录前移/CMMV;HIGH;/HIGH指针继续向前搜索/}}RLOWR0;/LOWHIGH,将R0移动到它的终结位置/CMMV;IFSLOWQUICKSORTR,S,HIGH1,CM;/对RS到RHIGH1区间进行快速排序/IFLOWTQUICKSORTR,HIGH1,T,CM;/对RHIGH1到RT区间进行快速排序/}VOIDRESTORERECDTYPER,RECDTYPER1,INTN/恢复原始数据,用于每次排序后/{INTI;FORI1;IN;IRIR1I;}FLOATTIMECOSTRECDTYPER,RECDTYPER1,INTN,CPMVCM,INTMODE{INTK0;FLOATCOST;//程序运行所需时间INTKK100;INTIMODE;CLOCK_TSTART,FINISH;SWITCHI{CASE1STARTCLOCK;//开始时间//COUT以下进行插入排序ENDL;//COUTENDL;FORK1;KKK;K{SIMPLESORTR,N,CM;RESTORER,R1,N;}FINISHCLOCK;//COSTFLOATFINISHSTART/KK;BREAK;CASE2STARTCLOCK;INTCOUNT;FORK1;KKK;K{COUNTBUBBLESORTR,N,CM;RESTORER,R1,N;}FINISHCLOCK;COSTFLOATFINISHSTART/KK;BREAK;CASE3STARTCLOCK;FORK1;KKK;K{QUICKSORTR,1,N,CM;RESTORER,R1,N;}FINISHCLOCK;//终止时间COSTFLOATFINISHSTART/KK;//通过终止和起始时间计算得出运行所需时间,原始单位为秒BREAK;DEFAULTPRINTF;;}RETURNCOST;}INTMAIN{INTI,J;FLOATCOST;PRINTFTHOUSANDRANDOMNUMBERSFROM0TO2000\N\N;FORI0;IN;/输出显示格式的设置,每行显示14个数,共1000个数/{FORJ0;J13;J{RJIKEYRAND2000;R1IKEYRIKEY;PRINTF6D,RJIKEY;}PRINTF\N;II13;}CPMVCM3;CPMVP;/CMPV类型指针,中间变量,记录排序的比较次数移动次数的平均值/SRANDUNSIGNEDTIMENULL;/初始化随机发生器/PRINTFTHOUSANDRANDOMNUMBERSFROM0TO2000\N\N;FORI0;IN;/输出显示格式的设置,每行显示14个数,共1000个数/{FORJ0;J13;J{RJIKEYRAND2000;R1IKEYRIKEY;PRINTF6D,RJIKEY;}PRINTF\N;II13;}FORI0;I3;I{CMICP0;CMIMV0;}

注意事项

本文(嵌入式linux实验报告-三种排序算法的在linux和arm上执行速度比较.doc)为本站会员(21ask)主动上传,人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知人人文库网(发送邮件至[email protected]或直接QQ联系客服),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。

关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

网站客服QQ:2846424093    人人文库上传用户QQ群:460291265   

[email protected] 2016-2018  renrendoc.com 网站版权所有   南天在线技术支持

经营许可证编号:苏ICP备12009002号-5