bitmap计数,求TopK最快的方法?
《TopK到底怎么答?》介绍了TopK的四种解法,其中随机选择 (randomized select) 最为经典,用减治法 (Reduce & Conquer) 的思想,将数据规模急速降低,总体复杂度为O(n)。
结尾挖了一个坑:求TopK,有没有比随机选择更快的方法呢?
空间换时间,是算法优化中最常见的手段,如果有相对充裕的内存,可以有更快的算法。
画外音:即使内存不够,也可以水平切分,使用分段的方法来操作,减少每次内存使用量。
TopK问题描述
从arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中,找出最大的k=5个。
比特位图(bitmap)法
bitmap,是空间换时间的典型代表。它是一种,用若干个bit来表示集合的数据结构。
例如,集合S={1,3,5,7,9},容易发现,S中所有元素都在1-16之间,于是,可以用16个bit来表示这个集合:存在于集合中的元素,对应bit置1,否则置0。
画外音:究竟需要多少存存储空间,取决于集合中元素的值域,在什么范围之内。
上述集合S,可以用1010101010000000这样一个16bit的bitmap来表示,其中,第1, 3, 5, 7, 9个bit位置是1。
假设TopK的n个元素都是int,且元素之间没有重复,只需要申请2^32个bit,即4G的内存,就能够用bitmap表示这n元素。
扫描一次所有n个元素,以生成bitmap,其时间复杂度是O(n)。生成后,取TopK只需要找到最高位的k个bit即可。算法总时间复杂度也是O(n)。
伪代码为:
bitmap[4G] = make_bitmap(arr[1, n]); return bitmap[top k bits];
bitmap算法有个缺点,如果集合元素有重复,相同的元素会被去重,假设集合S中有5个1,最终S制作成bitmap后,这5个1只对应1个bit位,相当于4个元素被丢掉了,这样会导致,找到的TopK不准。该怎么优化呢?
比特位图计数
优化方法是,每个元素的1个bit变成1个计数。
如上图所示,TopK的集合经过比特位图计数处理后,会记录每个bit对应在集合S中出现过多少次。
接下来,找TopK的过程,就是bitmap从高位的计数开始,往低位的计数扫描,得到count之和等于k,对应的bit就是TopK所求。
如上图所示,k=5:
(1)第一个非0的count是1,对应的bit是9;
(2)第二个非0的count也是1,对应的bit是8;
(3)第三个非0的count是2,对应的bit是7;
(4)第四个非0的count是2,对应的bit是6,但TopK只缺1个数字了,故只有1个6入选;
故,最终的TopK={9, 8, 7, 7, 6}。
结论:通过比特位图精准计数的方式,求解TopK,算法整体只需要不到2次扫描,时间复杂度为O(n),比减治法的随机选择会更快。
为了巩固今天的内容,例行挖个坑。
面试中,还有个问题问得比较多:求一个正整数的二进制表示包含多少个1?
例如:7的二进制表示是111,即7的二进制表示包含3个1。
画外音:我面试过程中从不问这个问题。
最常见的解法是:
uint32_t count_one(uint32_t n){ uint32_t count=0; while(n){ count ++; n &= (n-1); } return count; }
提问:还有多少种更快的方法呢?
原文发布时间为:2018-09-25
本文作者:58沈剑
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
告别微服务:究竟是千军易得还是一将难求
白小白: 初看这篇文章时,我实际上是有些犹豫要不要把他翻译过来的。毕竟多数人,包括我们的团队也都在采用和推崇微服务架构。这个时候谈及“告别微服务”的话题,是否有些不合时宜。然而,文章中关于从单体到微服务再到单体的架构变迁过程,我认为对很多希望从微服务中获得收益的团队是很有意义的。文章中也涉及了很现实很落地的一些关于挑战的应对以致妥协。正如此前火山哥的文章《微服务的4个设计原则和19个解决方案》中所讲的“实际上微服务也不是个万金油”,回顾一下那篇文章中的原则,再看一下本文中的实践过程,将对微服务架构的采用和取舍有更深切的认知。很多时候,不在于是否最好,而在于是否适合自己。 当然,这只是我选择这篇文章理由之一,另一个理由是,我总感觉,作为文章中所举的例子来说,似乎并非只有回归单体应用这一条路线,比如,我并未在文章中看到诸如API网关的相关描述--文中所讲的消息路由只解决了网关的一部分问题,就像是简单的NGINX代理一样--而API网关是微服务架构中非常关键的组成部分。此外,关于代码库的拆分(毕竟这是作者的团队决定回归单体结构的重要原因之一),此前叶婉婷的文章《当持续集成遇上微服务:分治优于...
- 下一篇
Scrapy分布式、去重增量爬虫的开发与设计
基于 python 分布式房源数据抓取系统为数据的进一步应用即房源推荐系统做数据支持。本课题致力于解决单进程单机爬虫的瓶颈,打造一个基于 Redis 分布式多爬虫共享队列的主题爬虫。本系统采用 python 开发的 Scrapy 框架来开发,使用 Xpath 技术对下载的网页进行提取解析,运用 Redis 数据库做分布式,使用MongoDb 数据库做数据存储,利用 Django web 框架和 Semantic UI开源框架对数据进行友好可视化,最后使用了Docker对爬虫程序进行部署。设计并实现了针对 58 同城各大城市租房平台的分布式爬虫系统。 分布式爬虫抓取系统主要包含以下功能: 1.爬虫功能: 爬取策略的设计 内容数据字段的设计 增量爬取 请求去重 2.中间件: 爬虫防屏蔽中间件 网页非200状态处理 爬虫下载异常处理 3.数据存储: 抓取字段设计 数据存储 4.数据可视化 完整项目源码 关注微信公众号 datayx 然后回复 分布式 即可获取。 二、系统分布式架构 分布式采用主从结构设置一个Master服务器和多个Slave服务器,Master端管理Redis数据库和分发下载...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS7,8上快速安装Gitea,搭建Git服务器
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- SpringBoot2整合Redis,开启缓存,提高访问速度
- MySQL8.0.19开启GTID主从同步CentOS8
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- CentOS8编译安装MySQL8.0.19
- CentOS8安装Docker,最新的服务器搭配容器使用