Средняя функция без исключения переполнения - PullRequest
Новая
       11

Средняя функция без исключения переполнения

19 голосов
/ 24 мая 2010

.NET Framework 3.5.
Я пытаюсь вычислить среднее значение некоторых довольно больших чисел.
Например: 

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();
    }
}

Очевидно, математический результат - 9223372036854775607 (long.MaxValue - 200), но я получаю исключение. Это связано с тем, что реализация (на моей машине) метода среднего расширения, проверенного .NET Reflector, выглядит следующим образом: 

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));
}

Я знаю, что могу использовать библиотеку BigInt (да, я знаю, что она включена в .NET Framework 4.0, но я привязан к 3.5).

Но мне все еще интересно, есть ли довольно прямая реализация вычисления среднего целого числа без внешней библиотеки. Вы случайно не знаете о такой реализации?

Спасибо !!

UPDATE:

Предыдущий пример из трех больших целых чисел был просто примером, иллюстрирующим проблему переполнения. Вопрос заключается в том, чтобы вычислить среднее значение любого набора чисел, которое может привести к большому числу, превышающему максимальное значение типа. Извините за эту путаницу. Я также изменил название вопроса, чтобы избежать дополнительной путаницы.

Спасибо всем !!

Ответы [ 17 ]

17 голосов
/ 24 мая 2010

Этот ответ использовался для того, чтобы предлагать хранить частное и остаток (mod count) отдельно. Это решение менее компактно и сложнее кода.

Для того, чтобы точно вычислить среднее значение, вы должны следить за итогом. Обойти это невозможно, если вы не готовы пожертвовать точностью. Вы можете попытаться сохранить итоговые значения причудливыми способами, но в конечном итоге вы должны отслеживать их, если алгоритм верен.

Для однопроходных алгоритмов это легко доказать. Предположим, что вы не можете восстановить общее количество всех предыдущих элементов, учитывая полное состояние алгоритма после обработки этих элементов. Но подождите, мы можем смоделировать алгоритм, получив серию из 0 элементов, пока не закончим последовательность. Затем мы можем умножить результат на количество и получить сумму. Противоречие. Следовательно, алгоритм однократного прохода должен в некотором смысле отслеживать сумму.

Поэтому самый простой правильный алгоритм просто суммирует элементы и делит их на количество. Все, что вам нужно сделать, это выбрать целочисленный тип с достаточным пространством для хранения суммы. Использование BigInteger не гарантирует никаких проблем, поэтому я предлагаю использовать это. 

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?
12 голосов
/ 24 мая 2010

Если вы просто ищете среднее арифметическое, вы можете выполнить вычисления следующим образом: 

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;
}

Edit:

В ответ на комментарии определенно происходит потеря точности из-за выполнения многочисленных делений и дополнений. Для значений, указанных в вопросе, это не должно быть проблемой, но это должно быть рассмотрение.

5 голосов
/ 24 мая 2010

Вы можете попробовать следующий подход:

пусть количество элементов равно N , а числа: arr [0], .., arr [N-1].

Вам необходимо определить 2 переменные:

означает и остаток .

изначально mean = 0, remainder = 0.

на шаге i вам необходимо изменить означает и остаток следующим образом: 

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

после N шагов, вы получите правильный ответ в означает переменную и остаток / N будет дробной частью ответа (я не уверен, что вам это нужно, но в любом случае)

2 голосов
/ 24 мая 2010

Простой ответ с LINQ ... 

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

В зависимости от размера набора данных вы можете принудительно ввести data .ToList() или .ToArray() доВаш процесс этот метод, поэтому он не может рассчитывать на каждый проход.(Или вы можете позвонить до .Select(..).Sum().)

2 голосов
/ 24 мая 2010

Если вы приблизительно знаете, каково будет среднее значение (или, по крайней мере, что все пары чисел будут иметь максимальную разницу <<code>long.MaxValue), вы можете вместо этого вычислить среднюю разницу от этого значения, Я беру пример с меньшими числами, но он одинаково хорошо работает и с большими. 

// 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;

Конечно, вы можете реализовать это некоторым способом, который облегчает повторное использование, например, как метод расширения до IEnumerable<long>.

2 голосов
/ 24 мая 2010

Вот как бы я поступил, если бы столкнулся с этой проблемой. Сначала давайте определим очень простой класс RationalNumber, который содержит два свойства - Dividend и Divisor и оператор для добавления двух комплексных чисел. Вот как это выглядит: 

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; }
}

Вторая часть действительно проста. Допустим, у нас есть массив чисел. Их среднее значение оценивается как сумма (числа) / длина (числа), что совпадает с числом [0] / длина + число [1] / длина + ... + число [n] / длина. Чтобы иметь возможность рассчитать это, мы представим каждое число [i] / длину как целое число и рациональную часть (напоминание). Вот как это выглядит: 

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 );

В конце у нас есть список рациональных чисел и целое число, которое мы суммируем и получаем среднее значение последовательности без переполнения. Тот же подход может быть использован для любого типа без переполнения, и нет потери точности.

EDIT:

Почему это работает:

Определить: набор чисел.

если Среднее (A) = СУММА (A) / LEN (A) =>

Среднее (A) = A [0] / LEN (A) + A [1] / LEN (A) + A [2] / LEN (A) + ..... + A [N] / LEN (2) =>

если мы определим An как число, которое удовлетворяет этому: An = X + (Y / LEN (A)), что, по сути, так, потому что если вы разделите A на B, мы получим X с напоминанием рациональное число (Y / B).

=> так

Среднее (A) = A1 + A2 + A3 + ... + AN = X1 + X2 + X3 + X4 + ... + Напоминание1 + Напоминание2 + ...;

Суммируйте целые части и суммируйте напоминания, сохраняя их в рациональной числовой форме. В конце мы получаем одно целое число и одно рациональное, которое в сумме дает Среднее (A). В зависимости от того, какую точность вы хотите, вы можете применить это только к рациональному числу в конце.

1 голос
/ 06 января 2011

Я думаю, что где-то должен быть компромисс. Если числа действительно становятся такими большими, то несколько цифр младших разрядов (скажем, младших 5 цифр) могут не так сильно повлиять на результат.

Другая проблема заключается в том, что вы на самом деле не знаете размер входящего набора данных, особенно в случаях потоковой передачи / реального времени. Здесь я не вижу никакого решения, кроме (previousAverage * oldCount + newValue) / (oldCount <- oldCount + 1) </p>

Вот предложение: 

*LargestDataTypePossible* currentAverage;
*SomeSuitableDatatypeSupportingRationalValues* newValue;

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

getCurrentAverage(){
 return currentAverage * 100000;
}
1 голос
/ 24 мая 2010

Если вы заранее знаете , что все ваши числа будут «большими» (в смысле «намного ближе long.MaxValue, чем ноль»), вы можете вычислить среднее значение ихрасстояние от long.MaxValue, тогда среднее число чисел будет long.MaxValue меньше, чем.

Однако этот подход потерпит неудачу, если (m) любое из чисел будет far от long.MaxValue, так что это лошади для курсов ...

0 голосов
/ 03 апреля 2013

Вот моя версия метода расширения, который может помочь с этим. 

    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;
    }
0 голосов
/ 26 февраля 2013

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

Страница:
...