10 亿个数取中位数

10 亿个数取中位数
1、取 16*1024 个数，生成一个 TreeMap 。取得最大值 max 和最小值 min。
2、构造一个1024个元素的计数数组 T[i]，对最初的 1024 个数按区间计数；
对 min 和 max 进行 1024 个等分,各等分值为 N[i]。

当数据 N[a]<data<=N[a+1] 时， T[a]++；

3、将大于 N[512-8] 且小于 N[512+8] 的数放入一个新的 TreeMap。

4、开始读取之后的数据，执行2 和 3的操作；

5、根据区间计数，获知中位数处于N[x]区间。
如果正好处于 N[512-8] 且小于 N[512+8]，则可以直接查询数据。
否则，重新读取一次数据，将处于 N[x] 区间的数，放入一个 TreeMap 中，获得中位数。

6、如果某个区间的数据量超过 200万，则对该区间进行分区，分成 1024 个区，并进行计数。


嗯嗯，计数要智能一些，可以分拆、合并计数据区间。最大值最小值要随时取。

唔唔，有空将代码写出来试试。不知道是否可行。

评论

3 楼 zwhc 2010-04-03  

分区计数应该是正解。

具体算法如下：
1、开始时取2个数，以其平均值为界分成2个区间，此时对最多4个数进行分区计数；
变量：区间数用 Q 表示，分区计数用 N[i] 表示。

2、将数据按大小，放入相应的区间；每放入一个，N[i]++;

3、当某个区间里的数字个数大于分区数时，即 N[i] >= Q，则生成新的分区对新数据进行计数；
新分区有如下属性；

a、分区数*2 ，因为区间里的数字个数不大于分区数，所以新分区最多可
对 Q*Q 个数进行计数，

b、以之前所有数的最大值和最小值进行等分；即，遍历数据时，要保存最大值和最小值；

4、各组分区与最大可计数的数据列表
Q   Q*Q
2    4
4    16
8    64
16   256
32   1024
64   4K
128  16K
256  64K
512  256K
1024 1M
2K   4M
4K   16M
8K   64M
16K  256M
32K  1G
64K  4G
128K 16G
256K 64G
512K 256G

唔，这种算法有个缺陷：如果最大数和最小数相差很大，数据集中在一块，会有很多无效的分区，因此效率不高。

如果数据平均分布，这是个好办法。不过。。。嗯嗯，这种情况太少了。

==============================================================

分区计数应该是正解。

上面一种算法不好用，做一些改进。

具体算法如下：
1、开始时取2个数，以其平均值为界分成2个区间，此时对最多4个数进行分区计数；
变量：区间数用 Q 表示，分区计数用 N[i] 表示。

2、将数据按大小，放入相应的区间；每放入一个，N[i]++;

3、当某个区间里的数字个数大于分区数时，即 N[i] >= Q，则在该分区下，生成两个子分区对新数据进行计数；
子分区有如下属性；

a、以父分区的最大值和最小值的平均值分成两个分区
b、每个子分区可计数的量为父分区的两倍；

唔，这种算法应该比较好。

2 楼 zwhc 2010-04-03  

分区计数应该是正解。

具体算法如下：
1、开始时取2个数，以其平均值为界分成2个区间，此时对最多4个数进行分区计数；
变量：区间数用 Q 表示，分区计数用 N[i] 表示。

2、将数据按大小，放入相应的区间；每放入一个，N[i]++;

3、当某个区间里的数字个数大于分区数时，即 N[i] >= Q，则生成新的分区对新数据进行计数；
分区扩展时，按如下方式进行扩展；

a、分区数*2 ，因为区间里的数字个数不大于分区数，所以新分区最多可
对 Q*Q 个数进行计数，

b、以之前所有数的最大值和最小值进行等分；即，遍历数据时，要保存最大值和最小值；

4、各组分区与最大可计数的数据列表
Q   Q*Q
2    4
4    16
8    64
16   256
32   1024
64   4K
128  16K
256  64K
512  256K
1024 1M
2K   4M
4K   16M
8K   64M
16K  256M
32K  1G
64K  4G
128K 16G
256K 64G
512K 256G

唔，这种算法有个缺陷：如果最大数和最小数相差很大，数据集中在一块，会导致一直分区下去。

如果数据平均分布，这是个好办法。不过。。。嗯嗯，这种情况太少了。

1 楼 zwhc 2010-04-03  

2 4
4 16
8 64
16 256
32 1024
64 4k
128 16k
256 64k
512 256k
1024 1M
......