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

Для двух положительных чисел (или два отрицательных числа), я нашел очень изящное решение от здесь .

, где среднее вычисление (a+b)/2 может быть заменено a+((b-a)/2.

Вы можете сохранить скользящее среднее, которое вы обновляете один раз для каждого большого числа.

Если вы готовы пожертвовать точностью, вы можете сделать что-нибудь вроде:

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;

Вот как бы я поступил, если бы столкнулся с этой проблемой. Сначала давайте определим очень простой класс 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 );

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

РЕДАКТИРОВАТЬ:

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

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

если Среднее (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).В зависимости от того, какая точность вам нужна, вы применяете это только к рациональному числу в конце.

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

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

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

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

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

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

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

Изменить:

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

Как насчет BigInteger в Visual J #.

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

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

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

среднее и остаток .

изначально среднее = 0, остаток = 0.

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

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

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

Если вы приблизительно знаете, каким будет среднее значение (или, по крайней мере, что все пары чисел будут иметь максимальную разницу < 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 .

Используйте библиотеку IntX на CodePlex.

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

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