​程序员应知应会之大数据如何求中位数

2024-02-21 23:51 来源:网络 点击:

程序员应知应会之大数据如何求中位数


相对于平均数,中位数在统计学中很多时候具有更高的参考意义。因为在很多情况下,平均数的意义并不大。例如如果有10个人,其中9个人每人月收入1块钱,而马云一人收入991块钱,那么,平均收入是100块钱。而中位数则是1块钱,所以光看平均数的话,在这种情况下意义不大。


我们首先来看一下中位数的定义:

对于一个排序好的数列,如果数据总数为奇数的话,那么中位数就取最中间的一个;如果数据总数为偶数的话,那么中位数就取最中间两个数的平均值。

那么如何求出中位数呢?这个问题本质上是一个排序问题,求中位数通常有以下几种方法:

1、对数据进行排序,然后直接取出中位数,该方法时间复杂度为O(N*logN);

2、对N个数,构建N/2大小的堆,然后遍历完所有的数再取出堆顶就是中位数了,时间复杂度为O(N*logK)其中K代表是的构建堆的大小;

3、BFPRT算法,用来求解Top-K问题。然后中位数就是求第N/2的数,即中位数。最坏时间复杂度为O(N)。

但是简单的算法在大数据应用中,很多时候并不能直接使用,因为大数据本身是一个量变引起质变的问题,数据量大的时候,要考虑的因素就更为复杂。


例如说,如果我们要解决以下的问题:

在一个大文件中,有10G个数,乱序排列,要求其中位数。应该如何做?

对于大数据来说,需要考虑的问题包括以下几点:

1、内存大小的约束,对于10G个数来说,数据量是大于很多计算机内存的,因此,如果内存不够大的话,就不可能将所有数据加载进内存进行排序;

2、数的类型约束,对于海量数据来说,其来源很多时候并不单一,特殊数据的情况也会经常存在,例如Java的整型数最大值为2147483647,而在海量数据中,很有可能出现比该数大的值,这种情况下,如果采用整型数的话,无疑会出问题。这时候就需要考虑使用长整型或者java.math.BigInteger来进行处理了。除此之外,一些来源的数据会因为各种原因,产生诸如undefined(未定义)或者是infinite(无穷大)等用字母表示的数据,这种情况如果不处理的话,程序也会产生问题。

好了,在考虑到以上问题之后,我们简单介绍一下大数据条件下,求中位数的常用方法。

一、堆排序(转化为Top-K问题)

对于Top-K来讲,不需要对数据进行排序,只需要拿新数据与堆顶数据进行比较即可,也不需要将全部数据加载到内存,只需要构建一个K大小的堆。当读取的新元素比堆顶元素小时舍弃,比堆顶元素大时替换掉堆顶。

因此,我们可以根据实际的内存大小,例如说内存只有2G的话,可以先构建一个1G的堆,得到第1G大小的元素,然后依次类推,直到求出中位数。

但是这种方法需要多次遍历数据,产生频繁的磁盘IO操作,效率很低。

二、桶排序

可以将数据根据数据类型,从小到大划分为若干个桶,例如说10000个,然后将数据根据内存大小,划分为适应内存大小的组,依次读入。例如首先装载前1G个数,遍历这些数,将它位扔进对应的桶里。

当所有数据都遍历完之后,从最小的桶计数开始类加,直到加到全部数据的一半,得到中位数。

该方法需要遍历两次数据,效率较高。


三、BFPTR算法

BFPTR算法是由Blum、Floyed、Pratt、Tarjan、Rivest五个人一起提出来的,其特点在于可以以最坏复杂度为 O(n)地求解top−k问题。

在BFPTR算法中,每次选择五分中位数的中位数作为pivot,算法步骤如下:

1、将输入数组的 n 个元素划分为 n/5 组,每组5个元素,且至多只有一个组由剩下的 n%5 个元素组成;

2、寻找 n/5 个组中每一个组的中位数,首先对每组的元素进行插入排序,然后从排序过的序列中选出中位数;

3、对于(2)中找出的 n/5 个中位数,递归进行步骤(1)和(2),直到只剩下一个数即为这 n/5 个元素的中位数,找到中位数后并找到对应的下标 P;

4、进行Partion划分过程,Partion划分中的pivot元素下标为 P;

5、进行高低区判断即可。

以上就是在大数据应用场景下,求中位数需要考虑的约束问题和基本实现思路。在遇到具体问题的时候,还需要具体问题具体分析,灵活多变的解决实际应用问题哦。