Более глубокое понимание циклов (for, while, do while, foreach, рекурсия и т. Д.)

Question

Если представить какую-либо ситуацию, вы можете выполнить цикл определенного события или функции, которую необходимо решить с помощью циклов, где вы можете добиться этого с помощью любого вида цикла.Как мы можем определить разницу между каждым циклом, который можно использовать, исходя из их скорости, эффективности и использования памяти?Как, например, у вас есть эти циклы

for(int i=0;i<10;i++) {
    array[i] = i+1;
}

int i = 0;
while(i<10) {
    array[i] = i+1;
    i++;
}

Приведенный выше пример имеет одинаковый вывод, конечно, вы не можете увидеть разницу между ними при выполнении, так как это всего лишь небольшой процесс, что если вы обрабатываетеогромный цикл, который съедает вашу память?Какой цикл лучше использовать?Есть ли правильная мера, когда использовать какой цикл?

Редактировать:

для pakore ответа,

Из вашего ответа я могу с уверенностью сказать, что если я переставлю свои переменные там, где большинствоиз переменных, которые являются зависимыми далеко друг от друга (с другими линиями между ними), может быть более эффективным.Скажем, например,

a=0;
b=1;
c=5;
d=1;
for(int i=0; i<10;i++)
{
    a=b*CalculateAge()+d;
    m=c+GetAvarage(a);
    d++;
}

и

a=0;
b=1;
c=5;
d=1;
for(int i=0; i<10;i++)
{
    a=b*CalculateAge()+d;
    d++;
    m=c+GetAvarage(a);
}

Последнее более эффективно, чем первое, так как позднее я вызвал внешний метод в первой и второй строке.не зависит от результата первой строки, чем в третьей строке.

Поскольку первый пример будет ожидать результата первой строки перед выполнением второй строки и третьей, а второй пример ужевыполнил вторую строку в ожидании результата первой строки.

Вывод:

Оптимизированный цикл не имеет значения, какой тип цикла вы используете.Как объяснил Пакоре и полигеномасляные смазки, главное, что вы можете возразить в своем цикле, это то, как ваш код написан внутри.Это задача компилятора оптимизировать ваш код, это также помогает, если вы оптимизируете свой код в соответствии с его зависимостью от каждой переменной, как поясняется ниже.

Answer 1

Что ж, здесь трудно объяснить всю логику, лежащую в основе цикла.

Компилятор сделает удивительные вещи для вас, чтобы оптимизировать циклы, поэтому не имеет значения, используете ли вы while илиfor потому что компилятор все равно будет переводиться на ассемблер.

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

Чтобы улучшить конвейеризацию, лучше размещать операторы с одинаковыми переменными вдали друг от друга.Таким образом, пока вычисляется один оператор, процессор может взять следующий оператор, если он не зависит от первого, и начать его вычисление.

Например:

a=0;
b=3;
c=5;
m=8;
i=0;
while(i<10){
a=a+b*c;
b=b*10+a;
m=m*5;
i++;
}

У нас есть зависимостьздесь между a и b, а утверждения находятся рядом друг с другом.Но мы видим, что m и i не зависят от остальных, поэтому мы можем сделать:

a=0;
b=3;
c=5;
m=8;
i=0;
while(i<10){
a=a+b*c;
m=m*5;
i++;
b=b*10+a;

}

Итак, пока вычисляется a, мы можем начать вычислять m и i.В большинстве случаев компилятор обнаруживает это и делает это автоматически (это переупорядочение кода вызова).Иногда для небольших циклов компилятор копирует и вставляет код внутри цикла столько раз, сколько это необходимо, потому что быстрее не иметь управляющих переменных.

Я предлагаю, чтобы компилятор позаботился об этих вещах исосредоточиться на затратах на алгоритмы, которые вы используете, лучше сократить с O (n!) до O (logn) , чем проводить микрооптимизацию внутри циклов.

Обновление в соответствии с измененным вопросом

Что ж, зависимости должны быть зависимостями записи / записи или чтения / записи.Если это зависимость чтения / чтения, то здесь нет проблем (потому что значение не меняется).Взгляните на [Data Dependency article] (http://en.wikipedia.org/wiki/Data_dependency).

В вашем примере нет разницы между двумя кодами, m зависит от c и b, но эти дваникогда не пишутся, поэтому компилятор знает их значение до попадания в цикл. Это называется зависимостью чтения / чтения, и это не сама зависимость.

Если вы написали:

...
m=c+GetAvarage(a);
...

Тогда у нас будет зависимость записи / чтения (мы должны записать в a, а затем прочитать из a, поэтому мы должны ждать, пока не будет вычислено a), и оптимизация, которую вы сделали, будет хорошей.

Но еще раз, компилятор делает это для вас и многих других вещей. Трудно сказать, что микрооптимизация в коде высокого уровня окажет реальное влияние на код ассемблера, потому чтовозможно, компилятор делает это уже для вас, или, может быть, переупорядочивает код для вас, или, может быть, делает тысячу других вещей лучше, чем мы можем представить на первый взгляд.

Но в любом случаеу, это хорошо, просто знать, как все работает под ковром:)

Обновление, чтобы добавить некоторые ссылки Посмотрите на эти ссылки, чтобы лучше понять, что компилятор может сделать дляулучшить производительность вашего кода:

Разматывание петли

Анализ зависимостей

Автоматическое распараллеливание

Векторизация

Answer 2

Я объясню каждый случай цикла один за другим,

1. Для цикла: Если вы уверены, что выполняете определенный нет итераций, переходите к для цикла.

2. Цикл while: Если вы не уверены ни в одном из итераций, переходите к циклу while или хотите проходить до тех пор, пока условие не станет ложным.

3. do-while : Это то же самое, что и цикл while, за исключением того, что цикл выполняется как минимум один раз.

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

4. Рекурсия : Если вы правильно понимаете рекурсию, рекурсия приводит к элегантным решениям. рекурсия немного медленнее, чем прямая итерация.

Нет различий в производительности между for, while, do-while. Если таковые имеются, они незначительны.

Answer 3

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

Современные компиляторы для большинства основных языков действительно умны в оптимизации вашего кода и могут особенно нацеливаться именно на те виды хорошо читаемых кодов, которые должны писать люди. Чем сложнее ваш код, тем труднее его понять людям и тем сложнее оптимизировать компиляторы.

Большинство компиляторов могут оптимизировать хвостовую рекурсию , что позволяет вам рекурсивно выражать свой алгоритм (что является наиболее естественной формой в некоторых сценариях), но, по сути, выполнять его итеративно. В противном случае рекурсия может быть медленнее, чем итеративное решение, но вы должны учесть все факторы, прежде чем выполнять эту оптимизацию.

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

Не оптимизировать преждевременно.

Answer 4

Любой приличный компилятор сгенерирует тот же код .

Для проверки я создал файл с именем loops-f.c:

void f(int array[])
{
    for(int i=0; i<10; i++) {
        array[i] = i+1;
    }
}

и файл с именем loops-g.c:

void g(int array[])
{
    int i = 0;
    while(i<10) {
        array[i] = i+1;
        i++;
    }
}

Я скомпилировал файлы в сборку (gcc -std=c99 -S loops-f.c loops-g.c), а затем сравнил сгенерированный код сборки (diff -u loops-f.s loops-g.s):

--- loops-f.s   2010-08-06 10:57:11.377196516 +0300
+++ loops-g.s   2010-08-06 10:57:11.389197986 +0300
@@ -1,8 +1,8 @@
-   .file   "loops-f.c"
+   .file   "loops-g.c"
    .text
-.globl f
-   .type   f, @function
-f:
+.globl g
+   .type   g, @function
+g:
 .LFB0:
    .cfi_startproc
    pushq   %rbp
@@ -30,6 +30,6 @@
    ret
    .cfi_endproc
 .LFE0:
-   .size   f, .-f
+   .size   g, .-g
    .ident  "GCC: (GNU) 4.4.4 20100630 (Red Hat 4.4.4-10)"
    .section    .note.GNU-stack,"",@progbits

Как видите, код практически идентичен.

Answer 5

В книге «Компьютерная организация и проектирование: аппаратно-программный интерфейс» авторов Паттерсона и Хеннесси преобразование указанных выше циклов в сборку, и оба цикла имеют одинаковый код сборки в MIPS.

Различия возникают, если ваш компилятор компилирует оба цикла в разных инструкциях сборки, если они не имеют одинаковую производительность.

Answer 6

Это, безусловно, будет зависеть от языка, который вы используете, но помните, что самой медленной частью любого кода является человек, кодирующий его, поэтому я бы предложил выбрать стандарт для каждой ситуации и придерживаться его, а затем, когда вы придете к обновлению код, который вам не нужно каждый раз думать об этом.

Если вы пытаетесь сэкономить такими способами, то вы либо уже работаете с почти 100% эффективностью, либо, возможно, ищете не то место, чтобы ускорить ваш код?

Answer 7

Это просто вопрос личных предпочтений и стиля кодирования - предпочтительный стиль также во многом зависит от языка, на котором вы кодируете.

Например, в python предпочтительный способ выполнения вышеуказанного цикла выглядит немногокак:

for i in range(0, 9):
    array[i] = i + 1

(На самом деле в Python вы можете сделать вышеупомянутое в одной строке:

array = range(1,10)

Но это только пример ...)

Из двух приведенных выше я бы предпочел первый.

Что касается производительности, вы вряд ли увидите разницу.

Answer 8

названия самих циклов дают представление об использовании.

Когда вам просто нужно выполнить операцию, не задавая вопросов, цикл for работает хорошо.

Если вы перебираете структуру данных и у вас есть ограничение, например, условие разрыва или что-то в этом роде, следует выбрать цикл while или do while.