[C#] 중첩 루프에서 벗어나기

C# / 글쓴이

다른 루프에 중첩 된 for 루프가있는 경우 가능한 빨리 두 루프 (내부 및 외부)에서 효율적으로 나올 수있는 방법은 무엇입니까?

부울을 사용하고 싶지 않다가 다른 방법으로 가야한다고 말하고 외부 루프 후에 첫 번째 코드 줄을 실행해야합니다.

이것에 대해 빠르고 좋은 방법은 무엇입니까?

예외는 저렴하지 않고 진정으로 예외적 인 조건에서만 발생해야한다고 생각했습니다. 따라서이 솔루션이 성능 측면에서 좋을 것이라고 생각하지 않습니다.

.NET의 새로운 기능 (비정형 방법)을 사용하여 매우 근본적인 것을 수행하는 것이 옳다고 생각하지 않습니다.

답변

글쎄, goto그러나 그것은 추악하고 항상 가능한 것은 아닙니다. 루프를 메소드 (또는 anon-method)에 배치하고 return메인 코드로 돌아가는 데 사용할 수도 있습니다.

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

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

답변

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”방법이 없습니다).

인라인 주석 작성자에 대한 감사의 글 :
Meta의
i = INT_MAX - 1 제안 / ygoe의 의견 .
적절한 으로 jmbpiano 에 의해 내부 루프 후 코드에 대한 발언 blizpasta

forforeach
IntMax


답변

이 솔루션은 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에서 제안한대로 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 ) {}

답변

중첩 된 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;

컴파일러는 단일 단계로 이러한 작업을 수행하지만 프로세스에 대한 통찰력을 제공합니다. C # 프로그램에서 발전한 IL 코드 는 마지막 C # 코드 의 리터럴 변환 입니다. https://dotnetfiddle.net/QaiLRz 에서 직접 확인할 수 있습니다. 보기 ‘클릭)

자, 여기서 관찰 한 것은 프로세스 중에 코드가 더 복잡해진다는 것입니다. 이것을 관찰하는 가장 쉬운 방법은 동일한 것을 인식하기 위해 점점 더 많은 코드가 필요하다는 것입니다. 또한 그 주장 수도 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) 옵티 마이저 관점에서 볼 때 더 나은 솔루션입니다.

언급해야 할 또 다른 사항은 레지스터를 변수에 할당하도록 컴파일러를 최적화하는 데 매우 관련이 있다는 것입니다 ( 레지스터 할당 이라는 프로세스 ). 아시다시피, CPU에는 레지스터 수가 한정되어 있으며 하드웨어에서 가장 빠른 메모리입니다. 가장 안쪽 루프에있는 코드에 사용 된 변수는 레지스터가 할당 될 가능성이 높지만 루프 외부의 변수는 덜 중요합니다 (이 코드가 적을 수 있기 때문에).

도움, 너무 많은 복잡성 … 어떻게해야합니까?

결론은 항상 사용하는 언어 구조를 사용해야한다는 것입니다.이 구문은 일반적으로 컴파일러에 대해 예측 가능한 패턴을 빌드합니다. (: 특히 가능하면 이상한 가지 않도록하십시오 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)
  {
     // ...
  }
}

다른 경우에는 방법을 두 가지 방법으로 나눌 수도 있습니다.

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

// ...

이것에 대한 나의 개인적인 의견은 매우 간단합니다. 이것이 우리가 의도 한 것이라면 컴파일러와 가독성 모두를 위해 세상을 더 쉽게 만들고 즉시 작성하십시오.

tl; dr :

결론 :

  • 가능하면 for 루프에서 간단한 조건을 사용하십시오. 가능한 한 많이 사용하는 고급 언어 구성을 고수하십시오.
  • 모든 것이 실패하고 goto또는로 남아 있다면 bool more전자를 선호하십시오.