有没有一种方法可以根据数组平均值计算数组元素的平均距离，只需"访问"每个数组元素一次？（我搜索算法）
示例：
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
简单的算法需要两次通过。
第一次通过）读取并累加值，然后将结果除以数组长度以计算数组元素的平均值。
第二次）读取值，累积每个元素与先前计算的平均值的距离，然后将结果除以数组长度，以从数组的平均值中找到元素的平均距离。
这两道菜完全一样。它是计算一组值的平均值的经典算法。第一个输入数组的元素，第二个输入每个元素与数组平均值的距离。
计算平均值可以修改为不累加值，而是在我们依次从数组中读取元素时"动态"计算平均值。
公式为：
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之间的数组元素的平均值（运行平均值）。
我的问题是：
是否有类似的算法来计算"动态"（当我们读取数组元素时），即元素与数组平均值的平均距离？
问题是，当我们读取数组的元素时，数组的最终平均值是未知的。只有运行平均数是已知的。因此，计算与运行平均值的差值不会得到正确的结果。我想，如果存在这样的算法，它可能应该具有"能力"，在某种程度上，在读取每个新元素时补偿迄今为止计算出的误差。
我不认为你能做得比O（n log n）更好。
假设数组已排序。然后我们可以把它分为小于平均值的元素和大于平均值的因素。（如果有些元素等于平均值，那没关系。）假设前k个元素小于平均值。则平均距离为
D=（（xave-x1）+（xave-xk）+（xn-xave））/n
=（-x1）+（-x2（-xk）+（xk+1（xn）+（n-2k）xave）/n
=（[高于平均值的元素之和]-[低于平均值的元件之和]+（n-2k）xave）/n
你可以通过从两端进行计算，在计算过程中调整（目前未知的）平均值的限制来一次性计算出这一点 这将是O（n），排序是O（n-logn）（它们可能在同一个操作中完成），所以整个事情是O（nlogn）
两遍方法的唯一问题是，您需要重读或存储第二遍的整个序列。明显的改进是维护数据结构，以便在平均值发生变化时调整绝对差之和。
假设您通过观察一个巨大的数字，将平均值更改为一个非常大的值。现在将由此产生的变化与观察到的不太大的值所引起的变化进行比较。你将能够计算出两个绝对差之和之间的差，因为两个平均值都高于所有其他数字，所以所有的绝对值都会随着两个巨大平均值之间的差而减小。这种可预测的变化一直持续到平均值达到标准数字中观察到的最高值，这种变化可以让你找出观察到的最大数字是什么。
通过进行这样的实验，你可以恢复在你输入数字进行实验之前观察到的一组数字。因此，任何用于跟踪绝对差之和的聪明数据结构都能够存储观察到的一组数字，这（除了顺序和观察到同一数字的多个副本的情况外）几乎就是你通过存储第二次看到的所有数字所做的。所以我不认为绝对差和的情况有什么技巧，就像差平方的情况一样，你关心的大多数信息都是用一对数字来描述的（和，平方和）。
如果l2范数（平均距离平方）是可以的，那么它是：
sqrt(sum(x^2)/n - (sum(x)/n)^2)
这是（的平方根）平均值x^2减去平均值x的平方。
它被称为方差（实际上，上面是方差的平方根，称为标准差，是典型的"扩散度量"）。
请注意，这比您最初要求的度量对异常值更敏感。
您的跟进将您的上下文描述为HLSL从纹理中读取。如果您的过滤器足迹是二次方，并且与原始图像中相同的二次方边界对齐，则可以使用MIP映射来查找过滤器区域的平均值。
例如，对于8x8滤波器，预计算MIP链下三级的MIP映射，其元素将是每个8x8区域的平均值。然后，从MIP级别纹理读取的单个纹理将为您提供8x8区域的平均值。不幸的是，这不适用于将过滤器滑动到任意位置（在本例中不是8的倍数）。
只要可能，您可以使用中间MIP级别，通过使用4x4或2x2区域的MIP平均值来减少纹理读取的数量，但这会使算法变得相当复杂。