用于计算 .NET 中数组平均值的算法的性能问题

本文关键字：算法 性能 问题 平均值 数组 计算 NET 用于 | 更新日期: 2023-09-27 18:31:29

以下代码创建一个平均包含 200,000 个数组的数组，每个数组包含 512 个元素。

void Main()
{
    double[] avg = new double[512];
    int start = System.Environment.TickCount;
    for (int i = 0; i < 200000; i++)
    {
        for (int j = 0; j < avg.Length; j++)
        {
            // The `i` in `i-avg[j]` is a dummy for the measured variable.
            avg[j] = avg[j] + (i - avg[j])/(i + 1);
        }
    }
    Console.WriteLine(System.Environment.TickCount-start);
}

迭代平均值的原因是避免在对 200,000 个数组的值求和时溢出。

在现实世界中，200,000 个数组是使用 FFTW 库在 250 毫秒内生成的 DFT。我有点惊讶，在我的系统上计算平均数组大约需要 500-600 毫秒（平均），即迭代和几次翻牌所需的时间是 FFT 的 2-3 倍。

有没有办法在 .NET 中使用不同（更快）的方式加快速度或实现相同的结果，或者我是否必须切换语言以提高速度？

用于计算 .NET 中数组平均值的算法的性能问题

通过将内部循环展开除数 512 来节省一点。我也不确定我是否理解 i 循环的用途，因为它表明 （i+1） 可以预先计算并替换为乘法。有没有办法在您的实际案例中应用相同的优化，或者您这样做只是为了提高计时的准确性？

        for (double i = 0; i < 200000; i++)
        {
            var inv_i_plus_1 = 1.0 / (i + 1);
            for (int j = 0; j < avg.Length; )
            {
                // The `i` in `i-avg[j]` is a dummy for the measured variable.
                avg[j] = avg[j] + (i - avg[j]) * inv_i_plus_1; j++;
                avg[j] = avg[j] + (i - avg[j]) * inv_i_plus_1; j++;
                avg[j] = avg[j] + (i - avg[j]) * inv_i_plus_1; j++;
                avg[j] = avg[j] + (i - avg[j]) * inv_i_plus_1; j++;
                avg[j] = avg[j] + (i - avg[j]) * inv_i_plus_1; j++;
                avg[j] = avg[j] + (i - avg[j]) * inv_i_plus_1; j++;
                avg[j] = avg[j] + (i - avg[j]) * inv_i_plus_1; j++;
                avg[j] = avg[j] + (i - avg[j]) * inv_i_plus_1; j++;
            }
        }

表达式

avg[j] + (i - avg[j]) / (i + 1)

简化后成为

(avg[j] + 1) * i / (i + 1)

如我们所见，i / (i + 1) 与 j 没有任何共同之处，因此我们可以在内部循环之外预先计算它

for (int i = 0; i < 200000; i++)
{
    double k = i;
    k = k / (k + 1);
    for (int j = 0; j < avg.Length; j++)
    {
        avg[j] = (avg[j] + 1) * k;
    }
}

最终代码比原始代码快约 4 到 6 倍。

主要原因一定是内部循环中的划分。

你可能会牺牲一点准确性，做一个直接的求和。双倍没有溢出的风险。

如果值按递增或递

减顺序（或接近该顺序）排序，则按递增顺序求和将保持良好的准确性。

只需将除法更改为倒数乘法，然后将倒数计算提升到循环之外：

void Main()
{
    double[] avg = new double[512];
    int start = System.Environment.TickCount;
    for (int i = 0; i < 200000; i++)
    {
        double di = (double)i;
        double r = 1/(di + 1);
        for (int j = 0; j < avg.Length; j++)
        {
            // The `i` in `i-avg[j]` is a dummy for the measured variable.
            avg[j] = avg[j] + (di - avg[j]) * r;
        }
    }
    Console.WriteLine(System.Environment.TickCount-start);
}
相关文章：