海量数据处理之top K问题

2017-06-05 23:20 阅读 6,264 次 评论 0 条

topK问题是一个经典的海量数据处理问题,比如热搜上每天都会更新出排行前10的热门搜索信息,再或者通过大数据找出陕西省人最爱吃的水果等,都可以使用topK问题来解决,其核心思想就是最小堆的引入。

topK问题分析

在海量数据中找出出现频率最高的前k个数,或者从海量数据中找出最大的前k个数,这类问题通常被称为top K问题

下面我们通过一个简单的示例来说明:假如面试官给你100W个数据,请找出其中最大的前K个数,并且现在仅仅有1M的空间?

在32位操作系统中,默认一个字为4字节,则有以下运算:

计算结果约等于4M,很显然1M的空间根本不够。也就是说,即使用最复杂的方法排序你也无法找到一个合适的空间来存储,因此引入了最小堆的数据结构

当然假如这道题不再限制空间的大小,你会如何解决?可能不少人会说排序啊,下面我给大家证明一下时间复杂度:

我只说核心实现思路,不再獒述堆的实现,对此不解的查看最大堆和最小堆思路如下:

① 定义两个数组,arr用于存储海量数据,top用于存储最小堆(底层数据结构借助vector)。

② 将海量数据的前k个元素先填满top堆。

③ 调整top堆为最小堆结构。

④ 通过遍历将新数据与堆顶元素(此时堆顶元素最小)比较,大于堆顶元素就入堆,并下调堆结构。

⑤ 遍历结束,则堆中的元素即n个数中最大的前k个数。

CVTE笔试题之topK问题

问题描述:本公司现在要给公司员工发波福利,在员工工作时间会提供大量的水果供员工补充营养。由于水果种类比较多,但是却又不知道哪种水果比较受欢迎,然后公司就让每个员工报告了自己最爱吃的k种水果,并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数,并且求出大家最喜欢吃的前k种水果。

算法分析:往往在笔试过程中,要在很短的时间内写出一个算法,调用标准库里面的东西是很方便的,比如CVTE这道题就是对STL中三种容器的考察:具体步骤如下:

① 首先,使用vector来存储所有的水果。

② 其次,采用map将vector中存在的水果的数量统计出来,map支持下标访问。

③ 最后,通过优先级队列来建立小堆,回归到topK问题

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:海量数据处理之top K问题 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情