Выход из вложенной петли

Question

Если у меня есть цикл for, который вложен в другой, как я могу эффективно выйти из обоих циклов (внутреннего и внешнего) как можно быстрее?

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

Какой быстрый и приятный способ сделать это?

Спасибо

---

Я думал, что исключения недешевы / должны создаваться только в действительно исключительном состоянии и т. Д. Поэтому я не думаю, что это решение было бы хорошим с точки зрения производительности.

Я не считаю правильным использовать новые возможности в .NET (anon-методы) для выполнения чего-то, что является довольно фундаментальным.

Из-за этого, у tvon (извините, не пишется полное имя пользователя!) Есть хорошее решение.

Марк: Хорошее использование методов anon, и это тоже замечательно, но, поскольку я могу работать, когда мы не используем версию .NET / C #, которая поддерживает методы anon, мне нужно знать и традиционный подход .

Answer 1

Ну, goto, но это некрасиво и не всегда возможно. Вы также можете поместить циклы в метод (или anon-метод) и использовать return для возврата к основному коду.

    // goto
    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            goto Foo; // yeuck!
        }
    }
Foo:
    Console.WriteLine("Hi");

против

// anon-method
Action work = delegate
{
    for (int x = 0; x < 100; x++)
    {
        for (int y = 0; y < 100; y++)
        {
            return; // exits anon-method
        }
    }
};
work(); // execute anon-method
Console.WriteLine("Hi");

---

Обратите внимание, что в C # 7 мы должны получить "локальные функции", что (синтаксис tbd и т. Д.) Означает, что оно должно работать примерно так:

// local function (declared **inside** another method)
void Work()
{
    for (int x = 0; x < 100; x++)
    {
        for (int y = 0; y < 100; y++)
        {
            return; // exits local function
        }
    }
};
Work(); // execute local function
Console.WriteLine("Hi");

Answer 2

C # адаптация подхода, часто используемого в C - установить значение переменной внешнего цикла вне условий цикла (т. Е. Для цикла с использованием переменной int INT_MAX -1 часто является хорошим выбором):

for (int i = 0; i < 100; i++)
{
    for (int j = 0; j < 100; j++)
    {
        if (exit_condition)
        {
            // cause the outer loop to break:
            // use i = INT_MAX - 1; otherwise i++ == INT_MIN < 100 and loop will continue 
            i = int.MaxValue - 1;
            Console.WriteLine("Hi");
            // break the inner loop
            break;
        }
    }
    // if you have code in outer loop it will execute after break from inner loop    
}

Как отмечается в коде, break не будет магическим образом переходить к следующей итерации внешнего цикла - поэтому, если у вас есть код вне внутреннего цикла, этот подход требует больше проверок. Рассмотрим другие решения в этом случае.

Этот подход работает с for и while циклами, но не работает для foreach. В случае foreach у вас не будет доступа к коду для скрытого перечислителя, поэтому вы не сможете его изменить (и даже если бы вы могли IEnumerator не иметь какого-либо метода MoveToEnd).

_{Благодарность авторам встроенных комментариев:
i = INT_MAX - 1 предложение Мета
for / foreach комментарий от ygoe .
Правильно IntMax jmbpiano
Замечание о коде после внутреннего цикла blizpasta}

Answer 3

Это решение не относится к C #

Для людей, которые нашли этот вопрос на других языках, Javascript, Java и D допускают помеченные разрывы и продолжение :

outer: while(fn1())
{
   while(fn2())
   {
     if(fn3()) continue outer;
     if(fn4()) break outer;
   }
}

Answer 4

Используйте подходящий защитный кожух во внешней петле. Установите предохранитель во внутреннюю петлю, прежде чем сломать.

bool exitedInner = false;

for (int i = 0; i < N && !exitedInner; ++i) {

    .... some outer loop stuff

    for (int j = 0; j < M; ++j) {

        if (sometest) {
            exitedInner = true;
            break;
        }
    }
    if (!exitedInner) {
       ... more outer loop stuff
    }
}

Или, что еще лучше, абстрагируйте внутренний цикл в метод и выйдите из внешнего цикла, когда он вернет false.

for (int i = 0; i < N; ++i) {

    .... some outer loop stuff

    if (!doInner(i, N, M)) {
       break;
    }

    ... more outer loop stuff
}

Answer 5

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

GOTO:

for ( int i = 0; i < 10; ++i ) {
   for ( int j = 0; j < 10; ++j ) {
      // code
      if ( break_condition ) goto End;
      // more code
   }
}
End: ;

Условие:

bool exit = false;
for ( int i = 0; i < 10 && !exit; ++i ) {
   for ( int j = 0; j < 10 && !exit; ++j ) {
      // code
      if ( break_condition ) {
         exit = true;
         break; // or continue
      }
      // more code
   }
}

Исключение:

try {
    for ( int i = 0; i < 10 && !exit; ++i ) {
       for ( int j = 0; j < 10 && !exit; ++j ) {
          // code
          if ( break_condition ) {
             throw new Exception()
          }
          // more code
       }
    }
catch ( Exception e ) {}

Answer 6

Можно ли реорганизовать вложенный цикл for в закрытый метод? Таким образом, вы можете просто «вернуться» из метода, чтобы выйти из цикла.

Answer 7

Мне кажется, что людям очень не нравится высказывание goto, поэтому я почувствовал необходимость немного исправить это.

Я полагаю, что "эмоции" у людей примерно goto в конечном итоге сводятся к пониманию кода и (неправильных представлений) о возможных последствиях для производительности. Прежде чем ответить на вопрос, я сначала расскажу о некоторых деталях его компиляции.

Как все мы знаем, C # компилируется в IL, который затем компилируется в ассемблер с использованием компилятора SSA. Я немного расскажу о том, как все это работает, а затем попытаюсь ответить на сам вопрос.

От C # до IL

Сначала нам нужен кусок кода C #. Давайте начнем с простого:

foreach (var item in array)
{
    // ... 
    break;
    // ...
}

Я сделаю это шаг за шагом, чтобы дать вам хорошее представление о том, что происходит под капотом.

Первый перевод: из foreach в эквивалентный цикл for (Примечание: я здесь использую массив, потому что я не хочу вдаваться в подробности IDisposable - в этом случае я бы также имел использовать IEnumerable):

for (int i=0; i<array.Length; ++i)
{
    var item = array[i];
    // ...
    break;
    // ...
}

Второй перевод: for и break переводится в более простой эквивалент:

int i=0;
while (i < array.Length)
{
    var item = array[i];
    // ...
    break;
    // ...
    ++i;
}

И третий перевод (это эквивалент кода IL): мы меняем break и while на ветку:

    int i=0; // for initialization

startLoop:
    if (i >= array.Length) // for condition
    {
        goto exitLoop;
    }
    var item = array[i];
    // ...
    goto exitLoop; // break
    // ...
    ++i;           // for post-expression
    goto startLoop; 

Хотя компилятор делает все это за один шаг, он дает вам представление о процессе. Код IL, полученный из программы на C #, является буквальным переводом последнего кода на C #. Вы можете увидеть здесь: https://dotnetfiddle.net/QaiLRz (нажмите «посмотреть IL»)

Теперь, одна вещь, которую вы здесь заметили, заключается в том, что во время процесса код становится более сложным. Самый простой способ убедиться в этом - это то, что нам требовалось все больше и больше кода для подтверждения того же самого. Вы также можете утверждать, что foreach, for, while и break на самом деле являются короткими руками для goto, что отчасти верно.

От IL до ассемблера

.NET JIT-компилятор является SSA-компилятором. Я не буду вдаваться во все подробности формы SSA и о том, как создать оптимизирующий компилятор, это слишком много, но может дать общее представление о том, что произойдет. Для более глубокого понимания лучше начать с чтения по оптимизации компиляторов (мне нравится эта книга для краткого введения: http://ssabook.gforge.inria.fr/latest/book.pdf) и LLVM (llvm.org).

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

Однако теперь у нас есть прямые ветви для реализации наших циклов. Как вы могли догадаться, это на самом деле один из первых шагов, которые JIT собирается исправить, например:

    int i=0; // for initialization

    if (i >= array.Length) // for condition
    {
        goto endOfLoop;
    }

startLoop:
    var item = array[i];
    // ...
    goto endOfLoop; // break
    // ...
    ++i;           // for post-expression

    if (i >= array.Length) // for condition
    {
        goto startLoop;
    }

endOfLoop:
    // ...

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

Так почему компилятор делает это? Что ж, если мы сможем развернуть цикл, мы сможем его векторизовать. Мы могли бы даже доказать, что добавляются только константы, что означает, что весь наш цикл может исчезнуть в воздухе. Подводя итог: сделав шаблоны предсказуемыми (делая предсказуемые ветви), мы можем доказать, что в нашем цикле выполняются определенные условия, что означает, что мы можем творить чудеса во время оптимизации JIT.

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

Вы должны также осознать, что простой foreach более предсказуем, чем набор goto утверждений, которые встречаются повсюду. С точки зрения (1) читабельности и (2) с точки зрения оптимизатора, это и лучшее решение.

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

Помогите, слишком много сложности ... что мне делать?

Суть в том, что вы всегда должны использовать языковые конструкции, которые есть в вашем распоряжении, которые обычно (неявно) создают предсказуемые шаблоны для вашего компилятора. Старайтесь избегать странных ветвей, если это возможно (в частности: break, continue, goto или return в середине ничего).

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

Один из этих шаблонов называется SESE, что означает однократный однократный выход.

А теперь перейдем к реальному вопросу.

Представьте, что у вас есть что-то вроде этого:

// a is a variable.

for (int i=0; i<100; ++i) 
{
  for (int j=0; j<100; ++j)
  {
     // ...

     if (i*j > a) 
     {
        // break everything
     }
  }
}

Самый простой способ сделать эту предсказуемую модель - это просто полностью исключить if:

int i, j;
for (i=0; i<100 && i*j <= a; ++i) 
{
  for (j=0; j<100 && i*j <= a; ++j)
  {
     // ...
  }
}

В других случаях вы также можете разделить метод на 2 метода:

// Outer loop in method 1:

for (i=0; i<100 && processInner(i); ++i) 
{
}

private bool processInner(int i)
{
  int j;
  for (j=0; j<100 && i*j <= a; ++j)
  {
     // ...
  }
  return i*j<=a;
}

Временные переменные? Хорошо, плохо или безобразно?

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

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

bool more = true;
for (int i=0; i<100; ++i) 
{
  for (int j=0; j<100; ++j) 
  {
     // ...
     if (i*j > a) { more = false; break; } // yuck.
     // ...
  }
  if (!more) { break; } // yuck.
  // ...
}
// ...

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

Хорошо, позвольте мне изложить это. Что произойдет, это:

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

Итак, подведем итоги: оптимизатор в вашем компиляторе постигнет кучу хлопот, чтобы выяснить, что more используется только для потока управления и в лучшем случае переведет его в одну ветку за пределами внешнего цикла for.

Другими словами, в лучшем случае это будет эквивалентно следующему:

for (int i=0; i<100; ++i) 
{
  for (int j=0; j<100; ++j)
  {
     // ...
     if (i*j > a) { goto exitLoop; } // perhaps add a comment
     // ...
  }
  // ...
}
exitLoop:

// ...

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

ТЛ; др:

Итог:

• Используйте простое условие в цикле for, если это возможно. Придерживайтесь языковых конструкций высокого уровня, которые есть в вашем распоряжении.
• Если все не получается и у вас остается либо goto, либо bool more, предпочтите первое.

Answer 8

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

def do_until_equal():
  foreach a:
    foreach b:
      if a==b: return

Answer 9

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

Самый быстрый и наименее уродливый способ - использовать goto.

Answer 10

Иногда приятно абстрагировать код в его собственную функцию, а затем использовать ранний возврат - хотя ранние возвраты - это зло

public void GetIndexOf(Transform transform, out int outX, out int outY)
{
    outX = -1;
    outY = -1;

    for (int x = 0; x < Columns.Length; x++)
    {
        var column = Columns[x];

        for (int y = 0; y < column.Transforms.Length; y++)
        {
            if(column.Transforms[y] == transform)
            {
                outX = x;
                outY = y;

                return;
            }
        }
    }
}