pseint - Mejor algoritmo para encontrar el promedio
ejercicios de algoritmos para resolver (7)
Estoy haciendo un ejercicio de un libro de programación A Book on C. El ejercicio sugiere que para encontrar el promedio de un grupo de números, el algoritmo:
avg += (x - avg) / i;
es mejor que:
sum += x;
avg = sum / i;
''x'' es una variable utilizada para almacenar los números de entrada. También sugiere que, además de evitar el desbordamiento, el primer algoritmo tiene otros beneficios además del segundo algoritmo. ¿Alguien puede ayudarme? ¡Gracias!
¿Qué hay de calcular así, asumiendo que los ints están en una matriz ?:
sum += x[i] / N; rem += x[i] % N;
avg = sum + rem/N;
Si N es grande (0xFFFFF) y x[i] son todos pequeños, por lo que rem agrega hasta 0xFFFF (int más grande), entonces puede ocurrir un desbordamiento.
El último algoritmo es más rápido que el anterior, porque tiene que realizar n operaciones (en realidad, el último requiere realizar 2 * n operaciones). Pero es cierto que lo primero evita el desbordamiento. Por ejemplo, si tiene este conjunto de 1000 números: 4000000 * 250, 1500000 * 500, 2000000 * 500, la suma total de todos los enteros será 2''750.000.000, pero el límite superior de un tipo de datos c ++ int Es un 2.147.483.647. Por lo tanto, estamos tratando en este caso con un problema de desbordamiento. Pero si realiza el primer algoritmo, entonces podrá resolver este problema.
Por lo tanto, le recomiendo que use el primer algoritmo si es probable que ocurra el desbordamiento, de lo contrario solo agregará operaciones adicionales. Si decide utilizar el primero de todos modos, le recomiendo que use un tipo con un rango más amplio.
Es mejor en el sentido de que calcula un promedio de ejecución, es decir, no es necesario que tenga todos sus números por adelantado. Puede calcularlo a medida que avanza, o cuando los números estén disponibles.
Me gusta más el segundo método (sumar en un bucle y dividir al final), y puedo identificar el segundo método mucho más rápido que el primero.
Las diferencias de rendimiento, en su caso, son irrelevantes.
Y, si una suma de valores desborda un tipo de datos suficientemente grande, probablemente tendrá más problemas que el cálculo de un promedio.
Ok, la respuesta no radica en desbordar la suma (ya que eso se descarta), sino como dijo Oli en "perder la precisión de gama baja". Si el promedio de los números que está sumando es mucho mayor que la distancia de cada número desde el promedio, la segunda aproximación perderá los bits de mantisa. Dado que el primer enfoque es solo observar los valores relativos, no sufre ese problema.
Por lo tanto, cualquier lista de números que sea mayor que, por ejemplo, 60 millones (para el punto flotante de precisión simple), pero los valores no varían en más de 10, debería mostrar el comportamiento.
Si está utilizando flotadores de doble precisión, el valor promedio debería ser mucho mayor. O los deltas mucho más bajos.
Supongo que estamos hablando de aritmética de punto flotante aquí (de lo contrario, el promedio "mejor" será terrible).
En el segundo método, el resultado intermedio ( sum ) tenderá a crecer sin límite, lo que significa que eventualmente perderá precisión de nivel bajo. En el primer método, el resultado intermedio debe ser de una magnitud aproximadamente similar a la de sus datos de entrada (suponiendo que su entrada no tenga un rango dinámico enorme). lo que significa que conservará mejor la precisión.
Sin embargo , puedo imaginar que a medida que crezca, el valor de (x - avg) / i volverá cada vez menos preciso (relativamente). Así que también tiene sus desventajas.
sum += x;
avg = sum / i;
En el código anterior, supongamos que tenemos números como 10000,20000, es decir, los números que contienen un gran número de dígitos, entonces el valor en suma puede exceder su valor MÁXIMO, lo que no es el caso en la primera, ya que la suma siempre se divide por ninguna de Elementos previos a su almacenamiento.
Aunque debido a los grandes tipos de datos presentes en el lenguaje de programación, esto puede no ser un problema.
Los expertos dicen "Use el tipo de datos según su aplicación y requisito".