会员注册 | 登录 | 微信快捷登录 支付宝快捷登录 QQ登录 微博登录 | 帮助中心 人人文库renrendoc.com美如初恋!
站内搜索 百度文库

热门搜索: 直缝焊接机 矿井提升机 循环球式转向器图纸 机器人手爪发展史 管道机器人dwg 动平衡试验台设计

   首页 人人文库网 > 资源分类 > DOC文档下载

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

  • 资源星级:
  • 资源大小:100.27KB   全文页数:10页
  • 资源格式: DOC        下载权限:注册会员/VIP会员
您还没有登陆,请先登录。登陆后即可下载此文档。
  合作网站登录: 微信快捷登录 支付宝快捷登录   QQ登录   微博登录
友情提示
2:本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器)
3:本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

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

嵌入式linux设计实验报告项目概要名称三种排序算法的在linux和arm上执行速度比较具体内容和实验要求三种或三种以上排序算法在ARMLinux上执行速度的比较例如可以随机产生1000个数,在排序过程开始前计下系统时间,结束后再计下系统时间,算出时间差即为算法执行时间,每种算法需要多重复几次取平均值。项目分工需求分析共同完成概要设计和详细设计(李春元)负责整个程序的框架设计和具体函数的实现即代码注释调试和改进(李红)代码调试,包括调试实例的设计,功能的扩展和补充实现(共同完成)从visualc调试成功,移植到linux系统下的相关改进(库的变化等等),挂载到arm9上的过程,比较三种环境下运行时间的差异。项目需求分析由实验要求可知,首先是确定三种排序算法,这个容易解决,我们选择的是快速排序,冒泡排序,简单排序接着是随机数的产生然后是怎样计下系统时间,最后是怎样用系统时间来计算多次排序的平均值,这里又会涉及到数据类型的强制转换。所以要实现这些要求,包括的函数主要有main函数,冒泡排序函数,简单排序函数,快速排序函数,排序时间计算函数。代码的框架和具体的实验代码(概要设计和详细设计)由李春元同学完成。概要设计包括系统整体软硬件流程图,各个功能子模块的划分和描述产生随机数简单排序冒泡排序快速排序时间统计调试结果与改进方案工程框架//main主程序完成题目要求main{//产生随即数randomnumberbeforesortrandomnumber//根据题目要求计算所需时间并比较cost1...//TimeCostintbeforesort,intmodecost2...cost3...}//运行时间计算doubleTimeCostintbeforesort,intmode{记住系统时间Current0foriteration1N//N为排序算法多次执行的次数casemode1sort1intbeforesortcasemode2sort2intbeforesortcasemode3sort3intbeforesortend记住系统时间Current1costCurrent1Current0/Nreturncost}//排序算法,任意找三种sort1intbeforesort{//algorithm1}sort2intbeforesort{//algorithm2}sort3intbeforesort{//algorithm3}代码完成第一步测试随即数函数是否正确,随机数产生由函数srandunsignedtimeNULL实现,在这代码后添加显示函数printfthousandrandomnumbersfrom0to2000\n\nfori0i(冒泡排序,简单排序)。后两者基本相同。第五步为了更好的体现个排序算法的优劣,还加入了记录移动次数和比较次数的变量,当待排序数很多和排序次数很大时影响也会很大,所以要验证移动次数和比较次数,这个和第三步共同进行。第六步在linux系统上运行时要注意两者的兼容性,开始时李春元同学用了c的输出输入流来显示输出,这在linux的编译环境下是不支持的,最后都改成了c中的printf语句以及main函数返回值不能为void。还要注意的是文件的后缀是.c。在linux上实现后,挂载到arm上再通过终端显示。实验结果同1000个数经100次排序后的平均数据A)Window上运行结果B)Linux上运行结果运行时间(s)数据移动次数比较次数简单排序0.028049450500292605冒泡排序0.03004945050010838124快速排序0.019042276168218790C)(arm)终端上运行结果运行时间(s)数据移动次数比较次数简单排序10.460049450500292605冒泡排序12.15004945050010838124快速排序7.330042276539218741存在的问题和改进的方法程序中并没有涉及到判断排序是否是稳定的,这是需要改进的地方,这在前面也提到了,在设计结构体typedefstruct{keytypekey/定义关键字类型/elemtypedata/定义元素中其他数据项/}recdtype/定义元素结点类型/想到了这点,但没有深入下去,其实到这里也算是做到了,只需在初始化时对data赋初始值,标记每个数据的位置,移动时整个节点一起移动,最后每个节点完整输出,看key相同但data值不同的节点相对位置是变化了,没变则是稳定的,反之不稳定。参考文献【1】数据结构(C语言版)严蔚敏吴伟明编著,清华大学出版社【2】C语言程序设计谭浩强著清华大学出版社【3】嵌入式设计及Linux驱动开发指南基于ARM9处理器孙天泽,袁文菊,张海峰,北京电子工业出版社【4】嵌入式linux应用开发详解孙琼等北京人民邮电出版社源代码includeincludeincludeconstintN1000/待排序的数据个数常量/typedefintkeytype/关键字数据类型定义/typedefintelemtype/元素节点其他数据项数据类型定义/typedefstruct{keytypekey/定义关键字类型/elemtypedata/定义元素中其他数据项/}recdtype/定义元素结点类型/typedefstruct{longintcp/记录比较次数/longintmv/记录移动次数/}cpmv/r为待排序列的数组//n为待排序列元素的个数//cm用于记录关键字的比较和移动次数/voidsimplesortrecdtyper,intn,cpmvcm/简单选择排序法由小到大排列/{inti,j,krecdtypetfori0icp/比较一次,比较次数加一/}ifki{tririrkrktcmmv3/交换次数加3/}}}intBubbleSortrecdtyper,intn,cpmvcm/冒泡排序/{inti,j,count0intflagfori1ii1{ifrj.keymv3/关键字移动次数加3/}cmcp/执行if语句,比较次数加1/j}/如果无记录交换发生,则退出循环/count}returncount}/s为排序区间的起始点//t为排序区间的终止点/voidQuickSortrecdtyper,ints,intt,cpmvcm/快速排序/{intlowsinthightr0rs/将基准记录移至r0中/whilelowcp/循环执行一次,计较次数加1/}cmcp/最后一次比较,次数加1/iflowmv/关键字移动次数加1/low}whilelowcp/循环执行一次,比较次数加1/}iflowhighcmcp/比较次数加1/iflowmvhigh/high指针继续向前搜索/}}rlowr0/lowhigh,将r0移动到它的终结位置/cmmvifslowQuickSortr,s,high1,cm/对rs到rhigh1区间进行快速排序/iflowtQuickSortr,high1,t,cm/对rhigh1到rt区间进行快速排序/}voidRestorerecdtyper,recdtyper1,intn/恢复原始数据,用于每次排序后/{intifori1inirir1i}floatTimeCostrecdtyper,recdtyper1,intN,cpmvcm,intmode{intk0floatcost//程序运行所需时间intKK100intimodeclock_tstart,finishswitchi{case1startclock//开始时间//cout以下进行插入排序endl//coutendlfork1kKKk{simplesortr,N,cmRestorer,r1,N}finishclock//costfloatfinishstart/KKbreakcase2startclockintcountfork1kKKk{countBubbleSortr,N,cmRestorer,r1,N}finishclockcostfloatfinishstart/KKbreakcase3startclockfork1kKKk{QuickSortr,1,N,cmRestorer,r1,N}finishclock//终止时间costfloatfinishstart/KK//通过终止和起始时间计算得出运行所需时间,原始单位为秒breakdefaultprintf}returncost}intmain{inti,jfloatcostprintfthousandrandomnumbersfrom0to2000\n\nfori0iN/输出显示格式的设置,每行显示14个数,共1000个数/{forj0j13j{rji.keyrand2000r1i.keyri.keyprintf6d,rji.key}printf\nii13}cpmvcm3cpmvp/cmpv类型指针,中间变量,记录排序的比较次数移动次数的平均值/srandunsignedtimeNULL/初始化随机发生器/printfthousandrandomnumbersfrom0to2000\n\nfori0iN/输出显示格式的设置,每行显示14个数,共1000个数/{forj0j13j{rji.keyrand2000r1i.keyri.keyprintf6d,rji.key}printf\nii13}fori0i3i{cmi.cp0cmi.mv0}

注意事项

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

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

copyright@ 2015-2017 人人文库网网站版权所有
苏ICP备12009002号-5