C#动态交错数组迭代

本文关键字：数组 迭代 动态 | 更新日期: 2023-09-27 18:21:29

我提前为这个问题的长度道歉。。。这有点复杂。我正在写一个非常简单的"加权和"运算；取n个图像，将每个图像乘以特定的乘法器，并将它们相加为输出图像（通过迭代每个像素）。当图像数量不变时，我可以将逻辑硬编码为一次迭代，然而，我希望使该方法足够灵活，能够处理可变数量的图像。我无法想出一种同样"高效"的方法来实现这一点，例如，当输入数量未知时，如果没有额外的内部循环。以下是我的情况：

var rnd = new Random();
//Pixels in input and output images
const int x = 1000000;
//An output composite image
var pixelmap = new int[x];
var tStart = DateTime.Now;
//Known number of inputs
int knownNumberOfInputs = 3;
//Weights to apply to each pixel of the input images
//multipliers[0] applies to all pixels of inputA,
//multipliers[1] applies to all pixels of inputB etc.
var multipliers = new byte[3];
rnd.NextBytes(multipliers);
/* situation 1 
* - I know how many input images
* - Arrays are independent */
//3 (knownNumberOfInputs) input images (we'll use random numbers for filler)
var inputA = new byte[x];
rnd.NextBytes(inputA);
var inputB = new byte[x];
rnd.NextBytes(inputB);
var inputC = new byte[x];
rnd.NextBytes(inputC);
//I can iterate through each pixel of each input image, multiply and sum for pixelmap value.
//Without a nested loop
for (var i = 0; i < x; i++)
{
    pixelmap[i] = (
        (inputA[i]*multipliers[0]) +
        (inputB[i]*multipliers[1]) +
        (inputC[i]*multipliers[2])
                        );
}
Console.WriteLine("Operation took " + DateTime.Now.Subtract(tStart).TotalMilliseconds + " ms");
// Operation took 39 ms
tStart = DateTime.Now;
/* situation 2
* unknown number of inputs
* inputs are contained within jagged array */
/* Caveat - multipliers.Length == inputs.Length */
//var unknownNumberOfInputs = rnd.Next(1, 10);
var unknownNumberOfInputs = 3; //Just happens to be the same number (for performance comparisons)
multipliers = new byte[unknownNumberOfInputs];
rnd.NextBytes(multipliers);
//Jagged array to contain input images
var inputs = new byte[unknownNumberOfInputs][];
//Load unknownNumberOfInputs of input images into jagged array
for (var i = 0; i < unknownNumberOfInputs; i++)
{
    inputs[i] = new byte[x];
    rnd.NextBytes(inputs[i]);
}
// I cannot iterate through each pixel of each input image
// Inner nested loop
for (var i = 0; i < x; i++)
{
    for (var t=0;t<multipliers.Length;t++)
    {
        pixelmap[i] += (inputs[t][i] * multipliers[t]);
    }
}
Console.WriteLine("Operation took " + DateTime.Now.Subtract(tStart).TotalMilliseconds + " ms");
//Operation took 54 ms
//How can I get rid of the inner nested loop and gain the performance of LoopA?
//Or is that the cost of not knowing?

大型

更多信息

  • pixelmap将进入Silverlight中的WriteableBitmap，一旦构造好，就会将1D数组作为像素源（因为高度/宽度被传递到构造函数中）
  • 每个输入图像具有特定的乘法器，例如，将输入1的所有像素乘以2，将输入2的所有像素乘3等
  • 输入永远不会超过20个

C#动态交错数组迭代

有三种方法可以提高此代码的性能：

  1. 切换t和i回路。这样，您就可以使用相同的2个大数组，并且可以应用项2：
  2. 使用临时变量来消除内部循环中的数组访问
  3. 使用一种称为"循环展开"的技术：以3个为一组进行计算，直到剩下不到3个输入为止。然后再做一个循环

这一切看起来是这样的：

int t = 0;
for (; t < multipliers.Length - 2; t += 3) {
    var input1 = inputs[t];
    var input2 = inputs[t+1];
    var input3 = inputs[t+2];
    var multiplier1 = multipliers[t];
    var multiplier2 = multipliers[t+1];
    var multiplier3 = multipliers[t+2];
    if (t == 0) {
        for (var i = 0; i < x; i++)
            pixelmap[i] = input1[i] * multiplier1
                + input2[i] * multiplier2
                + input3[i] * multiplier3;
    } else {
        for (var i = 0; i < x; i++)
            pixelmap[i] += input1[i] * multiplier1
                + input2[i] * multiplier2
                + input3[i] * multiplier3;
    }
}
if (multipliers.Length < 3)
    Array.Clear(pixelmap, 0, pixelmap.Length);
for (; t < multipliers.Length; t++) {
    var input = inputs[t];
    var multiplier = multipliers[t];
    for (var i = 0; i < x; i++)
        pixelmap[i] += input[i] * multiplier;
}

我也会对你计时结果的方式做一些改变：

  1. 看起来您正在Visual Studio中运行基准测试，可能处于调试模式。请确保在Visual Studio之外的发布模式下运行基准测试
  2. 只对您感兴趣的代码进行基准测试。不要使用创建测试数据的代码
  3. 秒表类是计时的理想选择，尤其是在非常短的时间跨度内

我建议您创建一个表示计算的表达式。然后编译该表达式。

您的表达式将是lambda。三种输入的示例：

void (byte[] inputA, byte[] inputB, byte[] inputC) {
for (var i = 0; i < x; i++)
{
    pixelmap[i] = (
        (inputA[i]*multipliers0) +
        (inputB[i]*multipliers1) +
        (inputC[i]*multipliers1)
                        );
}
}

使用.NET 4，可以将for循环用作表达式（不在.NET 2中）。

这听起来很难，但实际上很容易做到。

澄清一下：您将在运行时编译一个专门用于常量输入的函数。

你甚至可以玩一些技巧，比如将循环展开2到4次。您也可以像示例中那样将乘数作为常量内联。这将比嵌套循环快得多。

请注意，循环在表达式树内部，而不是在它周围。这意味着您只有单个委托调用（以及可重用编译结果）的开销。

下面是一些让你开始的示例代码：

int inputCount = ...;
var paramExpressions = GenerateArray(inputCount, i => Expression.Parameter(typeof(byte[]), "input" + i);
var summands = GenerateArray(inputCount, i => Expression.Mul(/* inputA[i] HERE */, Expression.Constant(multipliers[i]));
var sum = summands.Aggregate((a,b) => Expression.Add(a,b));
var assignment = /* assign sum to pixelmap[i] here */;
var loop = /* build a loop. ask a new question to find out how to do this, or use google */
var lambda = Expression.Lambda(paramExpressions, loop);
var delegate = lambda.Compile();
//you are done compiling. now invoke:
delegate.DynamicInvoke(arrayOfInputs); //send an object of type byte[][] into the lambda

就是这样。你需要填补空白。

您应该尝试交换内部和外部循环。

您的pixelmap可能会放在Cpu缓存中，然后多次写入它就不必那么痛苦了。

然后，您可以展开在像素上迭代的内部循环，以获得最大性能。请确保在调试器之外测试发布版本，以获得正确的时间安排。

如果您仍然不满意，可以一次计算一条图像扫描线。

这里还有另一个答案：使用T4模板为1到20个输入生成所有可能的函数作为编译时。这不像我之前的回答那么酷，但也很好。

相关文章：