c# - C# 動的ジャグ配列反復

Question

この質問が長くなってしまうことをお詫びします...少し複雑です。私は非常に単純な「加重合計」操作を書いています。n 個の画像を取得し、各画像に特定の乗数を掛けて、出力画像に合計します (各ピクセルを反復することにより)。画像の数が一定の場合、ロジックを 1 回の反復にハードコーディングできますが、可変数の画像を処理できるようにメソッドを柔軟にしたいと考えています。入力の数が不明な場合に追加の内部ループを使用しないなど、これを達成するための同等に「パフォーマンスの高い」方法を思いつくことはできません。これが私の状況です：

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?

ビッグアップ

もう少し情報

ピクセルマップは、Silverlight の WriteableBitmap に入ります。これは、構築されると、1D 配列をピクセルソースとして受け取ります (高さ/幅がコンストラクターに渡されるため)。
各入力画像には特定の乗数があります。たとえば、入力 1 のすべてのピクセルに 2 を掛けたり、入力 2 のすべてのピクセルに 3 を掛けたりします。
入力が 20 を超えることはありません。

score 1 · Accepted Answer

計算を表す式を作成することをお勧めします。次に、その式をコンパイルします。

あなたの式はラムダになります。3 つの入力の例:

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

それでおしまい。ギャップを埋める必要があります。

score 1 · Accepted Answer

このコードのパフォーマンスを改善するには、次の 3 つの方法があります。

tとiループを切り替えます。そうすれば、同じ 2 つの大きな配列で作業し、項目 2 を適用できます。
一時変数を使用して、内側のループでの配列アクセスを排除します。
「ループアンローリング」と呼ばれる手法を使用します。残りの入力が 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;
}

また、結果の時間を計る方法にいくつかの変更を加える必要があります。

おそらくデバッグモードで、Visual Studio 内からベンチマークを実行しているようです。Visual Studio の外部でリリースモードでベンチマークを実行してください。
関心のあるコードのみをベンチマークします。テストデータを作成するコードは除外します。
Stopwatchクラスは、タイミングの目的、特に非常に短い期間の場合に理想的です。

score 0 · Accepted Answer

内側のループと外側のループを入れ替えてみてください。

ピクセルマップはおそらくCPUキャッシュに収まるので、何度も書き込むのにそれほど害を及ぼす必要はありません。

次に、最大のパフォーマンスを得るために、ピクセルを反復処理する内側のループを展開できます。正しいタイミングを取得するには、デバッガーの外部でリリースビルドをテストしてください。

それでも満足できない場合は、一度に1つの画像スキャンラインを計算できます。

score 0 · Accepted Answer

別の答えは次のとおりです。T4 テンプレートを使用して、コンパイル時に 1 ～ 20 個の入力に対して可能なすべての関数を生成します。これは私の以前の回答ほどクールではありませんが、うまく機能します。

c# - C# 動的ジャグ配列反復

もう少し情報

4 に答える 4

Related

Reference