首页 > > > 从10亿个浮点数中找出最大的1万个.doc

从10亿个浮点数中找出最大的1万个.doc

从10亿个浮点数中找出最大的1万个.doc

上传者: 天是无限高 2012-03-27 评分1 评论0 下载43 收藏10 阅读量49 暂无简介 简介 举报

简介:本文档为《从10亿个浮点数中找出最大的1万个doc》,可适用于手机软件领域,主题内容包含从亿个浮点数中找出最大的万个这是一道似易实难的题目一般同学最容易中的陷阱就是没有重视这个“亿”字。因为有亿个单精度浮点数元素的数组在位平台上已经达到符等。

10 亿个浮点数中找出最大的 1 万个 这是一道似易实难的题目,一般同学最容易中的陷阱就是没有重视这个 亿 字。因为有 10 亿个单精度浮点数元素的 数组在 32 位平台上已经达到 3.7GB 之巨,在常见计算机平台(如 Win32 )上声明一个这样的数组将导致堆栈溢出。 正确的解决方法是分治法,比如每次处理 100 万个数,然后再综合起来。不过这不是本文要讨论的主旨,所以本文 把上题的 10 亿改为 1 亿,把浮点数改为整数,这样可以直接地完成这个问题,有利于清晰地讨论相关算法的优化(注 2 )。 不假思索 拿到这道题,马上就会想到的方法是建立一个数组把 1 亿个数装起来,然后用 for 循环遍历这个数组,找出最大 1 万个数来。原因很简单,因为如果要找出最大的那个数,就是这样解决的;而找最大的 1 万个数,只是重复 1 遍而已。 template < class T > void solution_1 ( T BigArr[], T ResArr[]){ for ( int i=0;i<RES_ARR_SIZE;++i){ int idx=i; for ( int j=i+1;j<BIG_ARR_SIZE;++j){ if (BigArr[j]>BigArr[idx]) idx=j; } ResArr[i]=BigArr[idx]; std::swap(BigArr[idx],BigArr[i]); } } BIG_ARR_SIZE 1 亿, RES_ARR_SIZE=1 万,运行以上算法已经超过 40 分钟 (注 3 ),远远超过我们的可接受范 围。 稍作思考

第1页

编辑推荐

  • 名称/格式
  • 评分
  • 下载次数
  • 资料大小
  • 上传时间

用户评论

0/200
    暂无评论
上传我的资料

相关资料

资料评价:

/ 8
所需积分:0 立即下载
返回
顶部
举报
资料
关闭

温馨提示

感谢您对爱问共享资料的支持,精彩活动将尽快为您呈现,敬请期待!