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

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

Пример:

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 (скользящее среднее).

Мой вопрос:

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

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


arrays average algorithm
person Thanasis Ioannidis    schedule 05.03.2012    source источник
comment
вы можете вычислить квадрат расстояния (норма l2) за один проход, но я не знаю эквивалента для абсолютной разницы (l1).   -  person andrew cooke    schedule 05.03.2012
comment
ну, для той цели, которую я хочу, может быть, квадрат расстояния делает работу за меня. Это для графического языка HLSL. В результате получается что-то вроде фильтра шумоподавления. Так что пока шум минимизирован, у меня будет работать :) Спасибо, посмотрю!   -  person Thanasis Ioannidis    schedule 22.03.2012
comment
хорошо, см. Формулу ниже. Надеюсь, поможет.   -  person andrew cooke    schedule 22.03.2012

Ответы (4)


arrow_upward
2
arrow_downward

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

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

D = ((xср.-x1) + (xср.-x2) + (x< sub>ave-x3) + ... + (xave-xk) + (x k+1-xср.) + (xk+2-xср.) + ... + (x< sub>n-xave))/n

= (-x1) + (-x2) + (-x3) + ... + (-x k) + (xk+1) + (xk+2) + ... + (xn) + (n-2k)xср.)/n

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

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

person Beta    schedule 05.03.2012
comment
Впервые этот вопрос возник у меня, когда я играл с кодом HLSL (код шейдера для графики, например, DirectX). В этой ситуации массив фактически является текстурой в памяти. На самом деле это область NxN вокруг конкретного пикселя с элементами N^2, которые сначала считываются для расчета средней яркости, а затем пересчитываются для вычисления среднего расстояния яркости каждого пикселя до ранее рассчитанного среднего значения. Следовательно, массив (область NxN пикселей) нельзя сортировать или каким-либо образом манипулировать им до тех пор, пока я не получу его в коде шейдера. - person Thanasis Ioannidis; 22.03.2012
comment
Я хотел найти способ свести к минимуму поиск текстур (чтение значений пикселей из текстуры), поскольку эта операция значительно снижает производительность. Если у меня ядро ​​5x5, я делаю поиск в текстуре 2*5*5 раз для каждого пикселя. Если у меня есть входная текстура 1024*768 пикселей, то у меня есть в общей сложности 39 321 600 считываний текстуры на кадр. Это слишком много. Я подумал, что вдвое сократить эту сумму было бы действительно здорово, поэтому я начал думать, есть ли способ вычислить то, что я хотел, за один раз, прочитав входные значения один раз. - person Thanasis Ioannidis; 22.03.2012

arrow_upward
1
arrow_downward

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

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

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

person mcdowella    schedule 05.03.2012
comment
Вопрос может быть более конкретным, чем необходимо. То, что я на самом деле искал в первую очередь, - это способ получить значение, которое говорит мне, насколько разбросаны (отдельно) элементы массива, путем считывания значений массива один раз. Поскольку это находится в графическом коде HLSL, значения находятся в диапазоне [0...255], поэтому я ожидаю значения от 0 до 255 (крайние случаи). Я думаю, что это не будет значение больше 128. например, для значений [3,5,3,5] значение будет равно 1 (среднее расстояние от среднего массива равно 1). для [2,6,2,6] значение будет равно 2 (среднее расстояние от среднего равно 2, хотя в обоих случаях среднее равно 4) - person Thanasis Ioannidis; 22.03.2012
comment
Вы можете легко рассчитать дисперсию за один проход. Квадратный корень из этого, стандартное отклонение, имеет много общего с вашим средним абсолютным отклонением. Есть несколько способов сделать это. Тот, что находится по адресу en.wikipedia.org/wiki/, был настроен так, чтобы хорошая числовая точность. - person mcdowella; 22.03.2012

arrow_upward
1
arrow_downward

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

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

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

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

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

person andrew cooke    schedule 21.03.2012

arrow_upward
0
arrow_downward

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

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

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

person Steve Demlow    schedule 13.08.2012