许多时候,我们需要求得提供的一系列数中中间值,也就是整体数据的平均值的反应,而大部分时候我们会将这些数据先进行排序,
然后将排序好后的数据取得所有数据个数的二分之一的位置,即为整体数据的中间值。可是往往有些时候我们并不需要一个精确的在提供
的数据中存在的值,而是需要一个模糊的可以不属于提供的数据中的某一个数,却有接近整体数据的中间值,这个时候,若当整体数据个
数大于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]));
}
}
- 大小: 277 KB
分享到:
相关推荐
加载到CAD中,可用PFM命令快速求得平方米面积
任输入三个数,求得平均值,平均值程序(VB6.0源代码编写Function ave(ByVal a As Double, ByVal b As Double, ByVal c As Double) As Double
直角坐标系中非齐次热传导问题简单分解的精确解与数值解,张钧波,John C. Chai,在直角坐标系中,对非齐次热传导问题进行简单分解,以求得其精确解。与此同时,采用有限容积方法,在结构化网格中进行数值计算,
(1) 发方A用自己的私钥PVA,采用非对称RSA算法,将原文信息进行哈希(hash)运算,并对hash值进行加密,即得数字签名DS;(RSACryptoServiceProvider.SignData()) (3) 发方A用对称算法AES的对称密钥SK对原文...
算法首先通过CM算法求得不够精确的参数估计值,在所得估计值点处做平行切面.再把此切面方程与原参数估计函数方程联立,求相交曲线.在所求得的相交曲线处任取一点作为新的CM算法迭代初始值,重新进行迭代计算,进而得到...
任输入三个数,求得平均值,平均值程序(VB6.0源代码编写Function ave(ByVal a As Double, ByVal b As Double, ByVal c As Double) As Double ave = (a + b + c) / 3 End Function Private Sub Command1_Click() ...
Tsai提出的基于RAC约束(Radial Alignment Constraint)的两步法[2]先利用线性变换方法求解摄像机参数,再以求得的参数作为初始值,考虑畸变因素,利用非线性优化方法进一步提高标定精度。
数字微分纠正;一、数字微分纠正的基本原理 数字微分纠正的基本任务是实现两个二维图象之间的几何变换,因此,在数字微分纠正的过程中,必须首先确定原始图像与纠正后图像之间的几何关系。;原始图像;正射影像DOM;二、...
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干子问题,先求解子问题...如果我们能够保存解决的子问题的答案,而在需要时再找出已求得的答案,这样就可避免大量重复计算,从而得到多项式时间的算法。
利用不完全的状态概率,得到各方案的记分函数期望值与精确函数期望值的区间,根据决策者风险偏好水平,求得各方案的记分函数与精确函数的期望集结值,进而确定方案的排序结果。算例分析验证了两种方法的有效性和可行...
然后通过直接方法和假设方法的结合求得约化得到的非线性常微分方程的精确解,从而得到修正的非稳非线性Schrodinger方程的显式精确解,包括精确平面波解、钟状孤立波解、扭状孤立波解、奇异行波解和三角函数状周期波解...
基于matlab实现曲面拟合法是数字图像相关方法中的一种亚像素求解算法,通过此方法可以求得被测物体表面的全场位移.rar
传统的 QoS保障的单播路由算法都假设 IP网络结点的状态信息可以被准确地获知,但实际网 络存在许多因素使得状态信息非精确。所设计的改进算法是通过动态确定 k优路径算法( k_shor-test algorithm)中的 k值,从而确保...
伴随着网络技术和多媒体技术的飞速发展,数字水印被广泛地应用于版权保 护,数据跟踪与监视,多媒体认证等方面。针对不同的应用目的,学者们提出了 不同的解决方案及水印算法。本文从数字水印的实际应用出发,围绕着...
针对现有的非重叠视场多相机系统标定方法复杂的问题,提出了一种基于空间约束的非重叠视场相机精确标定方法。将多个小靶标分布在各自相机的视场中,拼接成大的标定平面,采用大视场相机对固连靶标进行平面测量,求得标定...
可以任意输入开始数字和结束数字,能求得起止数字间的阶乘之和
关于矩阵的特征值,学习过线性代数的读者都知道一个公式AX=bX(b是所求的特征向量)现在我们假设A的矩阵是3阶方阵:[1 1/5 3; 5 1 6; 1/3 1/6 1]。下面我们看看matlab中的代码是如何求出这个判断矩阵的最大特征值。 ...
圆柱坐标系中非齐次热传导问题简单分解方法的精确解与数值解,张钧波,张敏,在圆柱坐标系中,对非齐次热传导问题进行简单分解,并运用分离变量方法求得其精确解。与此同时,采用有限容积方法,在结构化网格
该方法使用共面特征点, 利用投影变换中的平行性约束等仿射不变量快速求得特征点摄像机坐标系空间深度值, 并作为初值求解以特征点几何约束条件建立的无约束非线性最优化目标函数, 保证最终解的精确性和收敛性。...
有一个数字组成三角形,从上向下有一个路径,在这个路径中所有的数字相加求得最大的数.