C # Динамическая итерация зубчатого массива

Question

Я заранее прошу прощения за длительность этого вопроса ... Это немного запутано.Я пишу операцию «взвешенная сумма», которая довольно проста;взять 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?

Большие взлеты

Немного больше информации

• Пиксельная карта входит в WriteableBitmap в Silverlight -который после построения принимает 1D массив в качестве источника пикселей (поскольку высота / ширина передается в конструктор)
• Каждое входное изображение имеет определенный множитель, например, умножает все пиксели входного 1 на 2, всепикселей ввода 2 на 3 и т. д.
• Никогда не будет более 20 входов.

Answer 1

Я рекомендую вам создать выражение, представляющее ваши вычисления.Затем вы компилируете это выражение.

Ваше выражение будет лямбда-выражением.Пример для трех входов:

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

Вот и все.Вам необходимо заполнить пробелы.

Answer 2

Существует три способа повысить производительность этого кода:

1. Переключение циклов t и i.Таким образом, вы работаете с теми же двумя большими массивами и можете применить элемент 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. The Секундомер класс идеально подходит для определения времени, особенно для очень коротких промежутков времени.

Answer 3

Вот еще один ответ: используйте шаблоны T4, чтобы генерировать все возможные функции для от 1 до 20 входных данных как время компиляции. Это не так круто, как мой предыдущий ответ, но также отлично работает.

Answer 4

Вы должны попробовать поменять местами внутренний и внешний цикл.

Ваша пиксельная карта, вероятно, поместится в кэш процессора, и тогда вам не нужно будет так много писать много раз.

Затем вы можете развернуть внутренний цикл, который повторяется по пикселям.для максимальной производительности.Обязательно протестируйте сборки выпуска за пределами отладчика, чтобы получить правильные временные характеристики.

Если вы все еще не удовлетворены, вы можете вычислять одну линию сканирования изображения за один раз.