c# - una - Función promedio sin excepción de desbordamiento

promedio c#

Question

.NET Framework 3.5.
Estoy tratando de calcular el promedio de algunos números bastante grandes.
Por ejemplo:

using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var items = new long[]
                        {
                            long.MaxValue - 100, 
                            long.MaxValue - 200, 
                            long.MaxValue - 300
                        };
        try
        {
            var avg = items.Average();
            Console.WriteLine(avg);
        }
        catch (OverflowException ex)
        {
            Console.WriteLine("can''t calculate that!");
        }
        Console.ReadLine();
    }
}

Obviamente, el resultado matemático es 9223372036854775607 ( long.MaxValue - 200 ), pero obtengo una excepción allí. Esto se debe a que la implementación (en mi máquina) del método de extensión Promedio, según lo inspeccionado por .NET Reflector es:

public static double Average(this IEnumerable<long> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    long num = 0L;
    long num2 = 0L;
    foreach (long num3 in source)
    {
        num += num3;
        num2 += 1L;
    }
    if (num2 <= 0L)
    {
        throw Error.NoElements();
    }
    return (((double) num) / ((double) num2));
}

Sé que puedo usar una biblioteca BigInt (sí, sé que está included en .NET Framework 4.0, pero estoy atada a 3.5).

Pero todavía me pregunto si hay una implementación bastante sencilla para calcular el promedio de enteros sin una biblioteca externa. ¿Por casualidad sabes acerca de tal implementación?

¡¡Gracias!!

ACTUALIZAR:

El ejemplo anterior, de tres enteros grandes, fue solo un ejemplo para ilustrar el problema del desbordamiento. La pregunta es sobre el cálculo de un promedio de cualquier conjunto de números que pueda sumar un gran número que exceda el valor máximo del tipo. Lo siento por esta confusión. También cambié el título de la pregunta para evitar confusiones adicionales.

¡¡Gracias a todos!!

Answer 1

¿Qué tal BigInteger en Visual J #.

Answer 2

Aquí está mi versión de un método de extensión que puede ayudar con esto.

    public static long Average(this IEnumerable<long> longs)
    {
        long mean = 0;
        long count = longs.Count();
        foreach (var val in longs)
        {
            mean += val / count;
        }
        return mean;
    }

Answer 3

Así es como lo haría si tuviera este problema. Primero definamos una clase RationalNumber muy simple, que contiene dos propiedades: Dividendo y Divisor y un operador para sumar dos números complejos. Aquí está cómo se ve:

public sealed class RationalNumber
{
    public RationalNumber()
    {
        this.Divisor = 1;
    }


    public static RationalNumberoperator +( RationalNumberc1, RationalNumber c2 )
    {
        RationalNumber result = new RationalNumber();

        Int64 nDividend = ( c1.Dividend * c2.Divisor ) + ( c2.Dividend * c1.Divisor );
        Int64 nDivisor = c1.Divisor * c2.Divisor;
        Int64 nReminder = nDividend % nDivisor;

        if ( nReminder == 0 )
        {
            // The number is whole
            result.Dividend = nDividend / nDivisor;
        }
        else
        {
            Int64 nGreatestCommonDivisor = FindGreatestCommonDivisor( nDividend, nDivisor );

            if ( nGreatestCommonDivisor != 0 )
            {
                nDividend = nDividend / nGreatestCommonDivisor;
                nDivisor = nDivisor / nGreatestCommonDivisor;
            }

            result.Dividend = nDividend;
            result.Divisor = nDivisor;
        }

            return result;
    }


    private static Int64 FindGreatestCommonDivisor( Int64 a, Int64 b)
    {
        Int64 nRemainder;

        while ( b != 0 )
        {
            nRemainder = a% b;
            a = b;
            b = nRemainder;
        }

        return a;
    }


    // a / b = a is devidend, b is devisor
    public Int64 Dividend   { get; set; }
    public Int64 Divisor    { get; set; }
}

La segunda parte es muy fácil. Digamos que tenemos una serie de números. Su promedio se estima por Suma (Números) / Longitud (Números), que es igual a Número [0] / Longitud + Número [1] / Longitud + ... + Número [n] / Longitud. Para poder calcular esto, representaremos cada Número [i] / Longitud como un número entero y una parte racional (recordatorio). Aquí está cómo se ve:

Int64[] aValues = new Int64[] { long.MaxValue - 100, long.MaxValue - 200, long.MaxValue - 300 };

List<RationalNumber> list = new List<RationalNumber>();
Int64 nAverage = 0;

for ( Int32 i = 0; i < aValues.Length; ++i )
{
    Int64 nReminder = aValues[ i ] % aValues.Length;
    Int64 nWhole = aValues[ i ] / aValues.Length;

    nAverage += nWhole;

    if ( nReminder != 0 )
    {
        list.Add( new RationalNumber() { Dividend = nReminder, Divisor = aValues.Length } );
    }
}

RationalNumber rationalTotal = new RationalNumber();

foreach ( var rational in list )
{
    rationalTotal += rational;
}

nAverage = nAverage + ( rationalTotal.Dividend / rationalTotal.Divisor );

Al final tenemos una lista de números racionales, y un número entero que sumamos y obtenemos el promedio de la secuencia sin un desbordamiento. Se puede adoptar el mismo enfoque para cualquier tipo sin desbordamiento, y no hay pérdida de precisión.

EDITAR:

Por qué esto funciona:

Definir: Un conjunto de números.

si el Promedio (A) = SUMA (A) / LEN (A) =>

Promedio (A) = A [0] / LEN (A) + A [1] / LEN (A) + A [2] / LEN (A) + ..... + A [N] / LEN (2) =>

si definimos que An es un número que satisface esto: An = X + (Y / LEN (A)), que es esencialmente así porque si divides A por B obtenemos X con un recordatorio de un número racional (Y / B) .

=> entonces

Promedio (A) = A1 + A2 + A3 + ... + AN = X1 + X2 + X3 + X4 + ... + Recordatorio1 + Recordatorio2 + ...;

Sume todas las partes y sume los recordatorios manteniéndolos en forma de número racional. Al final obtenemos un número entero y otro racional, que sumados dan el Promedio (A). Dependiendo de la precisión que desee, aplique esto solo al número racional al final.

Answer 4

En realidad, es posible calcular números de un tipo numérico específico de forma segura y, al mismo tiempo, usar solo ese tipo numérico, aunque aconsejaría utilizar la ayuda de BigInteger en una implementación práctica. Creé un proyecto para Cálculos numéricos seguros que tiene una estructura pequeña (Int32WithBoundedRollover) que puede sumar 2 ^ 32 int32s sin ningún desbordamiento (la estructura usa internamente dos campos int32 para hacer esto, por lo que no se usan tipos de datos más grandes).

Una vez que tenga esta suma, deberá calcular la suma / total para obtener el promedio, lo que puede hacer (aunque no lo recomendaría) creando y luego incrementando en total otra instancia de Int32WithBoundedRollover. Después de cada incremento, puede compararlo con la suma hasta que encuentre la parte entera del promedio. Desde allí puede despegar el resto y calcular la parte fraccionaria. Es probable que existan algunos trucos inteligentes para hacer esto más eficiente, pero esta estrategia básica funcionaría sin necesidad de recurrir a un tipo de datos más grande.

Dicho esto, la implementación actual no está diseñada para esto (por ejemplo, no hay un operador de comparación en Int32WithBoundedRollover, aunque no sería demasiado difícil de agregar). La razón es que es mucho más simple usar BigInteger al final para hacer el cálculo. En cuanto al rendimiento, esto no importa demasiado para grandes promedios, ya que solo se hará una vez, y es demasiado limpio y fácil de entender para preocuparse por encontrar algo inteligente (al menos hasta ahora ...).

En lo que respecta a su pregunta original relacionada con el tipo de datos largos, el Int32WithBoundedRollover se puede convertir en un LongWithBoundedRollover simplemente intercambiando las referencias int32 por referencias largas y debería funcionar igual. Para Int32s noté una diferencia bastante grande en el rendimiento (en caso de que sea de interés). En comparación con el método único de BigInteger, el método que produje es aproximadamente un 80% más rápido para las muestras grandes (como en el número total de puntos de datos) que estaba probando (el código para esto se incluye en las pruebas unitarias para la clase Int32WithBoundedRollover). Probablemente esto se deba principalmente a la diferencia entre las operaciones int32 que se realizan en hardware en lugar del software como lo son las operaciones BigInteger.

Answer 5

NextAverage = CurrentAverage + (NewValue - CurrentAverage) / (CurrentObservations + 1)

Answer 6

Podría mantener un promedio continuo que actualice una vez por cada número grande.

Answer 7

Puede intentar el siguiente enfoque:

deje que el número de elementos sea N , y los números son arr [0], .., arr [N-1].

Necesitas definir 2 variables:

media y resto

inicialmente mean = 0, remainder = 0.

En el paso i debe cambiar la media y el resto de la siguiente manera:

mean += arr[i] / N;
remainder += arr[i] % N;
mean += remainder / N;
remainder %= N;

después de N pasos obtendrá la respuesta correcta en la variable media y el resto / N será parte fraccionaria de la respuesta (no estoy seguro de que la necesite, pero de todos modos)

Answer 8

Sea Avg (n) el promedio en el primer número n, y los datos [n] son ​​el número n.

Avg(n)=(double)(n-1)/(double)n*Avg(n-1)+(double)data[n]/(double)n

Puede evitar el desbordamiento de valor, sin embargo, la precisión de pérdida cuando n es muy grande.

Answer 9

Si sabe de antemano que todos sus números van a ser ''grandes'' (en el sentido de ''mucho más long.MaxValue que cero), puede calcular el promedio de su distancia a long.MaxValue , luego el promedio de los números es long.MaxValue menos eso.

Sin embargo, este enfoque fallará si (m) alguno de los números está lejos de ser long.MaxValue . long.MaxValue de long.MaxValue , Por lo que son caballos para cursos ...

Answer 10

Si estás dispuesto a sacrificar la precisión, podrías hacer algo como:

long num2 = 0L;
foreach (long num3 in source)
{
    num2 += 1L;
}
if (num2 <= 0L)
{
    throw Error.NoElements();
}
double average = 0;
foreach (long num3 in source)
{
    average += (double)num3 / (double)num2;
}
return average;

Answer 11

Si sabe aproximadamente cuál será el promedio (o, al menos, que todos los pares de números tendrán una diferencia máxima < long.MaxValue ), puede calcular la diferencia promedio de ese valor . Tomo un ejemplo con números bajos, pero funciona igual de bien con los grandes.

// Let''s say numbers cannot exceed 40.
List<int> numbers = new List<int>() { 31 28 24 32 36 29 }; // Average: 30

List<int> diffs = new List<int>();

// This can probably be done more effectively in linq, but to show the idea:
foreach(int number in numbers.Skip(1))
{
    diffs.Add(numbers.First()-number);
}
// diffs now contains { -3 -6 1 5 -2 }

var avgDiff = diffs.Sum() / diffs.Count(); // the average is -1

// To get the average value, just add the average diff to the first value:
var totalAverage = numbers.First()+avgDiff;

Por supuesto, puede implementar esto de alguna manera que facilite su reutilización, por ejemplo, como un método de extensión a IEnumerable<long> .

Answer 12

Si solo está buscando una media aritmética, puede realizar el cálculo de la siguiente manera:

public static double Mean(this IEnumerable<long> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }

    double count = (double)source.Count();
    double mean = 0D;

    foreach(long x in source)
    {
        mean += (double)x/count;
    }

    return mean;
}

Editar:

En respuesta a los comentarios, definitivamente hay una pérdida de precisión de esta manera, debido a la realización de numerosas divisiones y adiciones. Para los valores indicados por la pregunta, esto no debería ser un problema, pero debería ser una consideración.

Answer 13

Supongo que tiene que haber un compromiso en algún lugar u otro. Si los números realmente son tan grandes, entonces algunos dígitos de órdenes más bajas (por ejemplo, 5 dígitos más bajos) podrían no afectar tanto el resultado.

Otro problema es cuando realmente no sabe el tamaño del conjunto de datos que viene, especialmente en casos de transmisión / tiempo real. Aquí no veo otra solución que no sea la (anteriorApago * oldCount + newValue) / (oldCount <- oldCount + 1)

Aquí hay una sugerencia:

*LargestDataTypePossible* currentAverage;
*SomeSuitableDatatypeSupportingRationalValues* newValue;

*int* count;
addToCurrentAverage(value){
 newValue = value/100000;
 count = count + 1;
 currentAverage = (currentAverage * (count-1) + newValue) / count;
}

getCurrentAverage(){
 return currentAverage * 100000;
}

Answer 14

Tal vez pueda reducir cada elemento calculando el promedio de los valores ajustados y luego multiplicarlo por el número de elementos en la colección. Sin embargo, encontrará un número diferente de operaciones en punto flotante.

var items = new long[] { long.MaxValue - 100, long.MaxValue - 200, long.MaxValue - 300 };
var avg = items.Average(i => i / items.Count()) * items.Count();

Answer 15

Utilice la biblioteca IntX en CodePlex.

Answer 16

Esta respuesta se utiliza para sugerir almacenar el cociente y el resto (recuento de mod) por separado. Esa solución es menos eficiente en el espacio y más compleja en código.

Para calcular con precisión el promedio, debe realizar un seguimiento del total. No hay forma de evitar esto, a menos que estés dispuesto a sacrificar la precisión. Puede intentar almacenar el total de manera elegante, pero en última instancia, debe seguirlo si el algoritmo es correcto.

Para los algoritmos de un solo paso, esto es fácil de probar. Suponga que no puede reconstruir el total de todos los elementos anteriores, dado el estado completo del algoritmo después de procesar esos elementos. Pero espera, podemos simular el algoritmo y luego recibir una serie de 0 elementos hasta que terminemos la secuencia. Luego podemos multiplicar el resultado por el conteo y obtener el total. Contradicción. Por lo tanto, un algoritmo de un solo paso debe estar siguiendo el total en algún sentido.

Por lo tanto, el algoritmo correcto más simple simplemente resumirá los elementos y se dividirá por el recuento. Todo lo que tiene que hacer es elegir un tipo de entero con espacio suficiente para almacenar el total. Usar un BigInteger no garantiza problemas, por lo que sugiero usarlo.

var total = BigInteger.Zero
var count = 0
for i in values
    count += 1
    total += i
return total / (double)count //warning: possible loss of accuracy, maybe return a Rational instead?

Answer 17

Respuesta simple con LINQ ...

var data = new[] { int.MaxValue, int.MaxValue, int.MaxValue };
var mean = (int)data.Select(d => (double)d / data.Count()).Sum();

Dependiendo del tamaño del conjunto de datos, es posible que desee forzar los data .ToList() o .ToArray() antes de procesar este método para que no pueda volver a contar en cada pase. (O puede llamarlo antes de .Select(..).Sum() .)