Подтвердить что ты не робот

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

.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:

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

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

4b9b3361

Ответ 1

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

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

Для однопроходных алгоритмов это легко доказать. Предположим, вы не можете восстановить общее количество всех предыдущих элементов, учитывая полное состояние алгоритма после обработки этих элементов. Но подождите, мы можем имитировать алгоритм, после чего получим серию из 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?

Ответ 2

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

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:

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

Ответ 3

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

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

Вам нужно определить две переменные:

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

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

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

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

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

Ответ 4

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

// Let 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>.

Ответ 5

Вот как я мог бы это сделать, если бы дал эту проблему. Сначала давайте определим очень простой класс 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]/Length + Number [1]/Length +... + Number [n]/Length. Чтобы иметь возможность вычислить это, мы будем представлять каждый Number [i]/Length как целое число и рациональную часть (напоминание). Вот как это выглядит:

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:

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

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

если Average (A) = SUM (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).

= > so

Среднее (A) = A1 + A2 + A3 +... + AN = X1 + X2 + X3 + X4 +... + Reminder1 + Reminder2 +...;

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

Ответ 6

Простой ответ с 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().)

Ответ 7

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

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

Ответ 8

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

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


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

*LargestDataTypePossible* currentAverage;
*SomeSuitableDatatypeSupportingRationalValues* newValue;

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

getCurrentAverage(){
 return currentAverage * 100000;
}

Ответ 9

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

Ответ 10

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

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;

Ответ 11

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

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

Ответ 12

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

Ответ 13

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

Ответ 14

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

Ответ 15

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

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

Ответ 16

Пусть Avg (n) - среднее по первому n числу, а данные [n] - n-е число.

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

Может избежать переполнения значений, но точность потерь, когда n очень велико.

Ответ 17

В действительности допустимо усреднение числа определенного числового типа безопасным способом, а также только использование этого числового типа, хотя я бы посоветовал использовать помощь BigInteger в практической реализации. Я создал проект "Безопасные числовые вычисления" , который имеет небольшую структуру (Int32WithBoundedRollover), которая может суммировать до 2 ^ 32 int32 без переполнения (структура внутренне использует два int32-поля для этого, поэтому не используются более крупные типы данных).

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

При этом текущая реализация не строится для этого (например, в Int32WithBoundedRollover нет оператора сравнения, хотя его было бы сложно добавить). Причина в том, что проще всего использовать BigInteger в конце для вычисления. Производительность мудрая, это не имеет большого значения для больших средних значений, так как это будет сделано только один раз, и просто слишком просто и легко понять, чтобы беспокоиться о том, чтобы придумать что-то умное (по крайней мере, до сих пор...).

Что касается вашего первоначального вопроса, связанного с длинным типом данных, Int32WithBoundedRollover можно преобразовать в LongWithBoundedRollover, просто заменив ссылки int32 на длинные ссылки, и он должен работать одинаково. Для Int32s я заметил довольно большую разницу в производительности (в случае, если это интересно). По сравнению с методом BigInteger метод, который я производил, примерно на 80% быстрее для больших (как в общем числе точек данных) выборок, которые я тестировал (код для этого включен в модульные тесты для класса Int32WithBoundedRollover). Скорее всего, это связано с различием между операциями int32, выполняемыми в аппаратном обеспечении, а не программным обеспечением, поскольку операции BigInteger.