一道数据处理的算法题

有一份5000万个用户的数据,有一份2亿个用户看电影的记录。只有1G的内存,找到看电影最多的前1000个用户?

应该怎么做呢?

我一开始的想法,哎呀,快速排序!把2亿个用户的数据提取出来放到5000万长度的数组里进行快速排序。把2亿个用户的数据提取出来,只能靠HashMap了,那么就要在建一个5000万个Key的HashMap了。但是想想只有1G的内存。

查找资料,在一个人博客中写到:1000000个item的HashMap就占内存接近60M了,那么5000万个item估计就要超过1个G了,因为HaspMap是非常非常消耗内存的。越是我的这个想法就宣告失败。

其实从思想上来看,我的这个想法只是暴力而已,用已经熟知的快速排序在时间上找点优势。然后看看题目,就知道他考你的不是时间,而是内存。我们都知道快速排序用的分而治之的思想,和这个思想相同的排序算法还有归并排序。

这个问题的正确解法应该是将2亿个记录分成一段段小的部分(可以用1G内存处理的部分),然后用我上面的方法进行排序,这样得出来每段的顺序,取前1000个,然后两两结合再次排序,或者三三结合也行。直到最后合并成一块,那就是我们需要的东西。

纵观下来,这就是归并排序的思想,也是分而治之的思想。在物理内存限制的情况下,我们只能局部求解,慢慢扩展到整体。这样可以用少的内存解决一个很庞大的问题。

如果这样的思想能在你的脑袋里扎根,那么很多问题你就可以解决了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

求两个等长有序数组的中位数的logN算法 分治法

http://blog.csdn.net/yangliuy/article/details/7194199

5832
来自专栏C语言及其他语言

【每日一题】1443 [蓝桥杯][历届试题]数字游戏

每日一题,一年365天,想不成为大神都难! 题目描述 栋栋正在和同学们玩一个数字游戏。 游戏的规则是这样的:栋栋和同学们一共n个人围坐在一圈。栋栋首先说出数...

3045
来自专栏程序员互动联盟

【面试宝典】谈谈面向对象

面试官:知道面向对象吧。 小白:嗯,知道,面想对象就是封装继承多态呀。 面试官:回答了一部分,还能谈谈除了封装、继承、多态之外的吗,比如说怎么抽象,抽象的思想是...

4038
来自专栏我是业余自学C/C++的

redis_3.0.7_sds.h_sdslen()

1903
来自专栏计算机视觉与深度学习基础

主席树POJ2104

求区间第k大数是多少 用我惯用的线段树写法似乎不适合写主席树,看别人的代码好半天才看懂 用root表示每一个前缀树的根,思想大致是由第i-1个树构成的树建第i个...

2479
来自专栏Python小屋

Python实现大自然数分解为最多4个平方数之和(1)

问题描述:任意大自然数,总是能分解为最多4个平方数的和,所谓平方数是指它是一个自然数的平方。例如:72884 = 4^2 + 138^2 + 232^2,337...

2714
来自专栏程序员互动联盟

到底能不能越过C直接学C++?

现在有好多人都比较迷茫,学习C++是不是需要先学习C语言? 其实这个问题不难,就是直接了解两者的联系和区别就可以给出答案。下面我们来看看他俩到底有什么关系。 ?...

3514
来自专栏吴伟祥

学习数据结构的原因&方法 原

721
来自专栏ACM算法日常

I'm Telling the Truth(二分图)- HDU 3729

二分图:设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点...

894
来自专栏编程

零基础学习人工智能之Python篇1-Python定义

学习Python首先咱要明白Python是什么 定义: Python是一种面向对象的解释型计算机程序设计语言 我们分解下Python的定义,主要是要理解面向对象...

2106

扫码关注云+社区

领取腾讯云代金券