c - 如何有效地将数组缩小到目标标准差

我有一个n值的C数组。我需要计算的是在数组的极值处有多少个值，一旦排序，需要去掉，以便剩余值的标准差小于某个数字。
我不能就这些价值观的分散方式或价值观做出任何假设。它们可以是正的，也可以是负的。
我已经编写了下面的代码，但它是一个大锤，需要永远运行，因为这个函数每秒调用1000次以上，并且
阵列的长度可以在100到12000之间。
有更好的解决办法吗？

double standardDeviation(double values[], int length)
{
    double sdAverage = average(values, length);
    double stDev = 0;
    for (int i = 0; i < length; ++i)
        stDev += pow((values[i] - sdAverage), 2);

    return( sqrt(stDev/length) );
}

int countItemsThatFit(double values[], int length, int sDevTarget)
{
    qsort(values, length, sizeof (double), compareDoubles);
    int headIndex = 0, tailIndex  = length - 1;

    double sDev        = standardDeviation(values, length);
    int valuesRemaining = length;

    while (sDev > sDevTarget && valuesRemaining > 0)
    {
        // try removing head and tail (separately) to find which sDev is smaller
        double headStrippedDev = standardDeviation(&values[headIndex + 1], valuesRemaining);
        double tailStrippedDev = standardDeviation(&values[headIndex    ], valuesRemaining - 1);

        if (headStrippedDev <= tailStrippedDev)
            ++headIndex;
        --valuesRemaining;
    }
    return (valuesRemaining);
}

最佳答案

不要从数组中删除值并重新计算标准偏差，而是设想一个空数组，向它添加值并使用updating formula计算标准偏差。
这样做的诀窍是按顺序添加值，这样在添加值时标准偏差不会减小。这可以通过添加最接近原始数组平均值的值来实现。换句话说，与平均值的绝对偏差最小的值。
所以，应该有效的算法是：
计算数组的平均值
按与平均值的绝对偏差比较项的排序数组
设置N=2
计算前两个元素的标准差
当标准差设置N=N+1
从数组中获取下一项
使用更新公式重新计算附加值的标准偏差
如果数组仍然有元素返回N
否则返回N-1
下面是一个演示算法的示例：

Source Array: [10, 14, 16, 18, 20, 22, 24]
Target SD: 2.5

Step 1) Mean = 17.0
Step 2) [16, 18, 14, 20, 22, 10, 24]
Step 4) SD([16,18]) = 1.4142
Step 5.2) SD([16,18,14]) = 2
Step 5.2) SD([16,18,14,20]) = 2.5820

Return 3

关于c - 如何有效地将数组缩小到目标标准差，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22259744/