题目: 海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。

本人的思路是 在每台电脑上求出TOP10,可以采用包含10个元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆)。比如求TOP10大,我们首先取前10个元素调整成最小堆,如果发现,然后扫描后面的数据,并与堆顶元素比较,如果比堆顶元素大,那么用该元素替换堆顶,然后再调整为最小堆。最后堆中的元素就是TOP10大,然后求出每台电脑上的TOP10后,然后把这100台电脑上的TOP10组合起来,共1000个数据,再利用上面类似的方法求出TOP10就可以了。

大家有没有更好的算法?

2 1 收藏


直接登录
最新评论
  • TIF   2015/10/22

    每台电脑求出top1 然后100里面求top10呢?

    • 小编辑 编辑 2015/10/22

      显然不行啊。如果top10都在同台电脑呢?

      • 时光鸡不会飞   2015/10/24

        那每台电脑求出top1,然后降序排列,然后在top1的电脑里求出top2然后将降序的第二个数与top1里的top2比较如果比top2大,则降序的第二个数为真的top2,假如是top1里的top2大,则他是top2,然后再求出top1里的top3,然后再与降序的第二个数进行比较,然后以此类推求出top10,这样呢?

  •   学生 2015/10/22

    可以把每台电脑的数据分为好几份,然后求出每台电脑的第一份的TOP10,再求所有电脑第一份的top10,得出进入TOP10的最低要求,做第二份的top10,做之前,就可以根据第一份TOP判断这个数是否有资格进入Top 10,进而,提高进入TOP10要求,减少数据比对。有资格的才进入求Top10,余下数据,按此类推。

    • laball 软件工程师 2015/10/22

      正解,不过,个人以为,这个题目主要的考点是两个,一是每台几天去top10,二是单个机器上取top10时肯定要考虑内存不够用的情况,需要拆解。这两点做好了,面试官应该就比较满意了!

    • wohenshuai   2015/10/23

      楼上的思路没太明白,可以说的在清楚些吗?是如何在海量数据分布式处理时,减少数据比对的?

  • 潘小鶸 研发工程师 2015/10/22

    这就是阿里的ODPS对海量数据做order by 然后 limit 时用的策略,估计这就差不多了

  • Mr_map   2015/10/23

    1. 让100台电脑返回各自最大的值,共100个,降序排列,设为p1,p2,p3,…p100.其中最大的值一定是top1;

    2. 将p2仅发往找到P1的那电脑,就一定能得到top2;

    3.将top2发往p1,p2…..p100序列中,所有大于top2的电脑上,就一定能得到top3;

    4.重复以上过程,得到全部top10.

  • 对于100台机器,先将每台机器的大文件数据按照hash的方式进行切分。切分为100个小文件,编号为1-100;然后编号为1的统一放到机器1,编号为2的统一放到机器2…… (这步是为了保证同一条数据必须只出现在一台机器上)

    然后100台机器并发计算各自机器上每个数据的出现次数(HashMap或者HashTable)

    然后最小堆方式得到每台机器的TOP10,得到100 个 TOP10 共1000 个数据;

    1000个数据再找出TOP10(仍然最小堆方式)