Выход из вложенного цикла
-
11-07-2019 - |
Вопрос
Если у меня есть цикл for, вложенный в другой, как я могу максимально быстро выйти из обоих циклов (внутреннего и внешнего)?
Я не хочу использовать логическое значение, а затем говорить «перейти к другому методу», а просто выполнить первую строку кода после внешнего цикла.
Как это можно сделать быстро и красиво?
Спасибо
Я думал, что исключения недешевы и их следует создавать только в действительно исключительных условиях и т. д.Поэтому я не думаю, что это решение будет хорошим с точки зрения производительности.
Я не считаю правильным использовать новые возможности .NET (анонимные методы) для выполнения чего-то фундаментального.
По этой причине у tvon (извините, я не могу написать полное имя пользователя!) есть хорошее решение.
Марк:Хорошее использование анонимных методов, и это тоже здорово, но поскольку я могу работать, где мы не используем версию .NET/C#, поддерживающую анонимные методы, мне также нужно знать традиционный подход.
Решение
Хорошо, goto
, но это некрасиво и не всегда возможно.Вы также можете поместить циклы в метод (или анонимный метод) и использовать 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 мы должны получить «локальные функции», что (синтаксис будет уточнен и т. д.) означает, что они должны работать примерно так:
// 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");
Другие советы
C# адаптация подхода, часто используемого в C - установка значения переменной внешнего цикла вне условий цикла (т.е.цикл for с использованием переменной 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
прокомментировать угоэ.
Правильный IntMax
к jmbпиано
замечание о коде после внутреннего цикла близпаста
Это решение не применимо к C#.
Для людей, которые нашли этот вопрос на других языках: Javascript, Java и D позволяют помечать перерывы и продолжения.:
outer: while(fn1())
{
while(fn2())
{
if(fn3()) continue outer;
if(fn4()) break outer;
}
}
Используйте подходящее ограждение во внешнем контуре.Прежде чем сломаться, установите защиту во внутреннем цикле.
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
}
Не цитируйте меня по этому поводу, но вы могли бы использовать идти к как предложено в MSDN.Существуют и другие решения, например включение флага, который проверяется на каждой итерации обоих циклов.Наконец, вы можете использовать исключение как действительно тяжелое решение вашей проблемы.
ИДТИ К:
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 ) {}
Можно ли реорганизовать вложенный цикл for в частный метод?Таким образом, вы можете просто «вернуться» из метода, чтобы выйти из цикла.
Мне кажется, что люди не любят 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 к ассемблеру
JIT-компилятор .NET является компилятором SSA.Я не буду здесь вдаваться во все детали формы SSA и того, как создать оптимизирующий компилятор, это слишком много, но может дать общее представление о том, что произойдет.Для более глубокого понимания лучше начать читать об оптимизации компиляторов (мне нравится эта книга для краткого введения: http://ssabook.gforge.inria.fr/latest/book.pdf ) и LLVM (llvm.org).
Каждый оптимизирующий компилятор опирается на тот факт, что код легкий и следует предсказуемые закономерности.В случае циклов FOR мы используем теорию графов для анализа ветвей, а затем оптимизируем такие вещи, как циклы в наших ветвях (например,ветви в обратном направлении).
Однако теперь у нас есть прямые ветки для реализации наших циклов.Как вы могли догадаться, на самом деле это один из первых шагов, которые собирается исправить 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-оптимизации.
Однако ветки имеют тенденцию нарушать эти хорошие предсказуемые шаблоны, что оптимизаторам не нравится.Break, continue, goto — все они направлены на разрушение этих предсказуемых шаблонов — и поэтому не совсем «приятны».
На этом этапе вы также должны понимать, что простой 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
, предпочитаю первое.
учтите функцию/метод и используйте ранний возврат или перестройте циклы в предложение while.goto/Exceptions/whatever здесь явно не уместен.
def do_until_equal():
foreach a:
foreach b:
if a==b: return
Вы просили сочетание быстрого, красивого, без использования логических значений, без использования goto и C#.Вы исключили все возможные способы сделать то, что хотите.
Самый быстрый и наименее неприятный способ — использовать goto.
Иногда приятно абстрагировать код в отдельную функцию и затем использовать ранний возврат - хотя ранние возвраты - это зло:)
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;
}
}
}
}
В зависимости от вашей ситуации вы можете это сделать, но только если вы не выполняете код ПОСЛЕ внутреннего цикла.
for (int i = 0; i < 100; i++)
{
for (int j = 0; j < 100; j++)
{
i = 100;
break;
}
}
Это не элегантно, но может быть самым простым решением в зависимости от вашей проблемы.
Я видел много примеров, в которых используется «перерыв», но ни в одном не используется «продолжить».
Во внутреннем цикле все равно потребуется какой-то флаг:
while( some_condition )
{
// outer loop stuff
...
bool get_out = false;
for(...)
{
// inner loop stuff
...
get_out = true;
break;
}
if( get_out )
{
some_condition=false;
continue;
}
// more out loop stuff
...
}
С тех пор, как я впервые увидел break
в C пару десятилетий назад эта проблема меня беспокоила.Я надеялся, что некоторые улучшения языка будут иметь расширение для прерывания, которое будет работать следующим образом:
break; // our trusty friend, breaks out of current looping construct.
break 2; // breaks out of the current and it's parent looping construct.
break 3; // breaks out of 3 looping constructs.
break all; // totally decimates any looping constructs in force.
Я помню, еще со студенческих времен говорили, что математически доказуемо, что в коде можно делать что угодно без перехода (т.не существует ситуации, когда goto является единственным ответом).Итак, я никогда не использую goto (только мои личные предпочтения, не предполагающие, что я прав или нет)
В любом случае, чтобы выйти из вложенных циклов, я делаю что-то вроде этого:
var isDone = false;
for (var x in collectionX) {
for (var y in collectionY) {
for (var z in collectionZ) {
if (conditionMet) {
// some code
isDone = true;
}
if (isDone)
break;
}
if (isDone)
break;
}
if (isDone)
break;
}
...надеюсь, это поможет тем, кто, как и я, является "фанатами" против гото :)
Вот как я это сделал.Все еще обходной путь.
foreach (var substring in substrings) {
//To be used to break from 1st loop.
int breaker=1;
foreach (char c in substring) {
if (char.IsLetter(c)) {
Console.WriteLine(line.IndexOf(c));
\\setting condition to break from 1st loop.
breaker=9;
break;
}
}
if (breaker==9) {
break;
}
}
Вызовите собственное исключение, которое выходит за внешний цикл.
Это работает для for
,foreach
или while
или любой тип цикла и любой язык, который использует try catch exception
блокировать
try
{
foreach (object o in list)
{
foreach (object another in otherList)
{
// ... some stuff here
if (condition)
{
throw new CustomExcpetion();
}
}
}
}
catch (CustomException)
{
// log
}
bool breakInnerLoop=false
for(int i=0;i<=10;i++)
{
for(int J=0;i<=10;i++)
{
if(i<=j)
{
breakInnerLoop=true;
break;
}
}
if(breakInnerLoop)
{
continue
}
}
Как я вижу, вы приняли ответ, в котором человек отсылает вас к оператору goto, где в современном программировании и по мнению экспертов goto является убийцей, мы назвали его убийцей в программировании, у которого есть определенные причины, которые я не буду обсуждать здесь. на данный момент, но решение вашего вопроса очень просто: вы можете использовать логический флаг в таком сценарии, как я продемонстрирую это в своем примере:
for (; j < 10; j++)
{
//solution
bool breakme = false;
for (int k = 1; k < 10; k++)
{
//place the condition where you want to stop it
if ()
{
breakme = true;
break;
}
}
if(breakme)
break;
}
простой и понятный.:)
Вы хотя бы посмотрели на break
ключевое слово?оо
Это всего лишь псевдокод, но вы поймете, что я имею в виду:
<?php
for(...) {
while(...) {
foreach(...) {
break 3;
}
}
}
Если вы думаете о break
будучи функцией типа break()
, то его параметром будет количество циклов, из которых необходимо выйти.Поскольку мы находимся в третьем цикле кода, мы можем выйти из всех трех.
Руководство: http://php.net/break
Я думаю, что если вы не хотите делать «логические вещи», единственное решение — это бросить.Чего, очевидно, делать не следует..!