我需要最快的方法来处理数值数组数据的数学

Question

如果这是在不正确的论坛中，我深表歉意。尽管在此站点上找到了大量数组操作，但其中大多数都是求平均值/求和...使用 LINQ 将数字数组作为一个集合，它可以很好地处理数组中的所有值。但我需要处理多个数组（相同大小）上的每个索引。

\n

我的例程从设备接收数组数据，通常double[512]是 或ushort[512]；单个设备本身始终具有相同大小的数组数据，但数组大小的范围可以从 256 到 2048，具体取决于设备。我需要将CountToAverage数组的数量保持为平均值。每次接收到数组时，必须从队列中压入和弹出，以确保平均过程中数组的数量一致（这部分过程在Setup()本次基准测试中固定。为了比较，基准结果显示在代码后面。

\n

\n

1. 我正在寻找的是最快最有效的方法来平均所有数组的每个索引的值，并返回一个新数组（相同大小），其中每个索引是从数组集中平均的。要平均的数组数量范围为 3 到 25（下面的代码将基准参数设置为 10）。我在测试中使用了2种不同的平均方法，第二种明显更快，比第一种快6-7倍。我的第一个问题是；有没有什么方法可以更快地实现这一点，并且可以以 O(1) 或 O(log n) 的时间复杂度完成？

   \n
\n

2. 其次，我使用队列（可以更改为ConcurrentQueue实现）作为要处理的数组的持有者。我使用队列的主要原因是因为我可以保证对数组馈送进行 FIFO 处理，这一点至关重要。foreach另外，我可以通过循环（就像）处理队列中的值，List而无需出列直到准备好。如果有人知道这是否会阻碍性能，我会很感兴趣，因为我还没有对其进行基准测试。请记住它必须是线程安全的。如果您有其他方法以线程安全的方式处理多组数组数据，我会“洗耳恭听”。

   \n
\n

\n

性能要求的原因是这不是唯一正在发生的过程，我有多个设备正在以大约每 1-5 毫秒 1 次的速率“流式传输”数组结果，每个设备来自不同的线程/进程/connections，仍然有其他几个更密集的算法需要处理，所以这不会成为瓶颈。

\n

任何有关优化和性能的见解都将受到赞赏。

\n

using System;\nusing System.Collections.Generic;\nusing BenchmarkDotNet.Attributes;\nusing BenchmarkDotNet.Jobs;\nusing BenchmarkDotNet.Running;\nusing Microsoft.Diagnostics.Tracing.Parsers.MicrosoftAntimalwareEngine;\n\nnamespace ArrayAverage\n{\n    public class ArrayAverage\n    {\n        [Params(10)]\n        public int CountToAverage;\n\n        [Params(512, 2048)]\n        public int PixelSize;\n\n        static Queue<double[]> calcRepo = new Queue<double[]>();\n        static List<double[]> spectra = new();\n        \n        [Benchmark]\n        public double[] CalculateIndexAverages()\n        {\n            // This is too slow\n            var avg = new double[PixelSize];\n            for (int i = 0; i < PixelSize; i++)\n            {\n                foreach (var arrayData in calcRepo)\n                {\n                    avg[i] += arrayData[i];\n                }\n                avg[i] /= calcRepo.Count;\n            }\n            return avg;\n        }\n        \n        [Benchmark]\n        public double[] CalculateIndexAverages2()\n        {\n            // this is faster, but is it the fastest?\n            var sum = new double[PixelSize];\n            int cnt = calcRepo.Count;\n            foreach (var arrayData in calcRepo)\n            {\n                for (int i = 0; i < PixelSize; i++)\n                {\n                    sum[i] += arrayData[i];\n                }\n            }\n\n            var avg = new double[PixelSize];\n            for (int i = 0; i < PixelSize; i++)\n            {\n                avg[i] = sum[i] / cnt;\n            }\n\n            return avg;\n        }\n        \n        [GlobalSetup]\n        public void Setup()\n        {\n            // Just generating some data as simple Triangular curve simulating a range of spectra\n            for (double offset = 0; offset < CountToAverage; offset++)\n            {\n                var values = new double[PixelSize];\n                var decrement = 0;\n                for (int i = 0; i < PixelSize; i++)\n                {\n                    if (i > (PixelSize / 2))\n                        decrement--;\n                    values[i] = (offset / 7) + i + (decrement * 2);\n                }\n                calcRepo.Enqueue(values);\n            }\n        }        \n    }\n    \n    public class App\n    {\n        public static void Main()\n        {\n            BenchmarkRunner.Run<ArrayAverage>();\n        }\n    }\n}\n\n

\n

基准测试结果：

\n

\nBenchmarkDotNet=v0.13.1, OS=Windows 10.0.19043.1348 (21H1/May2021Update)\nIntel Core i7-6700HQ CPU 2.60GHz (Skylake), 1 CPU, 8 logical and 4 physical cores\n.NET SDK=6.0.100-preview.7.21379.14\n  [Host]     : .NET 5.0.12 (5.0.1221.52207), X64 RyuJIT  [AttachedDebugger]\n  DefaultJob : .NET 5.0.12 (5.0.1221.52207), X64 RyuJIT\n

\n

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n

方法	数组求平均值	数组大小	意思是	错误	标准差
计算指数平均值	10	第512章	32.164\xce\xbcs	0.5485 \xce\xbcs	0.5130 \xce\xbcs
计算指数平均值2	10	第512章	第5.792章	0.1135 \xce\xbcs	0.2241 \xce\xbcs
计算指数平均值	10	2048	123.628\xce\xbcs	2.3394 \xce\xbcs	1.9535 \xce\xbcs
计算指数平均值2	10	2048	22.311 \xce\xbcs	0.4366 \xce\xbcs	0.8093 \xce\xbcs

\n

Answer 1

当处理大量数据的简单操作时，您会对SIMD非常感兴趣：

\n

\n

SIMD 代表“单指令、多数据”。它\xe2\x80\x99 是一组处理器指令，...允许对一组值并行执行数学运算。

\n

\n

在您的特定情况下，使用Vector<T>示例将为您带来快速胜利。天真地将最快的方法转换为使用向量已经在我的电脑上提供了约 2 倍的速度。

\n

public double[] CalculateIndexAverages4() {\n    // Assumption: PixelSize is a round multiple of Vector<>.Count\n    // If not, you\'ll have to add in the \'remainder\' from the example.\n    var batch = Vector<double>.Count;\n    \n    var sum = new double[PixelSize];\n    foreach (var arrayData in calcRepo) {\n        // Vectorised summing:\n        for (int i = 0; i <= PixelSize - batch; i += batch) {\n            var vSum = new Vector<double>(sum, i);\n            var vData = new Vector<double>(arrayData, i);\n            (vSum + vData).CopyTo(sum, i);\n        }\n    }\n\n    var vCnt = Vector<double>.One * calcRepo.Count;\n    // Reuse sum[] for averaging, so we don\'t incur memory allocation cost\n    for (int i = 0; i <= PixelSize - batch; i += batch) {\n        var vSum = new Vector<double>(sum, i);\n        (vSum / vCnt).CopyTo(sum, i);\n    }\n    return sum;\n}\n

\n

它Vector<T>.Count告诉您有多少项被并行化为一条指令。就 而言double，它很可能位于支持AVX2 的4大多数现代 CPU 上。

\n

如果您可以接受损失精度并且可以转到，那么通过再次将单个 CPU 操作中处理的数据量加倍，float您将获得更大的胜利。所有这一切甚至无需更改您的算法。

\n