课程咨询: 400-996-5531 / 投诉建议: 400-111-8989
认识达内从这里开始
认真做教育 专心促就业
烟台it培训小编跟你讨论一下双层桶划分：
适用范围：第k大，中位数，不重复或重复的数字。
基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。
扩展：
问题实例：
1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。
2).5亿个int找它们的中位数。
这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。
< 上一篇：bit-map简介
下一篇：什么是倒排索引(Inverted index) >
2019-04-15
免费试听课程
- 全部课程
- IT课程
- 设计课程
- 运营课程
4578
最新开班时间
- 北京
- 上海
- 广州
- 深圳
- 南京
- 成都
- 武汉
- 西安
- 青岛
- 天津
- 杭州
- 重庆
- 哈尔滨
- 济南
- 沈阳
- 合肥
- 郑州
- 长春
- 苏州
- 长沙
- 昆明
- 太原
- 无锡
- 石家庄
- 南宁
- 佛山
- 珠海
- 宁波
- 保定
- 呼和浩特
- 洛阳
- 烟台
- 运城
- 潍坊
- 开课名称
- 开班时间
- 抢座
- 咨询
- 开课名称
- 开班时间
- 抢座
- 咨询
-
- Java全链路开发
- 8月29日
- 火热抢座中
- 立即咨询
- 云计算全栈开发
- 8月29日
- 火热抢座中
- 立即咨询
-
- 网络安全工程师
- 8月29日
- 火热抢座中
- 立即咨询
- 人工智能工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- 数据分析与商业智能
- 8月29日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 8月29日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 8月29日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 8月29日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 8月29日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 8月29日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 8月29日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 8月29日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 8月29日
- 火热抢座中
- 立即咨询
-
- Java全链路开发
- 8月29日
- 火热抢座中
- 立即咨询
- 云计算全栈开发
- 8月29日
- 火热抢座中
- 立即咨询
-
- 网络安全工程师
- 8月29日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 8月29日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 8月29日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 8月29日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 8月29日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 8月29日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 8月29日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 8月29日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 8月29日
- 火热抢座中
- 立即咨询
-
- 云计算全栈开发
- 8月29日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- C++物联网工程师
- 8月29日
- 火热抢座中
- 立即咨询
- Web全栈开发
- 8月29日
- 火热抢座中
- 立即咨询
-
- 软件测试工程师
- 8月29日
- 火热抢座中
- 立即咨询
- AI大模型全栈工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- 鸿蒙原生应用开发
- 8月29日
- 火热抢座中
- 立即咨询
- 智能职场办公
- 8月29日
- 火热抢座中
- 立即咨询
-
- VFX商业视效设计
- 8月29日
- 火热抢座中
- 立即咨询
- AGI商业设计变现
- 8月29日
- 火热抢座中
- 立即咨询
-
- UID全链路设计
- 8月29日
- 火热抢座中
- 立即咨询
- 新媒体电商运营
- 8月29日
- 火热抢座中
- 立即咨询
-
- Java全链路开发
- 8月29日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- 数据分析与商业智能
- 8月29日
- 火热抢座中
- 立即咨询
- C++物联网工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- Web全栈开发
- 8月29日
- 火热抢座中
- 立即咨询
- 软件测试工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- AI大模型全栈工程师
- 8月29日
- 火热抢座中
- 立即咨询
- 鸿蒙原生应用开发
- 8月29日
- 火热抢座中
- 立即咨询
-
- 智能职场办公
- 8月29日
- 火热抢座中
- 立即咨询
- VFX商业视效设计
- 8月29日
- 火热抢座中
- 立即咨询
-
- AGI商业设计变现
- 8月29日
- 火热抢座中
- 立即咨询
- UID全链路设计
- 8月29日
- 火热抢座中
- 立即咨询
-
- 新媒体电商运营
- 8月29日
- 火热抢座中
- 立即咨询
-
- 云计算全栈开发
- 8月29日
- 火热抢座中
- 立即咨询
- 网络安全工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- C++物联网工程师
- 8月29日
- 火热抢座中
- 立即咨询
- Web全栈开发
- 8月29日
- 火热抢座中
- 立即咨询
-
- 软件测试工程师
- 8月29日
- 火热抢座中
- 立即咨询
- AI大模型全栈工程师
- 8月29日
- 火热抢座中
- 立即咨询
-
- 鸿蒙原生应用开发
- 8月29日
- 火热抢座中
- 立即咨询
- 智能职场办公
- 8月29日
- 火热抢座中
- 立即咨询
-
- VFX商业视效设计
- 8月29日
- 火热抢座中
- 立即咨询
- AGI商业设计变现
- 8月29日
- 火热抢座中
- 立即咨询
-
- UID全链路设计
- 8月29日
- 火热抢座中
- 立即咨询
- 新媒体电商运营
- 8月29日
- 火热抢座中
- 立即咨询
预约申请试听课
400-111-8989
lihm@tedu.cn
