В C#, для циклов линеен?

Question

Здесь я использую математический термин для линейного. Если мы посмотрим, например, на определение усреднения, мы знаем, что:

Это то, что я имею в виду под линейным. Предположим, что в C# я хочу сделать следующее:

for (int i = 0; i<N; i++)
{
    someVar[i] += i;
    someOtherVar[i] += i;
}

Стоит ли это столько же накладных расходов, сколько:

for (int i = 0; i<N; i++)
{
    someVar[i] += i;
}
for (int i = 0; i<N; i++)
{
    someOtherVar[i] += i;
}

Изменится ли разница, если операция в для l oop более сложный, например:

for (int i = 0; i<N; i++)
{
    someOtherVar[i] *= Math.Cos(2.0 * Math.Pi * i / N);
}

Предположим, что N большое, 16384 записей.

Answer 1

Я выполнил дамп IL, и использование одного l oop быстрее, чем использование двух циклов, поскольку при увеличении «i» возникают накладные расходы. Тем не менее, разница будет минимальной.

Если вы имеете дело с гораздо большим набором данных и вам необходимо оптимизировать его дальше, изучите операции SIMD (одна инструкция, несколько данных).

https://habr.com/en/post/467689/

Answer 2

Что касается сложности , то и один, и два алгоритма l oop являются линейными O(n) операциями. Но что касается фактической производительности (накладные расходы), две версии l oop, скорее всего, медленнее. Компилятор или среда выполнения могут выбрать оптимизацию, но два цикла обычно переводят в:

set i to 0;

a:
if i < N goto done;
set someVar[i] = someVar[i] + i;
set i = i + 1
goto a;

done:
set i to 0;

b:
if i < N goto done;
set someOtherVar[i] = someOtherVar[i] + i;
set i = i + 1;
goto b;

... что явно больше шагов , чем один l oop.