关于如何快速求得非精确的大量数字的中间值（原创） -

lipengfei217

浏览: 3134 次
性别:
来自: 苏州

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

关于如何快速求得非精确的大量数字的中间值（原创）

博客分类：

算法，编程，中间值

算法 java 编程中间值

许多时候，我们需要求得提供的一系列数中中间值，也就是整体数据的平均值的反应，而大部分时候我们会将这些数据先进行排序，

然后将排序好后的数据取得所有数据个数的二分之一的位置，即为整体数据的中间值。可是往往有些时候我们并不需要一个精确的在提供

的数据中存在的值，而是需要一个模糊的可以不属于提供的数据中的某一个数，却有接近整体数据的中间值，这个时候，若当整体数据个

数大于10万，乃至100万，1000万，甚至1亿的时候，排序往往是极为费时又费力的工作，基于这样的需要，我写了一个极为粗略却又有

一定效果的算法，用来抛砖引玉。

     学过统计学的朋友都知道，通常我们针对一系列的样本按照某种规则去统计数据的时候，往往可以从一定程度上通过样本数据来反应整

体数据的大致走向。本文则利用类似的原理，当然，由于本人统计方面的知识匮乏，尚无法用比较确切的理论去证明，以及尽力求得更精

确的值。

    首先明确一下问题，什么叫一堆数字的中间值？

     案例：最近沉迷于从强伟那里抢来的《编程之美》，其中就有一个部分求得若干点（Point,即x、y轴所构成的二维坐标系的点）中，距

离最近的一组点对，《编程之美一书中》给出了一种解法，就是取这些点对的中间值（x坐标），即令x=M时，将该若干点对分成 Left部分

和Right部分，即当所提供的点的x坐标大于数M时，将所有点分在坐标轴的右半部分，而当所提供的点的x坐标小于数M时，将所有的点分

在坐标轴的左半部分，然后分别求得左半部分最近的点对，和右半部分最近的点对，而提供的一系列点对中，除了左右部分有可能取得最

近的点对之外，还有一种可能就是某一点属于Left部分，而另外一点属于Right部分，他们俩组成的点对是最近的点对。关于求最近点对的

算法我这里也不再赘述，有兴趣者可以查阅《编程之美》（ISBN978-7-121-06074-8）一书的Page 170

     通过上述案例可以看出，其中很重要的一点就是要从这些所有的点对中找出中间数，使得Left部分和Right部分的点的个数尽量相等。否

则若取得的M的值偏小或偏大，将导致Left部分和Right部分的点对数目失衡，从而该算法的效率在一定程度上受到限制。于是我就借用统

计原理的一些基础性原理来在数据无序的情况下（有序的数据也可以）来近似求得一系列数中的偏向于中间的值。下面说一下算法原理：

从一堆数据中随机取出一定数量的数据，求这些数据的平均值，当取得数的个数越大，其求得的平均值越接近整体数据的偏于中间的值。

具体我没有做过相关证明，该设想主要是因为当我从提供的数据中随机取有限个数时，这些取出的数的大小不一，因此得到的平均数将会

趋于取出的数的中间值，而小样本事件往往在一定规律上可以反映出整体数据的规律性，因此写出了该算法。以下代码使用Java写的，最

后会附上一些测试值，可以看出求得的平均值是否在一定程度上反映了整体数据的中间值，至

于C、C++等代码版本我这里就不再写了。

以下就java代码作出分析：


public static Integer getFuzzyNum(Integer[] array) {
  if (array != null) {

   int size = array.length;

   int num = 3;// 默认选取3个数，但若当size大于一定程度时，则按某种算法取num的个数

   Integer value = 0;

   if (size < 3) {
    num = 1;
   } else if (size > 30) {
    num = size / 10;
   }

   if (num > 100) {// 此外，无论size的值有多大，都只随机取100个数
    num = 100;
   }

   // 随机获取m个位置的数的值，取平均数
   for (int i = 0; i < num; i++) {
    double random = Math.random();
    int position = (int) (size * random) - 1;

    if (position < 0) {
     position = 0;
    }
    value += array[position];
   }

   Integer count = 0;
   int average = value / num;

//测试取出的平均数趋于整体数据中间值的水平，与算法本身无关------START---------
   for (int i = 0; i < array.length; i++) {
    if (array[i] < average) {
     count++;
    }
   }
   System.out.println("比随机平均数小的数的个数：" + count + ";比随机平均数大的数的个数"
     + (size - count) + ";均差为" + (size / 2 - count)/2);
//测试取出的平均数趋于整体数据中间值的水平，与算法本身无关------END---------   

   return value / num;
  }
  return null;
 }

以上算法将传入一个Integer类型的数组作为整体数据，这个变量命名为array,首先得到给出的数据的个数，也就是size的大小，通过这个

大小我们来判断需要取出多少样本数据来做平均值，比如，若给出的整体数据个数为10个，那么对样本数据而言，取出3~5个即可一定程

度上反应样本数据，但是若给出的整体数据个数为10，000时，我们取出的样本数据为3的个数则远远不够，由于取出所有数的随机概率

是等可能的，所以当我们取出的样本个数越多时，得到的平均值越趋向于整体数据的平均水平，而平均水平也是样本数据中间值的反应

所以上述程序中，当size大小小于30时，随机取出样本数据的个数为3，而当size的大小大于30时，就取样本数据的个数为整体数据的十分

之一，也就是说，若整体数据的个数为120，那么样本数据就取12个。只是当整体数据个数趋于非常大，也就是10000，或者10,0000甚至

100,0000时，样本数据取十分之一的个数，也太多了，于是本算法中限制了样本数据个数最大为100。
也即
if (num > 100) {// 此外，无论size的值有多大，都只随机取100个数
num = 100;
}
而这段代码：

// 随机获取m个位置的数的值，取平均数
   for (int i = 0; i < num; i++) {
    double random = Math.random();
    int position = (int) (size * random) - 1;
    if (position < 0) {
     position = 0;
    }
    value += array[position];
   }

   Integer count = 0;
   int average = value / num;

主要就是借用Java中数学类的随机值，来从整体数据中随机取得Num个数，并取得这Num个数的平均值，即为所求。

由于本人计算机性能的问题，该算法就只求最大数据个数为10000的数据，因此更多的数，需要大家自行测试并做相应改进，虽然这个方

法有些鸡肋，但是一定程度上却可以为我们提供新的思路。

而代码中附带上的：测试取出的平均数趋于整体数据中间值的水平

这个里面的代码主要是将求出的平均数与整体数据做对比，得出比这个平均值小的数的个数M和比平均值大的数的个数N，若M和N的个数

越是接近，则代表所求得的平均数越是接近整体数据的中间值，于是我又定义了均差的概念。即将M-N的值再除以2，可以得到求得

的平均值接近整体数据平均值的某种程度上的近似程度。

为了方便测试，我在测试程序中给出了100个数组，其中每一个数组中存储了10000个值，这10000个值属于无序随机数据，每一个随机数据是小于1000,0000的任何有可能的值。因此如果取得其中间值，那么大于这个中间值和小于这个中间值得数的个数应该为4999个和5001个或者4999个和5001（此处忽略相等的情况，因为在本算法中没有太多的影响。我们可以单独得到于平均数相等的数的个数，然后再增加一个维度来综合考虑算法的可行性和客观性）

运行测试程序，于是得到以下截图中的结果：

其中第一列的结果为计算出的中间值，由上图可看出，比平均数小的数的个数M以及比平均数大的数的个数N基本趋于一个相对稳定的状

态，最后一列均差就是描述M和N之间的差异程度。如果将均差的值作为各个点绘成坐标轴上的曲线图，那么会发现，在区间[-5000~5000]中，曲线为主要趋于0点上线，由于目前手上没有相应的工具，所以此处就不再绘制均差趋势图，有兴趣的朋友可以试一下。

代码附在下面，有需要的就直接复制吧。

转载请注明出处，支持原创是美德。
未经本人允许，请勿用于商业用途。


package cn.com.feifei.mathmatic.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lipengfei(Andrew Lee) 2013-7-25 排序的工具类
 */
public class SortUtil {

	/**
	 * 从一堆数据中随机选取一定量的值，做平均数 由于其概率的随机性，该平均数的值更接近整体数据的中间值
	 * 
	 * @author lipengfei 2013-7-25
	 * @param array
	 * @return
	 */
	public static Integer getFuzzyNum(Integer[] array) {
		
		if (array != null) {

			int size = array.length;

			int num = 3;// 默认选取3个数，但若当size大于一定程度时，则按某种算法取num的个数

			Integer value = 0;

			if (size < 3) {
				num = 1;
			} else if (size > 30) {
				num = size / 10;
			}

			if (num > 100) {// 此外，无论size的值有多大，都只随机取100个数
				num = 100;
			}

			// 随机获取m个位置的数的值，取平均数
			for (int i = 0; i < num; i++) {
				double random = Math.random();
				int position = (int) (size * random) - 1;

				if (position < 0) {
					position = 0;
				}
				value += array[position];
			}

			Integer count = 0;
			int average = value / num;
			for (int i = 0; i < array.length; i++) {
				if (array[i] < average) {
					count++;
				}
			}
			System.out.println("结果为："+average+";比随机平均数小的数的个数：" + count + ";比随机平均数大的数的个数"
					+ (size - count) + ";均差为" + ((size / 2 - count)/2));
			return value / num;
		}
		return null;
	}

	public static Float getFuzzyNum(Float[] array) {
		return null;
	}

	public static Double getFuzzyNum(Double[] array) {
		return null;
	}

	public static void main(String[] args) {

		List<Integer> array = new ArrayList<Integer>();

		int count = 10000;//每组数据10000个数
		int valueCount = 10000000;//数的大小小于10000000的任何有可能的值
		int count2 = 100;//得到一百组数据
		for (int j = 0; j < count2; j++) {
			array = new ArrayList<Integer>();
			for (int i = 0; i < count; i++) {
				int value = (int) (Math.random() * valueCount);
				array.add(value);
			}
			getFuzzyNum((Integer[])array.toArray(new Integer[0]));
			// str+=value+",";
		}
//		getFuzzyNum((Integer[]) array.toArray(new Integer[0]));
	}
}