Как сократить вычисление среднего значения до подмножеств в общем виде?

Question

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

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

Было несколько ответов, в которых говорилось, что нужно вычислять в наборах, например, взять 50 и 50 чисел и вычислить среднее значение внутри этих наборов, а затем, наконец, взять среднее из всех этих наборов и объединить их, чтобы получить окончательное среднее значение.

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

В основном, при произвольном количестве значений, где:

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

как рассчитать среднее?

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

Обратите внимание, что я достаточно хорошо знаю математику, чтобы знать, что в терминах математической теории вычисление суммы A[1..N]/N даст мне среднее значение, давайте предположим, что есть причины, по которым это не так просто, и мне нужно разделить рабочую нагрузку, и что число значений не обязательно будет делиться на 3, 7, 50, 1000 или что-то еще.

Другими словами, решение, которое я ищу, должно быть общим.

---

Из этого вопроса:

• Какое хорошее решение для расчета среднего, если сумма всех значений превышает пределы двойного?

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

---

Редактировать : Первоначальный вопрос касался верхнего предела, который мог содержать конкретный тип данных, и поскольку он суммировал много чисел (в качестве примера было приведено 10 ^ 9), тип данных не может содержать сумму. Поскольку это было проблемой в исходном решении, я предполагаю (и это является обязательным условием для моего вопроса, извините, что пропустил это), что цифры слишком велики, чтобы давать какие-либо значимые ответы.

Итак, деление на общее количество значений напрямую отсутствует. Первоначальная причина, по которой было выбрано нормальное решение SUM / COUNT, заключалась в том, что SUM переполняется, но давайте предположим, что для этого вопроса SET-SET / SET-SIZE будет недопустимым, или что-то еще.

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

---

Позвольте мне изложить проблему.

Предположим, вы собираетесь вычислить среднее число от 1 до 6, но вы не можете (по какой-либо причине) сделать это путем суммирования чисел, подсчета чисел, а затем деления суммы на количество. Другими словами, вы не можете просто сделать (1 + 2 + 3 + 4 + 5 + 6) /6.

Другими словами, SUM(1..6)/COUNT(1..6) отсутствует. Мы не рассматриваем NULL (как в базе данных NULL) здесь.

Некоторые из ответов на этот вопрос ссылались на возможность разбить усредняемые числа на наборы, скажем, 3 или 50 или 1000 чисел, затем вычислить некоторое число для этого и затем, наконец, объединить эти значения, чтобы получить окончательное среднее.

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

Например, чтобы вычислить среднее значение 1-6, вы можете разделить его на наборы из 3 чисел, например:

/ 1   2   3 \   / 4   5   6 \
| - + - + - | + | - + - + - |
\ 3   3   3 /   \ 3   3   3 /  <-- 3 because 3 numbers in the set
 ----------      -----------
      2               2        <-- 2 because 2 equally sized groups

Что дает вам это:

      2               5
      -       +       - = 3.5
      2               2

(примечание: (1 + 2 + 3 + 4 + 5 + 6) / 6 = 3,5, так что здесь все правильно)

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

Может ли подобный подход, который не будет суммировать все значений и считать все значений, за один раз, сработает?

Так есть ли такой подход? Как рассчитать среднее для произвольного числа значений, в которых выполняется следующее:

1. По какой-то причине я не могу использовать нормальный метод суммирования / подсчета
2. Я заранее знаю количество значений (что, если я не знаю, изменит ли это ответ?)

Answer 1

Хорошо, предположим, что вы добавили три числа и поделили на три, а затем добавили два числа и поделили на два. Можете ли вы получить среднее значение от этих?

x = (a + b + c) / 3
y = (d + e) / 2
z = (f + g) / 2

А ты хочешь

r = (a + b + c + d + e + f + g) / 7

Это равно

r = (3 * (a + b + c) / 3 + 2 * (d + e) / 2 + 2 * (f + g) / 2) / 7
r = (3 * x + 2 * y + 2 * z) / 7

Обе строки выше, конечно, переполнены, но так как деление является дистрибутивным, мы делаем

r = (3.0 / 7.0) * x + (2.0 / 7.0) * y + (2.0 / 7.0) * z

Что гарантирует, что вы не переполнитесь, так как я умножаю x, y и z на доли меньше единицы.

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

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

И нет, если вы заранее не знаете значения, это ничего не изменит (при условии, что вы можете считать их по мере их суммирования).

Вот функция Scala, которая делает это. Это не идиоматическая Scala, так что ее легче понять:

def avg(input: List[Double]): Double = {
  var partialAverages: List[(Double, Int)] = Nil
  var inputLength = 0
  var currentSum = 0.0
  var currentCount = 0
  var numbers = input

  while (numbers.nonEmpty) {
    val number = numbers.head
    val rest = numbers.tail
    if (number > 0 && currentSum > 0 && Double.MaxValue - currentSum < number) {
      partialAverages = (currentSum / currentCount, currentCount) :: partialAverages
      currentSum = 0
      currentCount = 0
    } else if (number < 0 && currentSum < 0 && Double.MinValue - currentSum > number) {
      partialAverages = (currentSum / currentCount, currentCount) :: partialAverages
      currentSum = 0
      currentCount = 0
    }
    currentSum += number
    currentCount += 1
    inputLength += 1
    numbers = rest
  }
  partialAverages = (currentSum / currentCount, currentCount) :: partialAverages

  var result = 0.0
  while (partialAverages.nonEmpty) {
    val ((partialSum, partialCount) :: rest) = partialAverages
    result += partialSum * (partialCount.toDouble / inputLength)
    partialAverages = rest
  }

  result
}

EDIT: Не умножится ли на 2 и 3, вернет ли меня обратно в диапазон "не поддерживает тип данных?"

Нет. Если вы погружались к 7 в конце, абсолютно. Но здесь вы делите на каждом шаге суммы. Даже в вашем реальном случае веса (2/7 и 3/7) будут в диапазоне управляемых чисел (например, 1/10 ~ 1/10000), которые не будут иметь большого значения по сравнению с вашим весом (то есть * 1030). *).

PS: мне интересно, почему я работаю над этим ответом, а не пишу свой, где я могу заработать свой представитель: -)

Answer 2

Если вы заранее знаете количество значений (скажем, это N), просто добавьте 1/N + 2/N + 3/N и т. Д., Предположив, что у вас есть значения 1, 2, 3. Вы можете разделить это на столько вычислений, сколько захотите, и просто сложить свои результаты. Это может привести к небольшой потере точности, но это не должно вызывать проблем, если вам не нужен сверхточный результат.

Если вы не знаете, сколько предметов заблаговременно, возможно, вам нужно быть более креативным. Но вы можете, опять же, делать это постепенно. Скажите, что список 1, 2, 3, 4. Начните с mean = 1. Тогда mean = mean*(1/2) + 2*(1/2). Тогда mean = mean*(2/3) + 3*(1/3). Затем mean = mean*(3/4) + 4*(1/4) и т. Д. Легко обобщить, и вам просто нужно убедиться, что количества в скобках рассчитаны заранее, чтобы предотвратить переполнение.

Конечно, если вам нужна предельная точность (скажем, точность более 0,001%), вам, возможно, придется быть немного более осторожным, чем это, но в противном случае у вас все будет хорошо.

Answer 3

Пусть X будет вашим набором образцов. Разбейте его на два набора A и B любым удобным для вас способом. Определите delta = m_B - m_A, где m_S обозначает среднее значение множества S. Тогда

m_X = m_A + delta * |B| / |X|

где |S| обозначает мощность множества S. Теперь вы можете повторно применить это к разделу и вычислить среднее значение.

Почему это правда? Пусть s = 1 / |A| и t = 1 / |B| и u = 1 / |X| (для удобства обозначений) и пусть aSigma и bSigma обозначают сумму элементов в A и B соответственно, так что:

  m_A + delta * |B| / |X|
= s * aSigma + u * |B| * (t * bSigma - s * aSigma)
= s * aSigma + u * (bSigma - |B| * s * aSigma)
= s * aSigma + u * bSigma - u * |B| * s * aSigma
= s * aSigma * (1 - u * |B|) + u * bSigma
= s * aSigma * (u * |X| - u * |B|) + u * bSigma
= s * u * aSigma * (|X| - |B|) + u * bSigma
= s * u * aSigma * |A| + u * bSigma
= u * aSigma + u * bSigma
= u * (aSigma + bSigma)
= u * (xSigma)
= xSigma / |X|
= m_X

Доказательство завершено.

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

Известный онлайновый алгоритм для вычисления среднего значения является лишь частным случаем этого. Это алгоритм, который, если m является средним значением {x_1, x_2, ... , x_n}, тогда среднее значение {x_1, x_2, ..., x_n, x_(n+1)} будет m + ((x_(n+1) - m)) / (n + 1). Таким образом, X = {x_1, x_2, ..., x_(n+1)}, A = {x_(n+1)} и B = {x_1, x_2, ..., x_n} восстанавливают онлайн-алгоритм.

Answer 4

Нестандартное мышление: Вместо этого используйте медиану. Это гораздо проще вычислить - существует множество алгоритмов (например, с использованием очередей), вы часто можете составить хорошие аргументы относительно того, почему он более значим для наборов данных (менее подвержен влиянию экстремальных значений и т. Д.), И у вас не будет проблем численная точность. Это будет быстро и эффективно. Кроме того, для больших наборов данных (которые звучат так, как у вас), если распределения не являются действительно странными, значения для среднего и медианы будут одинаковыми.

Answer 5

Вот другой подход. Вы «получаете» числа один за другим из какого-то источника, но вы можете отслеживать среднее значение на каждом шаге.

Сначала я выпишу формулу для среднего на шаге n+1:

mean[n+1] = mean[n] - (mean[n] - x[n+1]) / (n+1)

с начальным условием:

mean[0] = x[0]

(индекс начинается с нуля).

Первое уравнение можно упростить до:

mean[n+1] = n * mean[n] / (n+1) + x[n+1]/(n+1)

Идея состоит в том, что вы отслеживаете среднее значение, и когда вы «получаете» следующее значение в вашей последовательности, вы вычисляете его смещение относительно текущего среднего и делите его поровну между n+1 выборками, которые были замечены до сих пор. и скорректируйте свое среднее значение соответственно. Если у ваших чисел нет большой разницы, ваше среднее значение нужно будет немного откорректировать с помощью новых чисел, когда n станет большим.

Очевидно, что этот метод работает, даже если вы не знаете общее количество значений при запуске. У него есть дополнительное преимущество: вы всегда знаете значение текущего среднего значения. Единственный недостаток, о котором я могу подумать, это то, что он, вероятно, придает больший «вес» числам, видимым в начале (не в строгом математическом смысле, а из-за представлений с плавающей запятой).

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

В качестве теста я сгенерировал N=100000 нормально распределенных случайных чисел со средним нулем и дисперсией 1. Затем я рассчитал их среднее значение тремя методами.

1. сумма (цифры) / N, назовите это m ₁ ,
2. мой метод выше, назовите его m ₂ ,
3. отсортируйте числа, а затем используйте мой метод выше, назовите его m ₃ .

Вот что я нашел: m ₁ & minus; м ₂ & сим; минус 4,6 раза; 10 ^{минус 17} , м ₁ минус; м ₃ & сим; "минус 3", "10 ^{", "минус 15 * 1053", м ₂ , "минус"; м ₃ & сим; & Минус; 3 & раза; 10 & минус; 15 * 1 059 *. Таким образом, если ваши номера отсортированы, ошибка может быть недостаточно мала для вас. (Однако обратите внимание, что даже наихудшая ошибка составляет 10 & минус; 15 частей в 1 для 100000 номеров, так что в любом случае она может быть достаточно хорошей.)}

Answer 6

Некоторые из математических решений здесь очень хороши. Вот простое техническое решение.

Используйте больший тип данных. Это разбивается на две возможности:

1. Использование высокоточной библиотеки с плавающей запятой. У того, кто сталкивается с необходимостью усреднить миллиард чисел, вероятно, есть ресурсы для покупки или умственные способности для написания 128-битной (или более длинной) библиотеки с плавающей запятой.

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

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

class BigMeanSet{
    List<uint> list = new List<uint>();

    public double GetAverage(IEnumerable<uint> values){
        list.Clear();
        list.Add(0);

        uint count = 0;

        foreach(uint value in values){
            Add(0, value);
            count++;
        }

        return DivideBy(count);
    }

    void Add(int listIndex, uint value){
        if((list[listIndex] += value) < value){ // then overflow has ocurred
            if(list.Count == listIndex + 1)
                list.Add(0);
            Add(listIndex + 1, 1);
        }
    }

    double DivideBy(uint count){
        const double shift = 4.0 * 1024 * 1024 * 1024;

        double rtn       = 0;
        long   remainder = 0;

        for(int i = list.Count - 1; i >= 0; i--){
            rtn *= shift;
            remainder <<= 32;
            rtn += Math.DivRem(remainder + list[i], count, out remainder);
        }

        rtn += remainder / (double)count;

        return rtn;
    }
}

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

Это должно обеспечить такую ​​точность, которую может представлять double, и должно работать для любого количества 32-битных элементов, вплоть до 2 ³² - 1. Если требуется больше элементов, тогда count переменная должна быть расширена, а функция DivideBy усложнится, но я оставлю это в качестве упражнения для читателя.

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

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

---

Я сейчас протестировал этот код и внес несколько небольших исправлений (отсутствующая пара скобок в вызове конструктора List<uint> и неверный делитель в конечном делении функции DivideBy).

Я проверил его, сначала пропустив 1000 наборов случайной длины (в диапазоне от 1 до 1000), заполненных случайными целыми числами (в диапазоне от 0 до 2 ³² - 1). Это были наборы, для которых я мог легко и быстро проверить точность, запустив на них каноническое среднее.

Затем я проверил с большими сериями 100 ^*, со случайной длиной от 10 ⁵ до 10 ⁹ . Нижняя и верхняя границы этих рядов также выбирались случайным образом, ограничиваясь так, чтобы ряды подходили к диапазону 32-разрядного целого числа. Для любой серии результаты легко проверяются как (lowerbound + upperbound) / 2.

_{^{* Хорошо, это маленькая белая ложь. Я прервал тест большой серии примерно после 20 или 30 успешных прогонов. Серия длиной 10 9 занимает чуть меньше полутора минут, чтобы запустить на моей машине, так что примерно полчаса тестирования этой процедуры было достаточно для моих вкусов.}}

Для тех, кто заинтересован, мой тестовый код ниже:

static IEnumerable<uint> GetSeries(uint lowerbound, uint upperbound){
    for(uint i = lowerbound; i <= upperbound; i++)
        yield return i;
}

static void Test(){
    Console.BufferHeight = 1200;
    Random rnd = new Random();

    for(int i = 0; i < 1000; i++){
        uint[] numbers = new uint[rnd.Next(1, 1000)];
        for(int j = 0; j < numbers.Length; j++)
            numbers[j] = (uint)rnd.Next();

        double sum = 0;
        foreach(uint n in numbers)
            sum += n;

        double avg = sum / numbers.Length;
        double ans = new BigMeanSet().GetAverage(numbers);

        Console.WriteLine("{0}: {1} - {2} = {3}", numbers.Length, avg, ans, avg - ans);

        if(avg != ans)
            Debugger.Break();
    }

    for(int i = 0; i < 100; i++){
        uint length     = (uint)rnd.Next(100000, 1000000001);
        uint lowerbound = (uint)rnd.Next(int.MaxValue - (int)length);
        uint upperbound = lowerbound + length;

        double avg = ((double)lowerbound + upperbound) / 2;
        double ans = new BigMeanSet().GetAverage(GetSeries(lowerbound, upperbound));

        Console.WriteLine("{0}: {1} - {2} = {3}", length, avg, ans, avg - ans);

        if(avg != ans)
            Debugger.Break();
    }
}

Answer 7

Average of x_1 .. x_N
    = (Sum(i=1,N,x_i)) / N
    = (Sum(i=1,M,x_i) + Sum(i=M+1,N,x_i)) / N
    = (Sum(i=1,M,x_i)) / N + (Sum(i=M+1,N,x_i)) / N

Это может применяться многократно, и это верно независимо от того, имеют ли суммы одинаковый размер. Итак:

• Продолжайте добавлять термины, пока оба:
• • добавление еще одного переполнит (или иначе потеряет точность)
• • деление на N не приведет к снижению
• Разделите сумму на N
• Добавьте результат к среднему на данный момент

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

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

10^100, 1, -10^100

Математика говорит, что это 1, но арифметика с плавающей точкой говорит, что это зависит от того, в каком порядке вы сложите термины, и в 4 из 6 возможных вариантов это 0, потому что (10 ^ 100) + 1 = 10 ^ 100. Но я думаю, что некоммутативность арифметики с плавающей точкой - это другая и более общая проблема, чем этот вопрос. Если об сортировке входных данных не может быть и речи, я думаю, есть вещи, которые вы можете сделать, когда вы поддерживаете множество аккумуляторов разной величины и добавляете каждое новое значение к тому, какой из них даст наилучшую точность. Но я действительно не знаю.

Answer 8

Когда вы разделяете числа на наборы, вы просто делите их на общее число или я что-то упустил?

Вы написали это как

/ 1   2   3 \   / 4   5   6 \
| - + - + - | + | - + - + - |
\ 3   3   3 /   \ 3   3   3 /
 ----------      -----------
      2               2

но это просто

/ 1   2   3 \   / 4   5   6 \
| - + - + - | + | - + - + - |
\ 6   6   6 /   \ 6   6   6 /

, поэтому для чисел от 1 до 7 одна из возможных группировок - просто

/ 1   2   3 \   / 4   5   6 \   / 7 \
| - + - + - | + | - + - + - | + | - |
\ 7   7   7 /   \ 7   7   7 /   \ 7 /