确定两个分布是否相同

机器算法验证 统计学意义 正态分布 非自卑
2022-03-31 11:35:05

我开发 GNU Parallel。对于每个版本,我想测试我即将发布的版本是否存在内存泄漏。

我可以测量内存使用情况。不幸的是,在相同输入的情况下,用法略有不同。内存使用量为:base+leak。基数略有不同,每个作业预计泄漏 1 位。我想检测的是是否存在比预期泄漏更大的泄漏。

对于一个版本,基数介于 13050 和 13150 kB 之间,而对于另一个版本,它可以在 15000 和 15500 kB 之间。它们或多或少呈正态分布。

很容易看出是否存在内存泄漏:只需将 1000 个作业的运行与 1000000 个作业的运行进行比较,如果存在 1 个字节/作业的泄漏,则使用量将增加 1000000 个字节,这比基础范围大内存使用情况。

但是运行 1000000 个作业大约需要 10000 秒(运行 1 个作业大约需要 0.01 秒)。那么有没有一种更快的方法可以确定是否存在比预期更大的泄漏?

我正在考虑运行 10 次运行 1000 个作业和运行 10 次运行 2000 个作业,并比较这些的内存使用分布。如果分布显着不同,则存在泄漏。我怎么做?

直觉上我可以看到,如果泄漏很大(例如,每个作业 500 字节)比泄漏很小(例如,每个作业 2 字节),您需要更少的运行和更少的作业,因此应该可以更早地停止. 我如何确定要运行多少次以及应该运行多少个作业才能获得 99% 的确定性?

(我是统计、R 和 Python 方面的新手,并且在 Perl 方面很先进。所以解决方案必须显示真实的代码,而不仅仅是参考一些统计方法;而且给出“是/否”的代码也比“目瞪口呆”更受欢迎它”)。

((理想情况下,我想要两段代码:一段我可以告诉“你有 3 分钟的时间运行。之后我想知道你对 1 字节、10 字节、100 字节和 1000 字节的内存泄漏有多大把握” ,第二个版本在运行更多运行以收集更多数据点时不断向我展示确定性。))

1个回答

在这种情况下,Kolmogorov-Smirnov 统计量可能会对您有所帮助。
下面是一个使用 Kolmogorov-Smirnov 统计的实现,该函数返回相似的概率。

#include <math.h>
#define EPS1 0.001
#define EPS2 1.0e-8

float kstest(float alam) {
    int j;
    float a2, fac = 2.0, sum = 0.0, term, termbf = 0.0;
    a2 = -2.0 * alam * alam;
    for (j = 1; j <= 100; j++) {
    term = fac * exp(a2 * j * j);
    sum += term;
    if (fabs(term) <= EPS1 * termbf || fabs(term) <= EPS2 * sum)
        return sum;
    fac = -fac;
    termbf = fabs(term);
    }
    return 1.0;
}

void checkSameDist(float data1[], unsigned long n1, float data2[],
          unsigned long n2, float *d, float *prob) {
    float           kstest(float alam);
    void            sort(unsigned long n, float arr[]);
    unsigned long   j1 = 1,
    j2 = 1;
    float d1, d2, dt, en1, en2, en, fn1 = 0.0, fn2 = 0.0;
    sort(n1, data1);
    sort(n2, data2);
    en1 = n1;
    en2 = n2;
    *d = 0.0;
    while (j1 <= n1 && j2 <= n2) {
        if ((d1 = data1[j1]) <= (d2 = data2[j2]))
            fn1 = j1++ / en1;
        if (d2 <= d1)
            fn2 = j2++ / en2;
        if ((dt = fabs(fn2 - fn1)) > *d)
            *d = dt;
    }
    en = sqrt(en1 * en2 / (en1 + en2));
    *prob = kstest((en + 0.12 + 0.11 / en) * (*d));
}

还要检查,以下函数检查特定分布是否正常,您可以对其进行一些修改(这将使您对统计数据有更多的直觉以及如何从头开始实现它
https://walteis.wordpress.com/2012 /04/26/a-kolmogorov-smirnov-implementation/ )

public bool IsNormal
{
    get
    {
        // This method uses the Kolmogorov-Smirnov test to determine a normal distribution.
        // The level of significance (alpha) used is .05, and the critical values used are from Table 1 of: 
        // The Kolmogorov-Smirnov Test for Goodness of Fit
        // Frank J. Massey, Jr.
        // Journal of the American Statistical Association
        // Vol. 46, No. 253 (Mar., 1951) (pp. 68-78)

        if (DataSet.Count == 0)
            return false;

        List<double> vals = DataSet.Values.ToList();
        Accumulator acc = new Accumulator(vals.ToArray());
        double dmax = double.MinValue;
        double cv = 0;

        MathNet.Numerics.Distributions.NormalDistribution test = new MathNet.Numerics.Distributions.NormalDistribution(acc.Mean, acc.Sigma);

        // the 0 entry is to force the list to be a base 1 index table.
        List<double> cvTable = new List<double>() { 0, .975, .842, .708, .624, .565,
                                                .521, .486, .457, .432, .410,
                                                .391, .375, .361, .349, .338,
                                                .328, .318, .309, .301, .294};

        test.EstimateDistributionParameters(DataSet.Values.ToArray());
        vals.Sort();

        for (int i = 0; i < vals.Count; i++)
        {
            double dr = Math.Abs(((i + 1) / (double)vals.Count) - test.CumulativeDistribution(vals[i]));
            double dl = Math.Abs(test.CumulativeDistribution(vals[i]) - (i / (double)vals.Count));
            dmax = Math.Max(dmax, Math.Max(dl, dr));
        }

        // get critical value and compare to d(N)
        if (vals.Count <= 10)
            cv = cvTable[vals.Count];
        else if (vals.Count > 10)
            cv = 1.36 / Math.Sqrt(vals.Count);

        return (dmax < cv);
    }
}

祝你好运