Как мне найти среднее в БОЛЬШОМ наборе чисел?

Question

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

Это все числа с плавающей запятой.

Это не чтение из базы данных, это файл CSV, собранный из нескольких источников. Он должен быть точным, так как он хранится в долях секунды (например, 0,293482888929), и скользящее среднее может быть разницей между 0,2 и 0,3

Это набор #, представляющий, сколько времени потребовалось пользователям, чтобы ответить на определенные действия формы. Например, при отображении окна сообщения, сколько времени им потребовалось, чтобы нажать OK или Отмена. Данные были отправлены мне в виде секунд секунды. 1,2347 секунд, например. Преобразование в миллисекунды и переполнение int, long и т. Д. Довольно быстро. Даже если я не преобразую это, я все еще переполняю это довольно быстро. Я предполагаю, что один ответ ниже верен, что, возможно, мне не нужно быть на 100% точным, просто посмотрите в определенный диапазон внутри отдельного StdDev, и я был бы достаточно близко.

Answer 1

Вы можете выбрать случайным образом из вашего набора (" население "), чтобы получить среднее значение (" среднее "). Точность будет зависеть от того, насколько варьируются ваши образцы (как определено « стандартное отклонение » или дисперсия).

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

Вот числовая библиотека для C #, которая включает генератор случайных последовательностей. Просто сделайте случайную последовательность чисел, которые ссылаются на индексы в вашем массиве элементов (от 1 до x , количество элементов в вашем массиве). Разыщите, чтобы получить значения, а затем рассчитайте среднее значение и стандартное отклонение.

Если вы хотите проверить распределение ваших данных, рассмотрите возможность использования теста Chi-Squared Fit или KS , который вы найдете во многих таблицах и статистических пакетах. (например, R ). Это поможет подтвердить, пригоден ли этот подход или нет.

Answer 2

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

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

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

---

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

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

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

По сути, количество сегментов определяет количество значащих цифр в вашем среднем. Таким образом, выберите 10000 или 100000 ведер, чтобы получить 4 или 5 цифр точности. Поскольку это измерение, вероятность того, что ваши измерения состоят только из двух или трех цифр.

---

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

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

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

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

Answer 3

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

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

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

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

Answer 4

Вы имеете в виду 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);
    }
}

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

Answer 5

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

Answer 6

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

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

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

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

Answer 7

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

Дано:

A = current avg</code>
<code>C = count of items</code>
<code>V = next value in the sequence

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

      (C * A) + V
A<sub>1</sub> =  &mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;
        C + 1

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

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

A<sub>1</sub> = C/(C+1) * A/(C+1) + V/(C+1)

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

Answer 8

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

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

Answer 9

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

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

Дано:

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, что правильно.

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

Answer 10

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