sacar - registro de alumnos en c#

¿Cómo encuentro el promedio en un GRAN grupo de números?

Question

Tengo un gran número de números, probablemente en el rango de varios gigabytes. El primer problema es que no puedo almacenar todo esto en la memoria. El segundo es que cualquier intento de agregar estos resultará en un desbordamiento. Estaba pensando en usar más de un promedio móvil, pero necesita ser preciso. ¿Algunas ideas?

Estos son todos los números de punto flotante.

Esto no se lee de una base de datos, es un archivo CSV recopilado de múltiples fuentes. Tiene que ser preciso, ya que se almacena como partes de un segundo (por ejemplo, 0.293482888929) y una media móvil puede ser la diferencia entre .2 y .3

Es un conjunto de # que representa el tiempo que tardaron los usuarios en responder a ciertas acciones de formulario. Por ejemplo, cuando se muestra un buzón de mensajes, ¿cuánto tiempo les llevó presionar Aceptar o Cancelar? Los datos me fueron enviados almacenados como segundas.porciones de segundo; 1.2347 segundos por ejemplo. Convertirlo en milisegundos y desbordar int, long, etc. bastante rápido. Incluso si no lo convierto, sigo desbordándolo bastante rápido. Supongo que la respuesta a continuación es correcta, que quizás no tenga que ser 100% precisa, solo mire dentro de un cierto rango dentro de un StcDev específico y estaré lo suficientemente cerca.

Answer 1

¿Enteros o flotadores?

Si son enteros, necesita acumular una distribución de frecuencia leyendo los números y registrando cuántos de cada valor ve. Eso se puede promediar fácilmente.

Para el punto flotante, esto es un poco un problema. Dado el rango general de los flotadores y la distribución real, debe calcular un tamaño de contenedor que conserve la precisión que desea sin preservar todos los números.

Editar

Primero, necesita muestrear sus datos para obtener una media y una desviación estándar. Unos pocos miles de puntos deberían ser lo suficientemente buenos.

Entonces, necesitas determinar un rango respetable. La gente elige cosas como ± 6σ (desviaciones estándar) alrededor de la media. Dividirás este rango en tantos cubos como puedas soportar.

En efecto, el número de cubos determina el número de dígitos significativos en su promedio. Por lo tanto, elija 10,000 o 100,000 cubos para obtener 4 o 5 dígitos de precisión. Ya que es una medida, las probabilidades son buenas de que sus medidas solo tengan dos o tres dígitos.

Editar

Lo que descubrirá es que la media de su muestra inicial está muy cerca de la media de cualquier otra muestra. Y cualquier media muestral está cerca de la media poblacional. Notarás que la mayoría (pero no todos) de tus medios están con una desviación estándar de cada uno.

Debería encontrar que sus errores de medición e imprecisiones son mayores que su desviación estándar.

Esto significa que una media muestral es tan útil como una media poblacional.

Answer 2

¿No sería un promedio móvil tan preciso como cualquier otra cosa (me refiero a descontar los errores de redondeo)? Puede ser un poco lento debido a todas las divisiones.

Podrías agrupar lotes de números y promediarlos recursivamente. Como el promedio de 100 números 100 veces, entonces promedia el resultado. Esto sería menos doloroso y en su mayoría adición.

De hecho, si agregó 256 o 512 a la vez, podría cambiar el resultado en 8 o en 9, (creo que podría hacerlo en un doble simplemente cambiando la mantisa de punto flotante) - esto haría su programa es extremadamente rápido y podría escribirse de forma recursiva en solo unas pocas líneas de código (sin contar el funcionamiento inseguro del cambio de mantisa).

¿Tal vez dividir por 256 ya usaría esta optimización? Puede que tenga que acelerar la prueba dividiendo por 255 vs 256 y ver si hay alguna mejora masiva. Supongo que no.

Answer 3

¿Por qué no escalar los números (abajo) antes de calcular el promedio?

Answer 4

¿Por qué se está desbordando una suma de números de punto flotante? Para que eso suceda, deberías tener valores cercanos al valor flotante máximo, que suena extraño.

Si estuviera tratando con enteros, sugeriría usar un BigInteger o dividir el conjunto en múltiples subconjuntos, promediando recursivamente los subconjuntos, y luego promediando los promedios.

Si estás tratando con flotadores, se pone un poco raro. Una media móvil podría llegar a ser muy inexacta. Sugiero usar un promedio móvil que solo se actualiza cuando se llega a una excepción de desbordamiento o al final del conjunto. Dividiendo efectivamente el conjunto en conjuntos no desbordantes.

Answer 5

Aquí hay una forma de hacerlo en pseudocódigo:

average=first count=1 while more: count+=1 diff=next-average average+=diff/count return average

Answer 6

Dos ideas de mi parte:

• Si los números son íntegros, use una biblioteca de precisión arbitraria como IntX , aunque podría ser demasiado lento.
• Si los números son flotantes y conoce la cantidad total, puede dividir cada entrada por ese número y sumar el resultado. Si usas doble, la precisión debería ser suficiente.

Answer 7

El truco es que estás preocupado por un desbordamiento. En ese caso, todo se reduce a orden de ejecución. La fórmula básica es así:

Dado:

A = current avg C = count of items V = next value in the sequence El siguiente promedio (A ₁ ) es:

(C * A) + V A₁ = ——————————— C + 1

El peligro es que le preocupa que, en el transcurso de la evaluación de la secuencia, mientras que A debería ser relativamente manejable, C se vuelva muy grande.
Finalmente, C * A desbordará los tipos enteros o dobles.

Una cosa que podemos intentar es volver a escribirlo así, para reducir la posibilidad de un desbordamiento:

A₁ = C/(C+1) * A/(C+1) + V/(C+1)

De esta manera, nunca multiplicamos C * A y solo tratamos con números más pequeños. Pero la preocupación ahora es el resultado de las operaciones de la división. Si C es muy grande, C/C+1 (por ejemplo) puede no ser significativo cuando está limitado a las representaciones de punto flotante normal. Lo mejor que puedo sugerir es usar el tipo más grande posible para C aquí.

Answer 8

Este es un problema clásico de dividir y conquistar.

El problema es que el promedio de un gran conjunto de números es el mismo que el promedio de la primera mitad del conjunto, promediado con el promedio de la segunda mitad del conjunto.

En otras palabras:

AVG(A[1..N]) == AVG( AVG(A[1..N/2]), AVG(A[N/2..N]) )

Aquí hay una solución simple, C #, recursiva. Ha pasado mis pruebas, y debe ser completamente correcta.

public struct SubAverage
{
    public float Average;
    public int   Count;
};

static SubAverage AverageMegaList(List<float> aList)
{
    if (aList.Count <= 500) // Brute-force average 500 numbers or less.
    {
        SubAverage avg;
        avg.Average = 0;
        avg.Count   = aList.Count;
        foreach(float f in aList)
        {
            avg.Average += f;
        }
        avg.Average /= avg.Count;
        return avg;
    }

    // For more than 500 numbers, break the list into two sub-lists.
    SubAverage subAvg_A = AverageMegaList(aList.GetRange(0, aList.Count/2));
    SubAverage subAvg_B = AverageMegaList(aList.GetRange(aList.Count/2, aList.Count-aList.Count/2));

    SubAverage finalAnswer;
    finalAnswer.Average = subAvg_A.Average * subAvg_A.Count/aList.Count + 
                          subAvg_B.Average * subAvg_B.Count/aList.Count;
    finalAnswer.Count = aList.Count;

    Console.WriteLine("The average of {0} numbers is {1}",
        finalAnswer.Count, finalAnswer.Average);
    return finalAnswer;
}

Answer 9

Lo siento por el comentario tardío, pero ¿no es la fórmula anterior proporcionada por Joel Coehoorn reescrita incorrectamente?

Quiero decir, la fórmula básica es correcta:

Dado:

A = promedio actual C = cuenta de ítems V = siguiente valor en la secuencia

El siguiente promedio (A1) es:

A1 = ((C * A) + V) / (C + 1)

Pero en lugar de:

A1 = C / (C + 1) * A / (C + 1) + V / (C + 1)

no deberíamos tener

A1 = C / (C + 1) * A + V / (C + 1)

Eso explicaría el post de kastermester:

"Mi matemática marca aquí - Tienes C, que dices" ir hacia el infinito "o al menos, un número realmente grande, luego: C / (C + 1) va hacia 1. A / (C + 1) va hacia 0. V / (C + 1) va hacia 0. En general: A1 = 1 * 0 + 0 Por lo tanto, al poner brevemente A1 va hacia 0, parece un poco apagado. - kastermester "

Porque tendríamos que A1 = 1 * A + 0, es decir, A1 va hacia A, que es correcto.

He estado usando este método para calcular promedios durante mucho tiempo y los problemas de precisión antes mencionados nunca han sido un problema para mí.

Answer 10

Podría dividir los datos en conjuntos de, digamos, 1000 números, promediarlos y luego promediar los promedios.

Answer 11

Puede muestrear al azar de su conjunto (" population ") para obtener un promedio (" mean "). La precisión se determinará según la cantidad de muestras que varíen (según lo determine la " desviación estándar " o la varianza).

La ventaja es que tiene miles de millones de observaciones y solo tiene que muestrear una fracción de ellas para obtener una precisión decente o el " rango de confianza " de su elección. Si las condiciones son correctas, esto reduce la cantidad de trabajo que estará realizando.

Aquí hay una biblioteca numérica para C # que incluye un generador de secuencia aleatorio. Simplemente haga una secuencia aleatoria de números que hagan referencia a los índices en su matriz de elementos (de 1 a x , el número de elementos en su matriz). Dereferencia para obtener los valores y luego calcular su media y desviación estándar.

Si desea probar la distribución de sus datos, considere usar la prueba de ajuste Chi-cuadrado o la prueba K-S , que encontrará en muchas hojas de cálculo y paquetes estadísticos (por ejemplo, R ). Eso ayudará a confirmar si este enfoque es utilizable o no.

Answer 12

Si los números son int, acumule el total en un largo. Si los números son largos, ¿qué idioma estás usando? En Java podría acumular el total en un BigInteger, que es un entero que crecerá tan grande como sea necesario. Siempre puedes escribir tu propia clase para reproducir esta funcionalidad. La esencia de esto es simplemente hacer una matriz de enteros para mantener cada "gran número". Cuando agregue dos números, recorra en bucle comenzando con el valor de orden bajo. Si el resultado de la adición establece el bit de orden superior, borre este bit y lleve el uno a la siguiente columna.

Otra opción sería encontrar el promedio de, digamos, 1000 números a la vez. Mantenga estos resultados intermedios, luego, cuando termine, prométalos todos juntos.

Answer 13

Te refieres a números de 32 y 64 bits. Pero, ¿por qué no usar una biblioteca adecuada de Rational Big Num? Si tiene tantos datos y desea una media exacta, simplemente codifíquelos.

class RationalBignum {
    public Bignum Numerator { get; set; }
    public Bignum Denominator { get; set; }
}

class BigMeanr {
    public static int Main(string[] argv) {
        var sum = new RationalBignum(0);
        var n = new Bignum(0);
        using (var s = new FileStream(argv[0])) {
            using (var r = new BinaryReader(s)) {
                try {
                    while (true) {
                        var flt = r.ReadSingle();
                        rat = new RationalBignum(flt);
                        sum += rat;
                        n++;
                    }
                }
                catch (EndOfStreamException) {
                    break;
                }
            }
        }
        Console.WriteLine("The mean is: {0}", sum / n);
    }
}

Solo recuerda, hay más tipos numéricos que los que te ofrece tu compilador.

Answer 14

dependiendo del rango de números, puede ser una buena idea tener una matriz donde el subíndice sea su número y el valor sea la cantidad de ese número, luego puede hacer su cálculo a partir de este