Как я нахожу среднее число в БОЛЬШОМ наборе чисел?

Почему сумма чисел с плавающей запятой переполняется? Для этого вам нужно иметь значения, близкие к максимальному значению с плавающей запятой, что звучит странно.

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

Если вы имеете дело с числами с плавающей запятой, это становится немного странным. Скользящее среднее значение может быть очень неточным. Я предлагаю использовать скользящее среднее, которое обновляется только при возникновении исключения переполнения или в конце набора. Так эффективно разделение набора на непереполняющиеся множества.

Если числа являются целыми, суммируются в длинном. Если числа длинные ... какой язык вы используете? В Java вы можете накапливать общую сумму в BigInteger, который является целым числом, которое будет расти настолько, насколько это необходимо. Вы всегда можете написать свой собственный класс для воспроизведения этой функциональности. Суть в том, чтобы просто создать массив целых чисел для хранения каждого «большого числа». Когда вы складываете два числа, выполняйте цикл, начиная с младшего значения. Если в результате сложения устанавливается бит высокого порядка, очистите этот бит и перенесите его в следующий столбец.

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

Две идеи от меня:

• Если числа являются целыми, используйте библиотеку произвольной точности, например IntX - это может быть слишком медленно, хотя
• Если числа являются числами с плавающей запятой, и вы знаете общую сумму, вы можете разделить каждую запись на это число и сложить результат. Если вы используете double, точности должно хватить.

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

Вот один из способов сделать это в псевдокоде:

average=first
count=1
while more:
  count+=1
  diff=next-average
  average+=diff/count
return average

Это классическая задача типа «разделяй и властвуй».

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

Другими словами:

AVG(A[1..N]) == AVG( AVG(A[1..N/2]), AVG(A[N/2..N]) )

Вот простое рекурсивное решение C #. Он прошел мои тесты и должен быть полностью правильным.

public struct SubAverage
{
    public float Average;
    public int   Count;
};

static SubAverage AverageMegaList(List<float> aList)
{
    if (aList.Count <= 500) // Brute-force average 500 numbers or less.
    {
        SubAverage avg;
        avg.Average = 0;
        avg.Count   = aList.Count;
        foreach(float f in aList)
        {
            avg.Average += f;
        }
        avg.Average /= avg.Count;
        return avg;
    }

    // For more than 500 numbers, break the list into two sub-lists.
    SubAverage subAvg_A = AverageMegaList(aList.GetRange(0, aList.Count/2));
    SubAverage subAvg_B = AverageMegaList(aList.GetRange(aList.Count/2, aList.Count-aList.Count/2));

    SubAverage finalAnswer;
    finalAnswer.Average = subAvg_A.Average * subAvg_A.Count/aList.Count + 
                          subAvg_B.Average * subAvg_B.Count/aList.Count;
    finalAnswer.Count = aList.Count;

    Console.WriteLine("The average of {0} numbers is {1}",
        finalAnswer.Count, finalAnswer.Average);
    return finalAnswer;
}

Вы имеете в виду 32- битные и 64-битные числа. Но почему бы просто не использовать правильную библиотеку Rational Big Num? Если у вас так много данных и вы хотите получить точное среднее значение, просто закодируйте его.

class RationalBignum {
    public Bignum Numerator { get; set; }
    public Bignum Denominator { get; set; }
}

class BigMeanr {
    public static int Main(string[] argv) {
        var sum = new RationalBignum(0);
        var n = new Bignum(0);
        using (var s = new FileStream(argv[0])) {
            using (var r = new BinaryReader(s)) {
                try {
                    while (true) {
                        var flt = r.ReadSingle();
                        rat = new RationalBignum(flt);
                        sum += rat;
                        n++;
                    }
                }
                catch (EndOfStreamException) {
                    break;
                }
            }
        }
        Console.WriteLine("The mean is: {0}", sum / n);
    }
}

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

Вы можете разбить данные на наборы, скажем, из 1000 чисел, усреднить их, а затем усреднить средние значения.

Разве скользящее среднее не будет таким же точным, как все остальное (я имею в виду, не считая ошибок округления)? Это может быть немного медленным из-за всего деления.

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

Фактически, если вы добавили 256 или 512 сразу, вы могли бы сдвинуть результат на 8 или 9 (я считаю, что вы могли бы сделать это в два раза на просто изменяя мантиссу с плавающей запятой) - это сделает вашу программу чрезвычайно быстрой, и ее можно будет написать рекурсивно всего в несколько строк кода (не считая небезопасной операции сдвига мантиссы).

Возможно, при делении на 256 уже использовалась эта оптимизация? Возможно, мне придется проверить скорость деления на 255 против 256 и посмотреть, есть ли какое-то значительное улучшение. Думаю, нет.

Уловка в том, что вы беспокоитесь о переполнении. В этом случае все сводится к порядку исполнения. Основная формула выглядит так:

Дано:

A = current avg
C = count of items
V = next value in the sequence

      (C * A) + V
A1 =  ———————————
        C + 1

Опасность состоит в том, что вы беспокоитесь, что в процессе исключения последовательности, в то время как A останется относительно управляемым, C станет очень большим.
В конце концов C * A переполнит целочисленные или двойные типы.

Мы можем попробовать переписать это так, чтобы уменьшить вероятность переполнения:

A1 = C/(C+1) * A/(C+1) + V/(C+1)

Таким образом, мы никогда не умножаем C * A, а имеем дело только с меньшими числами. Но сейчас концерн - результат работы подразделения. Если C очень велико, C / C + 1 (например) может не иметь смысла, когда оно ограничено обычными представлениями с плавающей запятой. Лучшее, что я могу предложить, - это использовать здесь максимально возможный тип для C.

Целые числа или числа с плавающей запятой?

Если они целые числа, вам нужно накопить частотное распределение, считывая числа и записывая, сколько из каждого значения вы видите. Это можно легко усреднить.

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

Редактировать

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

Затем вам нужно определить приличный диапазон. Люди выбирают такие вещи, как ± 6σ (стандартное отклонение) от среднего. Вы разделите этот диапазон на столько ведер, сколько сможете выдержать.

Фактически, количество сегментов определяет количество значащих цифр в вашем среднем значении. Итак, выберите 10 000 или 100 000 ведер, чтобы получить 4 или 5 знаков точности. Поскольку это измерение, велика вероятность того, что ваши измерения содержат только две или три цифры.

Править

Вы обнаружите, что среднее значение вашей исходной выборки очень близко к среднему значению любой другой выборки. И любое среднее значение выборки близко к среднему значению генеральной совокупности. Вы заметите, что большинство (но не все) ваши средние имеют одно стандартное отклонение друг от друга.

Вы должны обнаружить, что ваши ошибки и неточности измерений больше, чем ваше стандартное отклонение.

Это означает, что выборочное среднее так же полезно, как и среднее значение генеральной совокупности.

Edit

Вы обнаружите, что среднее значение вашей исходной выборки очень близко к среднему значению любой другой выборки. И любое среднее значение выборки близко к среднему значению генеральной совокупности. Вы заметите, что большинство (но не все) ваши средние имеют одно стандартное отклонение друг от друга.

Вы должны обнаружить, что ваши ошибки и неточности измерений больше, чем ваше стандартное отклонение.

Это означает, что выборочное среднее так же полезно, как и среднее значение генеральной совокупности.

Edit

Вы обнаружите, что среднее значение вашей исходной выборки очень близко к среднему значению любой другой выборки. И любое среднее значение выборки близко к среднему значению генеральной совокупности. Вы заметите, что большинство (но не все) ваши средние имеют одно стандартное отклонение друг от друга.

Вы должны обнаружить, что ваши ошибки и неточности измерений больше, чем ваше стандартное отклонение.

Это означает, что выборочное среднее так же полезно, как и среднее значение генеральной совокупности.

Почему бы просто не масштабировать числа (вниз) перед вычислением среднего?

Извините за поздний комментарий, но разве не неправильно переписана приведенная выше формула Джоэла Кохорна?

Я имею в виду, что основной формула верна:

Дано:

A = текущее среднее значение C = количество предметов V = следующее значение в последовательности

Следующее среднее значение (A1):

A1 = ((C * A) + V) / (C + 1)

Но вместо:

A1 = C / (C + 1) * A / (C + 1) + V / (C + 1)

не должно быть:

A1 = C / (C + 1) * A + V / ( C + 1)

Это объясняет сообщение кастерместра:

«Моя математика здесь неуместна - у вас есть C, которое вы говорите« идти к бесконечности »или, по крайней мере, действительно большое число, тогда: C / (C +1) идет к 1. A / (C + 1) идет к 0. V / (C + 1) идет к 0. В общем: A1 = 1 * 0 + 0 Итак, вкратце A1 идет к 0 - кажется откусил. - kastermester "

Потому что у нас было бы A1 = 1 * A + 0, т.е. A1 идет в сторону A, и это правильно.

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