100亿个数字找出最大的10个

标签: 数字 | 发表时间:2014-12-21 00:21 | 作者:shenstone2012
出处:http://www.iteye.com
1、首先一点,对于海量数据处理,思路基本上是确定的,必须分块处理,然后再合并起来。

2、对于每一块必须找出10个最大的数,因为第一块中10个最大数中的最小的,可能比第二块中10最大数中的最大的还要大。

3、分块处理,再合并。也就是Google MapReduce 的基本思想。Google有很多的服务器,每个服务器又有很多的CPU,因此,100亿个数分成100块,每个服务器处理一块,1亿个数分成100块,每个CPU处理一块。然后再从下往上合并。注意:分块的时候,要保证块与块之间独立,没有依赖关系,否则不能完全并行处理,线程之间要互斥。另外一点,分块处理过程中,不要有副作用,也就是不要修改原数据,否则下次计算结果就不一样了。

4、上面讲了,对于海量数据,使用多个服务器,多个CPU可以并行,显著提高效率。对于单个服务器,单个CPU有没有意义呢?

  也有很大的意义。如果不分块,相当于对100亿个数字遍历,作比较。这中间存在大量的没有必要的比较。可以举个例子说明,全校高一有100个班,我想找出全校前10名的同学,很傻的办法就是,把高一100个班的同学成绩都取出来,作比较,这个比较数据量太大了。应该很容易想到,班里的第11名,不可能是全校的前10名。也就是说,不是班里的前10名,就不可能是全校的前10名。因此,只需要把每个班里的前10取出来,作比较就行了,这样比较的数据量就大大地减少了。

已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [数字] 推荐:

数字的魔力

- 余波 - 腾讯CDC
  首先,在描述数字的神奇力量之前,先举一个贴近我们生活的实例. 大家还记得刚毕业时,汗流浃背的穿插在招聘现场投递简历的情景么. 相信每一个毕业生都经历过那紧张又焦虑的时刻. 那时手头那张薄薄的简历是我们的决胜的筹码,于是写简历自然成了一个技术活,令人痛苦却又不得不认真对待. 那么如何简洁明了,却又不遗漏任何一个闪光点的在简历里传递给招聘者所有有价值的信息呢.

数字化镜子

- Kidwind - 创意酷
  你想早上起来在刷牙的时候就能了解到当日的天气、当日的股市行情甚至个人的健康信息吗. 名为Cybertecture Mirror的镜子就要可以做到. 这可不是一个感念的家伙,它的售价约$7700,一面数字化镜子,早上起来当我们走进浴室就就可以打开当日的新闻资讯,查看微博. 它通过无线连接方式于电脑相连接,还外带有一块遥控器,使用它还可以得到我们的体重、健康指数,以及关于健康的一些其他指数.

数字绘画笔

- lei - 专利之家-设计发明与创意商机
手写板生产商Wacom近日发布了一款神奇的数字笔,可以将纸张上的图画或文字等内容数字化,以方便用户在计算机上进行修改. 这一设备由墨水笔、无线接收器、编辑软件(存储在接收器中)等部分组成. 值得一提的是,这只笔采用了压力感应技术,能够捕捉笔尖产生的不同压力,并将它们转换成粗细不一的线条. 该设备使用起来非常简单,你只需将接收器夹在绘画本或其他纸张上,用墨水笔进行创作,所有的这些内容就会被转化成数字格式并存储在接收器中.

数字原生代

- pisces - Oh My Media
能够守望一个小生命从懵懂无知渐渐成长,会笑会说会行走,是极其幸福的事情. 我也获得机会,伴随她那无比好奇的眼光,一同去看待身边每件似乎早已习惯、熟视无睹的事物,包括那些悄悄改变我们生活的数字媒体. 途中为拯救这个已百无聊赖哇哇大叫的小婴儿,我打开了iPad上的一个儿童教育应用程序,一只猫一只兔子分列左右,摆动前爪说“Hello”.

数字签名是什么?

- ArBing - 阮一峰的网络日志
它用图片通俗易懂地解释了,"数字签名"(digital signature)和"数字证书"(digital certificate)到底是什么. 我对这些问题的理解,一直是模模糊糊的,很多细节搞不清楚. 读完这篇文章后,发现思路一下子就理清了. 为了加深记忆,我把文字和图片都翻译出来了. 文中涉及的密码学基本知识,可以参见我以前的笔记.

生于数字时代

- Albert - 师北宸的网络日志
对于生于数字时代的人来说,生活在数字世界意味着什么. 凯文·凯利(Kevin Kelly)在他blog上分享了几则这样的故事,我翻译了几条出来,很有意思:. 我一位朋友有一个不到五岁的女儿. 像很多家庭一样,他们家里有很多电脑设备,但没有电视. 有一天,他带着他女儿去朋友家玩,朋友家有一台电视机. 小丫头走到电视面前,找了一圈,最后绕到电视后面,好奇地问大人们:“鼠标在哪儿.

Google的一些数字

- UnderSn0w - 36氪
今天Google在博客中发布了一篇文章,介绍Google搜索广告的演变,Google表示,现在几乎有1/3的Google搜索广告都不再只是三行文本,现在的广告包含价格、图片、特定链接或是视频预览等. 或者像Google在博客中说的那样:. 当初我们从三行文本起家的广告,现在已经演变成更加富媒体、基于位置的和社交增强型的广告.

[信息图]数字看facebook

- caixin - SocialBeta
我们知道facebook是这个星球上最大的社交网站,用户已经超过8亿,如果把facebook当成一个国家来看,它是世界上第二大人口大国,仅次于我们中国,但是有很多其他的数字你可能就不太了解了,比如你知道facebook上每天有多少照片上传呢. 下面一张关于facebook的各种数字方面的信息图也许能让你更深刻的了解facebook的的庞大.