Эффективный способ расчета среднего различия элементов массива от среднего значения массива

Question

Есть ли способ рассчитать среднее расстояние элементов массива от среднего значения массива, просто «посетив» каждый элемент массива один раз? (Я ищу алгоритм)

Пример:

Array : [ 1 , 5 , 4 , 9 , 6 ]
Average : ( 1 + 5 + 4 + 9 + 6 ) / 5 = 5
Distance Array : [|1-5|, |5-5|, |4-5|, |9-5|, |6-5|] = [4 , 0 , 1 , 4 , 1 ]
Average Distance : ( 4 + 0 + 1 + 4 + 1 ) / 5 = 2

Простому алгоритму нужно 2 прохода.

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

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

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

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

Формула:

Compute Running Average of Array's elements
-------------------------------------------
RA[i] = E[i] {for i == 1}
RA[i] = RA[i-1] - RA[i-1]/i + A[i]/i { for i > 1 }

Где A [x] - элемент массива в позиции x, RA [x] - среднее значение элементов массива между позицией 1 и x (скользящее среднее).

Мой вопрос:

Существует ли аналогичный алгоритм для вычисления "на лету" (когда мы читаем элементы массива) среднего расстояния элементов от среднего значения массива?

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

Answer 1

Я не думаю, что вы можете сделать лучше, чем O (n log n).

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

D = ((x _ave -x ₁ ) + (x _ave -x ₂ ) + (х _пр. -х ₃ ) + ... + (х _пр. -х _к ) + (х _{k + 1} -x _пр. ) + (x _{k + 2} -x _пр. ) + ... + (x _n -x _ave )) / n

= (-x ₁ ) + (-x ₂ ) + (-x ₃ ) + ... + (-x _k ) + (x _{k + 1} ) + (x _{k + 2} ) + ... + (x _n ) + (n-2k) x _ave ) / n

= ([сумма элементов выше среднего] -[сумма элементов ниже среднего] + (n-2k) x _ave ) / n

Вы можете рассчитать это за один проход, работая с обоих концов, регулируя ограничения на (пока что-неизвестно) средний, как вы идете. Это будет O (n), а сортировка - O (n logn) (и, возможно, они могут быть выполнены в одной и той же операции), так что все это O (n logn).

Answer 2

если норма l2 (среднее расстояние в квадрате) в порядке, то это:

sqrt(sum(x^2)/n - (sum(x)/n)^2)

это (квадратный корень из) среднего х ^ 2 минус квадрат среднего х.

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

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

Answer 3

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

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

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

Answer 4

Ваш ответ описал ваш контекст как чтение HLSL из текстуры. Если ваш след фильтра имеет степень двойки и выровнен с одинаковыми границами степени двух в исходном изображении, вы можете использовать карты MIP, чтобы найти среднее значение области фильтра.

Например, для фильтра 8x8 предварительно вычислите карту MIP на три уровня вниз по цепочке MIP, элементами которой будут средние значения для каждой области 8x8. Затем одна текстура, считанная из этой текстуры уровня MIP, даст вам среднее значение для региона 8x8. К сожалению, это не работает для скольжения фильтра к произвольным позициям (в данном примере это число не кратно 8).

Вы можете использовать промежуточные уровни MIP, чтобы уменьшить количество считываний текстур, используя средние значения MIP 4x4 или 2x2 областей, когда это возможно, но это значительно усложнит алгоритм.