【什么是双层桶】
事实上,与其说双层桶划分是一种数据结构,不如说它是一种算法设计思想。面对一堆大量的数据我们无法处理的时候,我们可以将其分成一个个小的单元,然后根据一定的策略来处理这些小单元,从而达到目的。
【适用范围】
第k大,中位数,不重复或重复的数字
【基本原理及要点】
因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子,分治才是其根本(只是“只分不治”)。
【扩展】
当有时候需要用一个小范围的数据来构造一个大数据,也是可以利用这种思想,相比之下不同的,只是其中的逆过程。
【问题实例】
1).2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不
同的区域,然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。
当然这个题也可以用我们前面讲过的BitMap方法解决,正所谓条条大道通罗马~~~
2).5亿个int找它们的中位数。
这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域,然后确定区
域的第几 大数,在将该区域分成2^20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可以直接利用direct
addr table进行统计了。
3).现在有一个0-30000的随机数生成器。请根据这个随机数生成器,设计一个抽奖范围是0-350000彩票中奖号码列表,其中要包含20000个中奖号码。
这个题刚好和上面两个思想相反,一个0到3万的随机数生成器要生成一个0到35万的随机数。那么我们完全可以将0-35万的区间分成35/3=12
个区间,然后每个区间的长度都小于等于3万,这样我们就可以用题目给的随机数生成器来生成了,然后再加上该区间的基数。那么要每个区间生成多少个随机数
呢?计算公式就是:区间长度*随机数密度,在本题目中就是30000*(20000/350000)。最后要注意一点,该题目是有隐含条件的:彩票,这意
味着你生成的随机数里面不能有重复,这也是我为什么用双层桶划分思想的另外一个原因。
分享到:
相关推荐
大数据量,海量数据 处理方法总结 包括Bloom filter 哈希 bit-map 堆 双层桶划分 数据库索引 倒排索引 外排序 trie树等。细分为适用范围、要点、实例等。
大数据量的问题是很多面试笔试中经常出现的问题,比如百度,谷歌,腾讯这样的一些涉及到海量数据的公司经常会问到。 本文的一些问题基本直接来源于...包括Bloom filter,Hashing,bit-map,双层桶划分,倒排索引等。
文章为大家介绍了电气双层电容器的结构与原理。
提出一种基于桶排序的双层模型预测控制方法。对电容 电压进行桶排序,将电压排序后的子模块按次序等分为若干组,通过第一层模型预测控制确定需要插入桥臂的 组数,再通过第二层模型预测控制进一步确定需要插入的子...
#资源达人分享计划#
土木工程毕业设计——地下双层岛式车站总长188.4 m总宽度20.7 m(计算书、施组、CAD图10张).zip
行业分类-设备装置-纸容器双层桶的取套结构.zip
C—— 自承式( 5 )外护层: 23—— 双层防腐钢带绕包销装聚乙烯外被层 33—— 单层细钢丝铠装聚乙烯被层 43—— 单层粗钢丝铠装聚乙烯被层 53—— 单层钢带皱纹纵包铠装聚乙烯外被层 553—— 双层钢带皱纹纵包铠装...
网页模板——jQuery+CSS3实现的双层圆环形进度条加载动画特效
Acrobat 33课时——光学识别-图像OCR识别与双层PDF文档.mp4
c# 部署PaddleOCR(csdn)————程序
该资源采用python编写,通过调用gurobi对数值双层优化问题进行求解,是学习双层规划的绝佳材料。
双层优化模型,求解思路是:首先对上层的决策变量编码,代人下层规划模型,通过求解下层模型的决策变量值,代入上层模型计算适应度值,然后进行交叉、变异、选择操作,最后求出最优解
双层PDF是指将标准资料通过扫描仪快速录入后,经过去污、纠偏和OCR识别,然后可以直接生成可以检索的PDF文件,这个PDF文件是双层的,上层是原始图像,下层是识别结果,这样可以100%保留原始版面效果,并且支持选择/...
双层PDF制作方法,示例中含O2S.Components.PDF4NET.dll 示例环境,VS2008,C SHARP,winform
#资源达人分享计划#
数学建模
双层BP神经网络,代码通俗易懂,可以下载学习
双层PDF的含义定义,便于读者了解PDF的本质,用于平时的存储及保存。数据查找等等功能。可以采用两种方法。
PCB板是重要的电子部件,是所有电子元器件的母体,从上世初开始出现到现在也变得越来越复杂,从单层到双层、四层,再到多层,设计难度也是不断增加。因为双层板正反两面都有布线,所以了解和掌握它的布线原则对于...