Función promedio sin excepción de desbordamiento

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 me da una excepción allí. Esto se debe a la aplicación (en mi máquina) para el método de promedio de extensión, como 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 utilizar una biblioteca Bigint (sí, ya sé que es included en. NET Framework 4.0, pero estoy vinculado a 3.5).

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

Gracias!

---

ACTUALIZACIÓN:

El ejemplo anterior, de tres números enteros grandes, era sólo un ejemplo para ilustrar el problema de desbordamiento. La pregunta es sobre el cálculo de un promedio de cualquier conjunto de números que podría sumar un número grande que exceda el valor máximo del tipo. Perdón por esta confusión También cambié el título de la pregunta para evitar confusión adicional.

Gracias a todos !!

Answer 1

Esta respuesta solía sugerir almacenar el cociente y el resto (conteo de mods) por separado. Esa solución es menos eficiente en el uso del espacio y más complejo de códigos.

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

Para algoritmos de un solo paso, esto es fácil de probar. Supongamos 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. Entonces podemos multiplicar el resultado por el conteo y obtener el total. Contradicción. Por lo tanto, un algoritmo de paso único debe estar rastreando el total en algún sentido.

Por lo tanto, el algoritmo correcto más simple resumirá los elementos y dividirá por el recuento. Todo lo que tiene que hacer es elegir un tipo de entero con suficiente espacio para almacenar el total. El uso de 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 2

¿Qué tal BigInteger en Visual J #.

Answer 3

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

Sin embargo, este enfoque fallará si (m) cualquiera de los números son ahora de long.MaxValue, por lo que es caballos para los cursos ...

Answer 4

Si usted está dispuesto a sacrificar la precisión, se podría 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 5

Si sabe aproximadamente lo que será la media (o, al menos, que todos los pares de números tendrán una diferencia máxima < long.MaxValue), se puede calcular el promedio de diferencia de ese valor i en su lugar. 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 poner en práctica esto de alguna manera que hace que sea más fácil volver a utilizar, por ejemplo, como un método de extensión a IEnumerable<long>.

Answer 6

Quizás pueda reducir cada elemento calculando el promedio de valores ajustados y luego multiplíquelo por el número de elementos en la colección. Sin embargo, encontrará un número diferente de operaciones en coma 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 7

Puede mantener un promedio continuo que actualice una vez para cada número grande.

Answer 8

Si lo que buscas es una media aritmética, se 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 9

Utilice la biblioteca IntX en CodePlex.

Answer 10

Así es como lo haría si tuviera este problema. Primero definamos la clase RationalNumber muy simple, que contiene dos propiedades: Dividendo y Divisor y un operador para agregar dos números complejos. Así es como 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; } 
} 

Segunda parte es realmente fácil. Digamos que tenemos una matriz de números. Su promedio se estima en Suma (Números)/Longitud (Números), que es lo mismo que 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í es como 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 los números racionales, y un número entero, que sumamos juntos y obtener el promedio de la secuencia sin un desbordamiento. El mismo enfoque se puede tomar para cualquier tipo sin desbordamiento, y no hay pérdida de precisión.

EDIT:

Por qué esto funciona:

definir: Un conjunto de números.

si media (A) = SUM (A)/LEN (A) =>

media (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 un número racional (Y/B).

=> así

media (A) = A1 + A2 + A3 + ... + AN = X1 + X2 + X3 + X4 + ... + Reminder1 + Reminder2 + ...;

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

Answer 11

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 fo es posible que desee forzar data.ToList() o .ToArray() antes de que su proceso de este método por lo que no puede contar con la nueva consulta cada pasada. (O se le puede llamar antes de la .Select(..).Sum().)

Answer 12

Usted puede probar el siguiente enfoque:

número de elementos es let N, y los números son arr [0], .., arr [N -1].

es necesario definir las variables 2:

significa y resto.

inicialmente mean = 0, remainder = 0.

en el paso i necesita cambiar media y resto de la siguiente manera:

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

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

Answer 13

Supongo que tiene que haber un compromiso en alguna parte u otra. Si los números realmente son tan grandes, pocos dígitos de órdenes inferiores (por ejemplo, 5 dígitos más bajos) podrían no afectar tanto el resultado.

Otro problema es cuando realmente no se conoce el tamaño del conjunto de datos que entra, especialmente en casos de transmisión/tiempo real.Aquí no veo otra solución entonces el (previousAverage * oldCount + nuevoValor)/(oldCount < - oldCount + 1)

---

He aquí 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

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

Answer 15

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 16

Sea Avg (n) el promedio en el primer n número, y los datos [n] es el enésimo número.

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

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

Answer 17

Promover números de un tipo numérico específico de forma segura, aunque también solo es posible utilizar ese tipo numérico, aunque aconsejaría utilizar la ayuda de BigInteger en una implementación práctica. Creé un proyecto para Safe Numeric Calculations que tiene una estructura pequeña (Int32WithBoundedRollover) que puede sumar hasta 2^32 int32s sin desbordamiento (la estructura internamente usa dos campos int32 para hacer esto, por lo que no se usan tipos de datos más grandes).

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

Dicho esto, la implementación actual no está desarrollada para esto (por ejemplo, no hay 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 tiene demasiada importancia para los grandes promedios, ya que solo se realizará una vez, y es demasiado limpio y fácil de entender para preocuparse por encontrar algo inteligente (al menos hasta ahora ...).

En cuanto a su pregunta original que se refería al tipo de datos largos, Int32WithBoundedRollover se podría convertir a LongWithBoundedRollover simplemente cambiando las referencias int32 por referencias largas y debería funcionar de la misma manera. Para Int32s noté una gran diferencia en el rendimiento (en caso de que sea de interés). Comparado con el único método BigInteger, el método que produje es aproximadamente 80% más rápido para las muestras grandes (como 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 de software, como lo son las operaciones de BigInteger.