Wyłamywanie się z zagnieżdżonej pętli

Jeśli mam pętlę for, która jest zagnieżdżona w innej, jak mogę efektywnie wyjść z obu pętli (wewnętrznej i zewnętrznej) w najszybszy możliwy sposób?

Nie chcę używać wartości logicznej, a następnie powiedzieć, że przejdź do innej metody, ale po prostu wykonuję pierwszy wiersz kodu po zewnętrznej pętli.

Jak szybko i przyjemnie to zrobić?

Myślałem, że wyjątki nie są tanie / powinny być wprowadzane tylko w naprawdę wyjątkowych warunkach itp. Dlatego nie sądzę, aby to rozwiązanie było dobre z punktu widzenia wydajności.

Nie sądzę, że warto korzystać z nowszych funkcji .NET (metody anonowe), aby robić coś, co jest dość fundamentalne.

Ale gototo brzydkie i nie zawsze możliwe. Możesz również umieścić pętle w metodzie (lub metodzie anonowej) i użyć, returnaby wyjść z powrotem do głównego kodu.

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

vs:

// 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");

Zauważ, że w C # 7 powinniśmy uzyskać „funkcje lokalne”, co (składnia tbd itp.) Oznacza, że ​​powinno działać coś takiego:

// 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");

Dostosowanie C # podejścia często używanego w C - ustawianie wartości zmiennej zewnętrznej pętli poza warunkami pętli (tj. Dla pętli używającej zmiennej int INT_MAX -1często jest dobrym wyborem):

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    
}

Jak zauważono w kodzie, breakmagicznie nie przeskoczy do następnej iteracji zewnętrznej pętli - więc jeśli masz kod poza wewnętrzną pętlą, to podejście wymaga więcej kontroli. W takim przypadku rozważ inne rozwiązania.

To podejście działa z pętlami fori whilenie działa foreach. W przeciwnym razie foreachnie będziesz mieć dostępu do kodu do ukrytego modułu wyliczającego, więc nie możesz go zmienić (a nawet jeśli nie możesz IEnumeratormieć metody „MoveToEnd”).

_{Podziękowania dla autorów komentarza:
i = INT_MAX - 1sugestia Meta
for / foreachkomentarz ygoe .
Właściwa IntMaxprzez jmbpiano
uwagą o kodzie po wewnętrznej pętlę blizpasta}

To rozwiązanie nie dotyczy C #

Dla osób, które znalazły to pytanie w innych językach, JavaScript, Java i D zezwalają na przerwy w pracy i kontynuuje :

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

Użyj odpowiedniej osłony w zewnętrznej pętli. Ustaw osłonę w wewnętrznej pętli przed zerwaniem.

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
    }
}

Lub jeszcze lepiej: wyodrębnij wewnętrzną pętlę do metody i wyjdź z zewnętrznej pętli, gdy zwróci fałsz.

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

    .... some outer loop stuff

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

    ... more outer loop stuff
}

Nie cytuj mnie, ale możesz użyć goto zgodnie z sugestią w MSDN. Istnieją inne rozwiązania, takie jak flaga sprawdzana w każdej iteracji obu pętli. Wreszcie możesz użyć wyjątku jako naprawdę ciężkiego rozwiązania swojego problemu.

IŚĆ DO:

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

Stan: schorzenie:

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
   }
}

Wyjątek:

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 ) {}

Czy jest możliwe przefakturowanie zagnieżdżonej pętli for na metodę prywatną? W ten sposób możesz po prostu „wrócić” z metody, aby wyjść z pętli.

Wydaje mi się, że ludzie bardzo nie lubią takich gotostwierdzeń, więc poczułem potrzebę nieco tego wyjaśnienia.

Wierzę, że „emocje”, które ludzie w gotokońcu sprowadzają się do zrozumienia kodu i (nieporozumień) na temat możliwych implikacji wydajnościowych. Zanim odpowiem na pytanie, najpierw przejdę do kilku szczegółów na temat jego kompilacji.

Jak wszyscy wiemy, C # jest kompilowany do IL, który jest następnie kompilowany do asemblera za pomocą kompilatora SSA. Dam trochę wglądu, jak to wszystko działa, a następnie spróbuję odpowiedzieć na pytanie.

Od C # do IL

Najpierw potrzebujemy fragmentu kodu C #. Zacznijmy od prostych:

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

Zrobię to krok po kroku, aby dać ci dobry obraz tego, co dzieje się pod maską.

Pierwsze tłumaczenie: od foreachdo równoważnej forpętli (Uwaga: używam tutaj tablicy, ponieważ nie chcę wchodzić w szczegóły IDisposable - w takim przypadku musiałbym również użyć IEnumerable):

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

Drugie tłumaczenie: fori breakjest tłumaczone na łatwiejszy odpowiednik:

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

Tłumaczenie i trzeci (jest to odpowiednik kodu IL): możemy zmienić breaki whiledo gałęzi:

    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; 

Kompilator wykonuje te czynności w jednym kroku, ale daje wgląd w proces. Kod IL, który ewoluuje z programu C #, jest dosłownym tłumaczeniem ostatniego kodu C #. Możesz zobaczyć tutaj: https://dotnetfiddle.net/QaiLRz (kliknij „zobacz IL”)

Jedną z rzeczy, które zauważyłeś tutaj, jest to, że podczas procesu kod staje się bardziej złożony. Najłatwiejszym sposobem na zaobserwowanie tego jest fakt, że potrzebowaliśmy coraz więcej kodu, aby stwierdzić to samo. Możesz także o to argumentowaćforeach , for, whilei breaksą rzeczywiście krótkie Ręce za goto, co jest częściowo prawdą.

Od IL do asemblera

Kompilator .NET JIT to kompilator SSA. Nie będę tutaj wchodził w wszystkie szczegóły formularza SSA i jak stworzyć optymalizujący kompilator, to po prostu za dużo, ale może dać podstawowe zrozumienie tego, co się stanie. Dla głębszego zrozumienia najlepiej zacząć czytać o optymalizacji kompilatorów (lubię tę książkę za krótkie wprowadzenie: http://ssabook.gforge.inria.fr/latest/book.pdf ) i LLVM (llvm.org) .

Każdy kompilator optymalizacyjny opiera się na fakcie, że kod jest łatwy i ma przewidywalne wzorce . W przypadku pętli FOR korzystamy z teorii grafów do analizy gałęzi, a następnie optymalizujemy takie rzeczy, jak cykle w naszych gałęziach (np. Gałęzie do tyłu).

Jednak teraz mamy gałęzie przekazujące do implementacji naszych pętli. Jak można się domyślić, jest to rzeczywiście jeden z pierwszych kroków, które JIT zamierza naprawić, w następujący sposób:

    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:
    // ...

Jak widać, mamy teraz odgałęzienie, które jest naszą małą pętlą. Jedyną rzeczą, która wciąż jest tutaj nieprzyjemna, jest gałąź, z którą skończymy z powodu naszejbreak oświadczenie. W niektórych przypadkach możemy to przenieść w ten sam sposób, ale w innych pozostanie.

Dlaczego więc kompilator to robi? Cóż, jeśli uda nam się rozwinąć pętlę, możemy ją wektoryzować. Możemy nawet być w stanie udowodnić, że dodawane są tylko stałe, co oznacza, że ​​cała nasza pętla może zniknąć w powietrzu. Podsumowując: czyniąc wzorce przewidywalnymi (powodując, że gałęzie są przewidywalne), możemy udowodnić, że pewne warunki utrzymują się w naszej pętli, co oznacza, że ​​możemy wykonywać magię podczas optymalizacji JIT.

Jednak gałęzie mają tendencję do przełamywania tych miłych, przewidywalnych wzorców, co jest czymś optymalizującym, a więc niechęcią. Przerwij, kontynuuj, goto - wszyscy zamierzają przełamać te przewidywalne wzorce - i dlatego nie są tak naprawdę „mili”.

Powinieneś również zdać sobie sprawę z tego, że proste foreachjest bardziej przewidywalne niż kilka gotostwierdzeń, które są wszędzie. Pod względem (1) czytelności i (2) z perspektywy optymalizatora jest to zarówno lepsze rozwiązanie.

Inną rzeczą wartą wspomnienia jest to, że jest to bardzo istotne dla optymalizacji kompilatorów do przypisywania rejestrów do zmiennych (proces zwany alokacją rejestrów ). Jak zapewne wiesz, w twoim CPU jest tylko skończona liczba rejestrów i są one zdecydowanie najszybszymi elementami pamięci w twoim sprzęcie. Zmienne używane w kodzie, który znajduje się w najbardziej wewnętrznej pętli, częściej przypisują rejestr, podczas gdy zmienne poza twoją pętlą są mniej ważne (ponieważ ten kod prawdopodobnie jest mniej trafiony).

Pomoc, zbyt duża złożoność ... co powinienem zrobić?

Najważniejsze jest to, że zawsze powinieneś używać konstrukcji językowych, które masz do dyspozycji, które zwykle (domyślnie) budują przewidywalne wzorce dla twojego kompilatora. Staraj się unikać dziwnych oddziałów, jeśli to możliwe (konkretnie: break, continue, gotolub returnw środku niczego).

Dobrą wiadomością jest to, że te przewidywalne wzorce są łatwe do odczytania (dla ludzi) i łatwe do wykrycia (dla kompilatorów).

Jeden z tych wzorów nosi nazwę SESE, co oznacza Single Entry Single Exit.

A teraz dochodzimy do prawdziwego pytania.

Wyobraź sobie, że masz coś takiego:

// a is a variable.

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

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

Najłatwiejszym sposobem uczynienia z tego przewidywalnego wzoru jest po prostu ifcałkowite wyeliminowanie :

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

W innych przypadkach można również podzielić metodę na 2 metody:

// 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;
}

Zmienne tymczasowe? Dobry, zły czy brzydki?

Możesz nawet zdecydować o zwróceniu wartości logicznej z pętli (ale ja osobiście wolę formularz SESE, ponieważ tak właśnie kompilator to zobaczy i myślę, że jest łatwiejszy do odczytania).

Niektórzy uważają, że łatwiej jest użyć zmiennej tymczasowej i proponują takie rozwiązanie:

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.
  // ...
}
// ...

Ja osobiście jestem przeciwny takiemu podejściu. Spójrz jeszcze raz, jak skompilowany jest kod. Teraz zastanów się, co to zrobi z tymi ładnymi, przewidywalnymi wzorami. Zrób zdjęcie?

Racja, pozwól mi to przeliterować. Stanie się tak, że:

• Kompilator wypisze wszystko jako gałęzie.
• W ramach etapu optymalizacji kompilator przeprowadzi analizę przepływu danych, próbując usunąć dziwną morezmienną, która jest używana tylko w przepływie kontrolnym.
• Jeśli się powiedzie, zmienna morezostanie usunięta z programu i pozostaną tylko gałęzie. Te gałęzie zostaną zoptymalizowane, więc z wewnętrznej pętli wydostaniesz się tylko jedna gałąź.
• Jeśli się nie powiedzie, zmienna morejest zdecydowanie używana w wewnętrznej pętli, więc jeśli kompilator jej nie zoptymalizuje, ma dużą szansę na przypisanie do rejestru (który zużywa cenną pamięć rejestru).

Podsumowując: optymalizator w twoim kompilatorze sprawi wiele kłopotów, aby dowiedzieć się, że morejest używany tylko do przepływu sterowania, aw najlepszym przypadku scenariusz przetłumaczy go na jedną gałąź poza zewnętrzną dla pętla.

Innymi słowy, najlepszym scenariuszem jest to, że zakończy się odpowiednikiem tego:

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:

// ...

Moja osobista opinia na ten temat jest dość prosta: jeśli tak właśnie zamierzaliśmy, uczyńmy świat łatwiejszym zarówno dla kompilatora, jak i czytelności, i napiszmy to od razu.

tl; dr:

Dolna linia:

• Jeśli to możliwe, użyj prostego warunku w pętli for. Trzymaj się konstrukcji języka wysokiego poziomu, które masz do dyspozycji w jak największym stopniu.
• Jeśli wszystko zawiedzie, a ty zostaniesz z jednym gotolub bool more, wybierz ten pierwszy.

dodaj do funkcji / metody i użyj wczesnego powrotu lub przestaw pętle w klauzulę while. goto / wyjątki / cokolwiek z pewnością nie jest tutaj odpowiednie.

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

Poprosiłeś o kombinację szybkiego, przyjemnego, bez użycia wartości logicznej, bez użycia goto i C #. Wykluczyłeś wszystkie możliwe sposoby robienia tego, co chcesz.

Najszybszym i najmniej brzydkim sposobem jest użycie goto.

Czasami miło jest wyodrębnić kod do jego własnej funkcji i niż użyć wczesnego powrotu - wczesne powroty są złe:)

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;
            }
        }
    }
}

Widziałem wiele przykładów, które używają słowa „przerwa”, ale żaden nie używa słowa „kontynuuj”.

Nadal wymagałoby to jakiejś flagi w wewnętrznej pętli:

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
    ...

}

Odkąd po raz pierwszy widziałem breakw C kilka dekad temu, ten problem mnie denerwuje. Miałem nadzieję, że jakieś ulepszenie języka będzie miało rozszerzenie break, które zadziała w ten sposób:

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.

Pamiętam z czasów studenckich, że powiedziano, że matematycznie można udowodnić, że możesz zrobić wszystko w kodzie bez goto (tzn. Nie ma sytuacji, w której goto jest jedyną odpowiedzią). Tak więc, nigdy nie używam goto (tylko moje osobiste preferencje, nie sugerując, że mam rację czy źle)

W każdym razie, aby wydostać się z zagnieżdżonych pętli, robię coś takiego:

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;
}

... mam nadzieję, że tym, którzy mnie lubią, są anty-goto „fanboys” :)

Tak to zrobiłem. Nadal obejście.

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;
  }
}

Najłatwiejszym sposobem zakończenia podwójnej pętli byłoby bezpośrednie zakończenie pierwszej pętli

string TestStr = "The frog jumped over the hill";
char[] KillChar = {'w', 'l'};

for(int i = 0; i < TestStr.Length; i++)
{
    for(int E = 0; E < KillChar.Length; E++)
    {
        if(KillChar[E] == TestStr[i])
        {
            i = TestStr.Length; //Ends First Loop
            break; //Ends Second Loop
        }
    }
}

Pętle mogą być przerywane przy użyciu niestandardowych warunków w pętli, co pozwala uzyskać czysty kod.

    static void Main(string[] args)
    {
        bool isBreak = false;
        for (int i = 0; ConditionLoop(isBreak, i, 500); i++)
        {
            Console.WriteLine($"External loop iteration {i}");
            for (int j = 0; ConditionLoop(isBreak, j, 500); j++)
            {
                Console.WriteLine($"Inner loop iteration {j}");

                // This code is only to produce the break.
                if (j > 3)
                {
                    isBreak = true;
                }                  
            }

            Console.WriteLine("The code after the inner loop will be executed when breaks");
        }

        Console.ReadKey();
    }

    private static bool ConditionLoop(bool isBreak, int i, int maxIterations) => i < maxIterations && !isBreak;   

Za pomocą tego kodu uzyskujemy następujące dane wyjściowe:

• Iteracja pętli zewnętrznej 0
• Iteracja pętli wewnętrznej 0
• Iteracja pętli wewnętrznej 1
• Iteracja pętli wewnętrznej 2
• Iteracja pętli wewnętrznej 3
• Iteracja pętli wewnętrznej 4
• Kod po wewnętrznej pętli zostanie wykonany po zerwaniu

Inną opcją jest anonimowa funkcja . Bez goto, bez etykiety, bez nowej zmiennej, bez nowej nazwy funkcji i jeden wiersz krótszy niż przykład metody anonimowej u góry.

// self-invoked-anonymous-function
new Action(() =>
{
    for (int x = 0; x < 100; x++)
    {
        for (int y = 0; y < 100; y++)
        {
            return; // exits self invoked lambda expression
        }
    }
})();
Console.WriteLine("Hi");

Rzuć niestandardowy wyjątek, który wychodzi poza pętlę zewnętrzną.

Działa dla for, foreachlub whiledowolnego rodzaju pętli i dowolnego języka, który używa try catch exceptionbloku

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
            }
        }

Widzę, że zaakceptowałeś odpowiedź, w której osoba odsyła twoje stwierdzenie goto, podczas gdy we współczesnym programowaniu i w opinii eksperta goto jest zabójcą, nazwaliśmy go zabójcą w programowaniu, które mają pewne powody, o których nie będę tutaj omawiać w tym momencie, ale rozwiązanie twojego pytania jest bardzo proste, możesz użyć flagi boolowskiej w tego rodzaju scenariuszu, tak jak pokażę to w moim przykładzie:

            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;
               }

proste i jasne. :)

Czy w ogóle spojrzałeś na breaksłowo kluczowe? Oo

To tylko pseudo-kod, ale powinieneś zobaczyć, co mam na myśli:

<?php
for(...) {
    while(...) {
        foreach(...) {
            break 3;
        }
    }
}

Jeśli myślisz o breakbyciu funkcją jakbreak() , to jego parametrem byłaby liczba pętli, z których można zerwać. Ponieważ znajdujemy się w trzeciej pętli kodu tutaj, możemy wyrwać się ze wszystkich trzech.

Podręcznik: http://php.net/break

Myślę, że chyba, że ​​chcesz zrobić „boolowską rzecz”, jedynym rozwiązaniem jest rzucenie. Czego oczywiście nie powinieneś robić ...!