Determinar si dos distribuciones son iguales

Question

I desarrollar GNU Paralelo. Para cada versión me gustaría probar si la versión que estoy a punto de estrenar tiene una pérdida de memoria.

Puedo medir el uso de la memoria. Lamentablemente, el uso varía ligeramente en la misma entrada. El uso de la memoria es: base + fuga. La base varía ligeramente y no se espera una pérdida de 1 bit por puesto de trabajo. Lo que quiero es detectar si hay una mayor pérdida de la esperada fuga.

Para una liberación de la base es de entre, digamos, 13050 y 13150 kB y otra de liberación puede ser entre 15000 y 15500 kB. Están más o menos distribuidos normalmente.

Es muy fácil ver si hay una pérdida de memoria: basta con comparar las carreras de 1000 puestos de trabajo para 1000000 de puestos de trabajo y si hay una fuga de 1 byte/trabajo, entonces el uso aumentará por 1000000 bytes que es más grande que el rango de la base del uso de la memoria.

Pero la ejecución de 1000000 de los trabajos se llevará alrededor de 10000 segundos (1 trabajo toma alrededor de 0.01 segundos para correr). Entonces, ¿hay una manera más rápida en la que me puedo determinar si es probable que un mayor de lo esperado fuga?

Estoy pensando en correr 10 carreras con 1000 puestos de trabajo y 10 carreras con más de 2000 puestos de trabajo y la comparación de las distribuciones de uso de la memoria de estos. Si las distribuciones son significativamente diferentes, a continuación, hay una fuga. ¿Cómo puedo hacer eso?

Intuitivamente puedo ver que usted necesita menos carreras y menos puestos de trabajo si la fuga es grande (por ejemplo, 500 bytes por puesto de trabajo), que si la fuga es pequeña (digamos, 2 bytes por puesto de trabajo), y por lo tanto debería ser posible para detener mucho antes. ¿Cómo puedo averiguar cuánta ejecuta y cómo muchos de los trabajos que se deben ejecutar para obtener un 99% de certeza?

(Yo soy un novato en estadística, R y Python, y avanzado en Perl. De modo que una solución tendrá que mostrar el código, no sólo se refieren a algunos de los métodos estadísticos; también el código que le da un "sí/no" es preferible a "eyeballing").

((Lo ideal sería que me quieras 2 piezas de código: que puedo decir "Usted tiene 3 minutos para que se ejecute. Después de que quiero saber que tan seguro acerca de un memleak de 1 byte, 10 bytes, 100 bytes, y 1000 bytes", y la segunda versión que me muestran las certezas continuamente mientras se está ejecutando carreras más, para recoger más puntos de datos.))

Answer 1

Prueba de Kolmogorov–Smirnov estadístico puede ayudar en este caso.
La siguiente es una aplicación que utiliza el test de Kolmogorov-Smirnov estadístico y la función devuelve la probabilidad de similitud.

#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));
}

Compruebe también, la siguiente función comprueba si la distribución es normal, se podría modificar un poco (esto le daría más la intuición acerca de la estadística y ¿cómo se puede implementar desde cero
(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);
    }
}

La mejor de las Suertes