海量数据处理专题(六)——双层桶划分

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

【适用范围】
第k大,中位数,不重复或重复的数字

【基本原理及要点】
因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子,分治才是其根本(只是“只分不治”)。 继续阅读