que - sacar promedio de un arreglo de calificaciones en java

¿Cuál es una buena solución para calcular un promedio donde la suma de todos los valores excede los límites de un doble? (18)

Tengo un requisito para calcular el promedio de un conjunto muy grande de dobles (10 ^ 9 valores). La suma de los valores excede el límite superior de un doble, por lo que ¿alguien sabe algunos pequeños trucos para calcular un promedio que no requiere también el cálculo de la suma?

Estoy usando Java 1.5.

(n ₁ + n ₂ + ... + n _k ) / k = (n ₁ + n ₂ ) / k + (n ₃ + n ₄ ) / k + ... + (n _k-1 + n _k ) / k, si k es par

(n ₁ + n ₂ + ... + n _k ) / k = n ₁ / k + (n ₂ + n ₃ ) / k + ... + (n _k-1 + n _k ) / k, si k es impar

Además de utilizar los mejores enfoques ya sugeridos, puede usar BigDecimal para hacer sus cálculos. (Tenga en cuenta que es inmutable)

Antes que nada, familiarícese con la representación interna de los valores double . Wikipedia debería ser un buen punto de partida.

Luego, considere que los dobles se expresan como "valor más exponente" donde el exponente es una potencia de dos. ¡El límite del valor doble más grande es un límite superior del exponente, y no un límite del valor! Entonces puedes dividir todos los números grandes de entrada por una potencia suficientemente grande de dos. Esto debería ser seguro para todos los números suficientemente grandes. Puede volver a multiplicar el resultado con el factor para verificar si perdió precisión con la multiplicación.

Aquí vamos con un algoritmo

public static double sum(double[] numbers) { double eachSum, tempSum; double factor = Math.pow(2.0,30); // about as large as 10^9 for (double each: numbers) { double temp = each / factor; if (t * factor != each) { eachSum += each; else { tempSum += temp; } } return (tempSum / numbers.length) * factor + (eachSum / numbers.length); }

y no te preocupes por la división y la multiplicación adicionales. La FPU los optimizará al máximo, ya que están hechos con una potencia de dos (para comparar, imagina agregar y eliminar dígitos al final de los números decimales).

PD: además, puede usar la suma de Kahan para mejorar la precisión. La suma de Kahan evita la pérdida de precisión cuando se suman números muy grandes y muy pequeños.

Así que no me repito tanto, permítanme decir que asumo que la lista de números se distribuye normalmente, y que puede sumar muchos números antes de que se desborde. La técnica aún funciona para las distribuciones no normales, pero algunas no cumplirán con las expectativas que describo a continuación.

Resuma una subserie, haga un seguimiento de cuántos números come, hasta que llegue al desbordamiento, luego tome la media. Esto le dará un a0 promedio y contará n0. Repita hasta agotar la lista. Ahora deberías tener muchos ai, ni.

Cada ai y ni debería estar relativamente cerca, con la posible excepción del último bocado de la lista. Puede mitigar eso sub-mordiendo cerca del final de la lista.

Puede combinar cualquier subconjunto de estos ai, ni eligiendo cualquier ni en el subconjunto (llámelo np) y dividiendo todos los ni en el subconjunto por ese valor. El tamaño máximo de los subconjuntos para combinar es el valor aproximadamente constante de las n.

El ni / np debe estar cerca de uno. Ahora suma ni / np * ai y multiple by np / (sum ni), haciendo un seguimiento de sum ni. Esto le da una nueva combinación ni, ai, si necesita repetir el procedimiento.

Si necesita repetir (es decir, el número de pares ai, ni es mucho más grande que el típico ni), intente mantener constantes los n tamaños relativos combinando todos los promedios en un nivel n primero, luego combinando en el siguiente nivel, y así.

Considera esto:

avg(n1) : n1 = a1 avg(n1, n2) : ((1/2)*n1)+((1/2)*n2) = ((1/2)*a1)+((1/2)*n2) = a2 avg(n1, n2, n3) : ((1/3)*n1)+((1/3)*n2)+((1/3)*n3) = ((2/3)*a2)+((1/3)*n3) = a3

Entonces, para cualquier conjunto de dobles de tamaño arbitrario, podrías hacer esto (esto está en C #, pero estoy bastante seguro de que podría traducirse fácilmente a Java):

static double GetAverage(IEnumerable<double> values) { int i = 0; double avg = 0.0; foreach (double value in values) { avg = (((double)i / (double)(i + 1)) * avg) + ((1.0 / (double)(i + 1)) * value); i++; } return avg; }

En realidad, esto se simplifica muy bien en (ya proporcionado por martinus):

static double GetAverage(IEnumerable<double> values) { int i = 1; double avg = 0.0; foreach (double value in values) { avg += (value - avg) / (i++); } return avg; }

Escribí una prueba rápida para probar esta función frente al método más convencional de resumir los valores y dividir por el recuento ( GetAverage_old ). Para mi entrada escribí esta función rápida para devolver tantos dobles positivos aleatorios como desee:

static IEnumerable<double> GetRandomDoubles(long numValues, double maxValue, int seed) { Random r = new Random(seed); for (long i = 0L; i < numValues; i++) yield return r.NextDouble() * maxValue; yield break; }

Y aquí están los resultados de algunos ensayos de prueba:

long N = 100L; double max = double.MaxValue * 0.01; IEnumerable<double> doubles = GetRandomDoubles(N, max, 0); double oldWay = GetAverage_old(doubles); // 1.00535024998431E+306 double newWay = GetAverage(doubles); // 1.00535024998431E+306 doubles = GetRandomDoubles(N, max, 1); oldWay = GetAverage_old(doubles); // 8.75142021696299E+305 newWay = GetAverage(doubles); // 8.75142021696299E+305 doubles = GetRandomDoubles(N, max, 2); oldWay = GetAverage_old(doubles); // 8.70772312848651E+305 newWay = GetAverage(doubles); // 8.70772312848651E+305

OK, pero ¿qué pasa con los valores de 10 ^ 9?

long N = 1000000000; double max = 100.0; // we start small, to verify accuracy IEnumerable<double> doubles = GetRandomDoubles(N, max, 0); double oldWay = GetAverage_old(doubles); // 49.9994879713857 double newWay = GetAverage(doubles); // 49.9994879713868 -- pretty close max = double.MaxValue * 0.001; // now let''s try something enormous doubles = GetRandomDoubles(N, max, 0); oldWay = GetAverage_old(doubles); // Infinity newWay = GetAverage(doubles); // 8.98837362725198E+305 -- no overflow

Naturalmente, cuán aceptable es esta solución dependerá de sus requisitos de precisión. Pero vale la pena considerarlo.

Consulte la sección de promedio móvil acumulativo

El primer problema que quisiera hacerte es este:

¿Conoces el número de valores de antemano?

Si no, entonces no tiene más remedio que sumar, contar y dividir, hacer el promedio. Si Double no tiene la precisión suficiente para manejar esto, entonces, mala suerte, no puedes usar Double , necesitas encontrar un tipo de datos que pueda manejarlo.

Si, por otro lado, conoce el número de valores de antemano, puede ver lo que realmente está haciendo y cambiar cómo lo hace, pero mantenga el resultado general.

El promedio de N valores, almacenados en alguna colección A, es este:

/ A[0] A[1] A[2] / / A[3] A[4] A[5] / // A[N-1] A[N] / | ---- + ---- + ---- | | ---- + ---- + ---- | // + ------ + ---- | / 3 3 3 / / 3 3 3 / // 3 3 / --------------------- + -------------------- + // -------------- N N N --- --- --- 3 3 3

Para calcular subconjuntos de este resultado, puede dividir el cálculo en conjuntos de igual tamaño, de modo que pueda hacer esto, para conjuntos de 3 valores (suponiendo que el número de valores sea divisible por 3, de lo contrario, necesitará un divisor diferente)

/ 1 2 3 / / 4 5 6 / / 7 / | - + - + - | + | - + - + - | + | - | / 3 3 3 / / 3 3 3 / / 3 / ----------- ----------- --- y y y

Tenga en cuenta que necesita conjuntos del mismo tamaño , de lo contrario, los números en el último conjunto, que no tendrán suficientes valores en comparación con todos los conjuntos anteriores, tendrán un mayor impacto en el resultado final.

Considere los números del 1 al 7 en secuencia, si elige un tamaño de conjunto de 3, obtendrá este resultado:

2 5 7/3 - + - + --- y y y

lo que da:

2 5 7/3 - + - + --- 3 3 3

Si y es 3 para todos los conjuntos, obtienes esto:

2*3 5*3 7 --- + --- + --- 9 9 9

lo que da:

6 15 7 - + -- + - 9 9 9

cual es:

28 -- ~ 3,1111111111111111111111.........1111111......... 9

que suma:

double mean(double[] ary) { double avg = 0; int t = 1; for (double x : ary) { avg += (x - avg) / t; ++t; } return avg; }

El promedio de 1-7 es 4. Obviamente esto no funcionará. Tenga en cuenta que si realiza el ejercicio anterior con los números 1, 2, 3, 4, 5, 6, 7, 0, 0 (observe los dos ceros al final), obtendrá el resultado anterior.

En otras palabras, si no puede dividir el número de valores en conjuntos de igual tamaño, el último conjunto se contará como si tuviera el mismo número de valores que todos los conjuntos anteriores, pero se rellenará con ceros para todos los valores perdidos

Entonces, necesitas conjuntos de igual tamaño . Difícil suerte si su conjunto de entrada original consiste en un número primo de valores.

Lo que me preocupa aquí es la pérdida de precisión. No estoy del todo seguro de que Double te brinde la precisión suficiente en tal caso, si inicialmente no puede contener la suma total de los valores.

En mi humilde opinión, la forma más sólida de resolver su problema es

clasifica tu conjunto
dividir en grupos de elementos cuya suma no se desborde, ya que están ordenados, esto es rápido y fácil
hacer la suma en cada grupo - y dividir por el tamaño del grupo
haga la suma de las sumas del grupo (posiblemente llamando a este mismo algoritmo recursivamente) - tenga en cuenta que si los grupos no tendrán el mismo tamaño, tendrá que ponderarlos por su tamaño

Una cosa buena de este enfoque es que se escala bien si tiene una gran cantidad de elementos para sumar, y una gran cantidad de procesadores / máquinas para usar para hacer los cálculos.

La opción 1 es usar una biblioteca de precisión arbitraria para que no tenga un límite superior.

Otras opciones (que pierden precisión) son sumar en grupos en lugar de hacerlo todos a la vez, o dividir antes de sumar.

Para mantener la lógica simple y mantener el rendimiento no el mejor, pero aceptable, le recomiendo que utilice BigDecimal junto con el tipo primitivo. El concepto es muy simple, se usa el tipo primitivo para sumar valores, siempre que el valor se desborde o desborde, se mueve el valor calculado al BigDecimal, luego se reinicia para el siguiente cálculo de la suma. Una cosa más que debes tener en cuenta es que cuando construyes BigDecimal, siempre debes usar String en lugar de double.

BigDecimal average(double[] values){ BigDecimal totalSum = BigDecimal.ZERO; double tempSum = 0.00; for (double value : values){ if (isOutOfRange(tempSum, value)) { totalSum = sum(totalSum, tempSum); tempSum = 0.00; } tempSum += value; } totalSum = sum(totalSum, tempSum); BigDecimal count = new BigDecimal(values.length); return totalSum.divide(count); } BigDecimal sum(BigDecimal val1, double val2){ BigDecimal val = new BigDecimal(String.valueOf(val2)); return val1.add(val); } boolean isOutOfRange(double sum, double value){ // because sum + value > max will be error if both sum and value are positive // so I adapt the equation to be value > max - sum if(sum >= 0.00 && value > Double.MAX - sum){ return true; } // because sum + value < min will be error if both sum and value are negative // so I adapt the equation to be value < min - sum if(sum < 0.00 && value < Double.MIN - sum){ return true; } return false; }

A partir de este concepto, cada vez que el resultado sea subdesbordamiento o desbordamiento, mantendremos ese valor en la variable más grande, esta solución podría ralentizar un poco el rendimiento debido al cálculo BigDecimal, pero garantiza la estabilidad del tiempo de ejecución.

Por favor aclare los rangos potenciales de los valores.

Dado que un doble tiene un rango ~ = +/- 10 ^ 308, y está sumando 10 ^ 9 valores, el rango aparente sugerido en su pregunta es valores del orden de 10 ^ 299.

Eso parece algo, bueno, poco probable ...

Si sus valores son realmente tan grandes, entonces con un doble normal solo tiene 17 dígitos decimales significativos para jugar, por lo que estará desperdiciando aproximadamente 280 dígitos de información antes de que pueda siquiera pensar en promediar los valores.

También señalaría (ya que nadie más lo ha hecho) que para cualquier conjunto de números X :

mean(X) = sum(X[i] - c) + c ------------- N

para cualquier constante arbitraria c .

En este problema particular, establecer c = min(X) podría reducir drásticamente el riesgo de desbordamiento durante la suma.

¿Puedo sugerir humildemente que la declaración del problema es incompleta ...?

Por qué tantas respuestas largas complicadas. Esta es la forma más sencilla de encontrar el promedio actual hasta ahora sin necesidad de saber cuántos elementos o tamaño, etc.

long int i = 0; promedio doble = 0; while (todavía hay elementos) {average = average * (i / i + 1) + X [i] / (i + 1); i ++; } promedio de retorno;

Publiqué una respuesta a una pregunta generada a partir de esta, dándome cuenta después de que mi respuesta es más adecuada para esta pregunta que para esa. Lo he reproducido a continuación. Sin embargo, noto que mi respuesta es similar a una combinación de Bozho''s y Anon.''s Anon.''s

Como la otra pregunta estaba etiquetada como independiente del idioma, elegí C # para la muestra del código que he incluido. Su relativa facilidad de uso y su sintaxis fácil de seguir, junto con la inclusión de un par de funciones que facilitan esta rutina (una función DivRem en BCL y soporte para funciones de iterador), así como mi propia familiaridad con ella, es una buena elección para este problema. Dado que el OP aquí está interesado en una solución Java, pero no soy lo suficientemente fluido como para escribir de manera efectiva, sería bueno que alguien pudiera agregar una traducción de este código a Java.

Algunas de las soluciones matemáticas aquí son muy buenas. Aquí hay una solución técnica simple.

Use un tipo de datos más grande. Esto se divide en dos posibilidades:

Use una biblioteca de punto flotante de alta precisión. Quien encuentra la necesidad de promediar un billón de números probablemente tenga los recursos para comprar, o la capacidad intelectual para escribir, una biblioteca de punto flotante de 128 bits (o más).
Entiendo los inconvenientes aquí. Sin duda sería más lento que el uso de tipos intrínsecos. Aún puede aumentar / disminuir si la cantidad de valores aumenta demasiado. Yada yada.
Si sus valores son enteros o pueden escalarse fácilmente a enteros, mantenga su suma en una lista de enteros. Cuando desbordes, simplemente agrega otro entero. Esto es esencialmente una implementación simplificada de la primera opción. Un ejemplo simple ~~(no probado)~~ en C # sigue

class BigMeanSet{ List<uint> list = new List<uint>(); public double GetAverage(IEnumerable<uint> values){ list.Clear(); list.Add(0); uint count = 0; foreach(uint value in values){ Add(0, value); count++; } return DivideBy(count); } void Add(int listIndex, uint value){ if((list[listIndex] += value) < value){ // then overflow has ocurred if(list.Count == listIndex + 1) list.Add(0); Add(listIndex + 1, 1); } } double DivideBy(uint count){ const double shift = 4.0 * 1024 * 1024 * 1024; double rtn = 0; long remainder = 0; for(int i = list.Count - 1; i >= 0; i--){ rtn *= shift; remainder <<= 32; rtn += Math.DivRem(remainder + list[i], count, out remainder); } rtn += remainder / (double)count; return rtn; } }

Como dije, esto no se ha probado: no tengo mil millones de valores que realmente quiero promediar, así que probablemente cometí un error o dos, especialmente en la función DivideBy , pero debería demostrar la idea general.

Esto debería proporcionar tanta precisión como un doble puede representar y debería funcionar para cualquier cantidad de elementos de 32 bits, hasta 2 ³² - 1. Si se necesitan más elementos, entonces la variable de count se deberá expandir y la función DivideBy aumentará en complejidad, pero lo dejo como un ejercicio para el lector.

En términos de eficiencia, debería ser tan rápido o más rápido que cualquier otra técnica aquí, ya que solo requiere iterar por la lista una sola vez, solo realiza una operación de división (bueno, un conjunto de ellas), y hace la mayor parte de su trabajo con enteros . Sin embargo, no lo optimicé, y estoy seguro de que podría hacerse un poco más rápido aún si fuera necesario. Anular la llamada a la función recursiva e indexar la lista sería un buen comienzo. De nuevo, un ejercicio para el lector. El código está destinado a ser fácil de entender.

~~Si alguien más motivado que yo en este momento siente que verifica la exactitud del código, y solucionando cualquier problema que pueda haber, sea mi invitado.~~

Ahora probé este código e hice un par de pequeñas correcciones (un par de paréntesis faltantes en la llamada de constructor List<uint> , y un divisor incorrecto en la división final de la función DivideBy ).

Lo probé ejecutándolo primero a través de 1000 conjuntos de longitud aleatoria (que van de 1 a 1000) llenos con enteros aleatorios (que varían entre 0 y 2 ³² - 1). Estos fueron conjuntos para los que pude verificar la exactitud fácil y rápidamente al ejecutar también una media canónica sobre ellos.

Luego probé con 100 ^* series grandes, con una longitud aleatoria de entre 10 ⁵ y 10 ⁹ . Los límites inferior y superior de estas series también se eligieron al azar, restringidos para que la serie se ajustara dentro del rango de un entero de 32 bits. Para cualquier serie, los resultados son fácilmente verificables como (lowerbound + upperbound) / 2 .

^{_{^* Está bien, esa es una pequeña mentira blanca.}} ^{_{Aborté la prueba de la serie grande después de aproximadamente 20 o 30 carreras exitosas.}} ^{_{Una serie de 10 ⁹ de longitud requiere poco menos de un minuto y medio para funcionar en mi máquina, así que media hora más o menos de probar esta rutina fue suficiente para mi gusto.}}

Para aquellos interesados, mi código de prueba es el siguiente:

static IEnumerable<uint> GetSeries(uint lowerbound, uint upperbound){ for(uint i = lowerbound; i <= upperbound; i++) yield return i; } static void Test(){ Console.BufferHeight = 1200; Random rnd = new Random(); for(int i = 0; i < 1000; i++){ uint[] numbers = new uint[rnd.Next(1, 1000)]; for(int j = 0; j < numbers.Length; j++) numbers[j] = (uint)rnd.Next(); double sum = 0; foreach(uint n in numbers) sum += n; double avg = sum / numbers.Length; double ans = new BigMeanSet().GetAverage(numbers); Console.WriteLine("{0}: {1} - {2} = {3}", numbers.Length, avg, ans, avg - ans); if(avg != ans) Debugger.Break(); } for(int i = 0; i < 100; i++){ uint length = (uint)rnd.Next(100000, 1000000001); uint lowerbound = (uint)rnd.Next(int.MaxValue - (int)length); uint upperbound = lowerbound + length; double avg = ((double)lowerbound + upperbound) / 2; double ans = new BigMeanSet().GetAverage(GetSeries(lowerbound, upperbound)); Console.WriteLine("{0}: {1} - {2} = {3}", length, avg, ans, avg - ans); if(avg != ans) Debugger.Break(); } }

Puede tomar el promedio de promedios de subconjuntos de números de igual tamaño que no excedan el límite.

Puedes calcular la media iterativamente . Este algoritmo es simple, rápido, debe procesar cada valor una sola vez, y las variables nunca superan el valor más grande del conjunto, por lo que no obtendrá un desbordamiento.

A[0] A[1] A[2] A[3] A[N-1] A[N] ---- + ---- + ---- + ---- + .... + ------ + ---- N N N N N N

Dentro de la avg bucle siempre está el valor promedio de todos los valores procesados hasta el momento. En otras palabras, si todos los valores son finitos, no debería obtener un desbordamiento.

Un doble se puede dividir por una potencia de 2 sin pérdida de precisión. Entonces, si su único problema es el tamaño absoluto de la suma, puede preescalar sus números antes de sumarlos. Pero con un conjunto de datos de este tamaño, aún existe el riesgo de que se llegue a una situación en la que se agregan números pequeños a uno grande, y los números pequeños terminarán siendo ignorados (o completamente) en su mayoría.

por ejemplo, cuando agrega 2.2e-20 a 9.0e20, el resultado es 9.0e20 porque una vez que las escalas se ajustan para que se puedan sumar, el número menor es 0. Los dobles solo pueden contener alrededor de 17 dígitos, y usted necesita más de 40 dígitos para sumar estos dos números sin pérdida.

Entonces, dependiendo de su conjunto de datos y de cuántos dígitos de precisión puede permitirse perder, es posible que deba hacer otras cosas. Romper los datos en conjuntos ayudará, pero una mejor manera de preservar la precisión podría ser determinar un promedio aproximado (es posible que ya conozca este número). luego reste cada valor del promedio aproximado antes de sumarlo. De esa manera, estás sumando las distancias del promedio, por lo que tu suma nunca debería ser muy grande.

Luego tomas el delta promedio y lo agregas a tu suma aproximada para obtener el promedio correcto. Hacer un seguimiento del delta mínimo y máximo también le indicará cuánta precisión perdió durante el proceso de suma. Si tiene mucho tiempo y necesita un resultado muy preciso, puede repetirlo.

Un muestreo aleatorio de un conjunto pequeño del conjunto de datos completo a menudo dará como resultado una solución "lo suficientemente buena". Obviamente tiene que tomar esta determinación usted mismo en función de los requisitos del sistema. El tamaño de la muestra puede ser notablemente pequeño y aún así obtener respuestas razonablemente buenas. Esto se puede calcular de manera adaptativa calculando el promedio de un número creciente de muestras elegidas al azar: el promedio convergerá dentro de algún intervalo.

El muestreo no solo aborda la doble preocupación de desbordamiento, sino que es mucho, mucho más rápido. No se aplica a todos los problemas, pero ciertamente es útil para muchos problemas.

divide todos los valores por el tamaño establecido y luego resúmelo