posts - 200, comments - 8, trackbacks - 0, articles - 0

【什么是双层桶】
事实上,与其说双层桶划分是一种数据结构,不如说它是一种算法设计思想。面对一堆大量的数据我们无法处理的时候,我们可以将其分成一个个小的单元,然后根据一定的策略来处理这些小单元,从而达到目的。

【适用范围】
第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)。最后要注意一点,该题目是有隐含条件的:彩票,这意味着你生成的随机数里面不能有重复,这也是我为什么用双层桶划分思想的另外一个原因。

做人好厚道,转载请注明出处:http://diducoder.com/mass-data-topic-6-multi-dividing.html


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理