如果我有一个嵌套在另一个循环中的for循环,我如何才能以最快的方式有效地从两个循环(内部和外部)中出来?

我不想必须使用布尔值然后必须说转到另一个方法,而只是在外部循环之后执行第一行代码。

有什么又快又好的方法呢?

我在想异常并不便宜/只应该在真正异常的情况下抛出等等。因此,从性能的角度来看,我不认为这个解决方案是好的。

我不认为利用。net中的新特性(anon方法)来做一些非常基础的事情是正确的。


当前回答

自从几十年前我第一次看到C语言中的break,这个问题就一直困扰着我。我希望一些语言增强会有一个扩展打破,这样工作:

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.

其他回答

好吧,去吧,但那很难看,而且并不总是可能的。您还可以将循环放入方法(或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");

我认为除非你想做“布尔的事情”,否则唯一的解决方案实际上是抛出。你显然不应该这么做!

我就设个旗子。

var breakOuterLoop = false;
for (int i = 0; i < 30; i++)
{
    for (int j = 0; j < 30; j++)
    {
        if (condition)
        {
            breakOuterLoop = true;
            break;
        }
    }
    if (breakOuterLoop){
        break;
    }
}

您要求的是快速、漂亮、不使用布尔、不使用goto和c#的组合。你已经排除了所有可能的方法去做你想做的事。

最快捷和最不丑陋的方法是使用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(点击“查看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优化期间发挥神奇的作用。

然而,分支往往会破坏这些良好的可预测模式,这是优化器不喜欢的。Break, continue, goto——他们都想打破这些可预测的模式,因此并不是真的“好”。

此时,您还应该意识到,简单的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)
  {
     // ...
  }
}

在其他情况下,你也可以把这个方法分成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.
  // ...
}
// ...

我个人反对这种方法。再看看代码是如何编译的。现在想想这些漂亮的,可预测的模式会带来什么。明白了吗?

好吧,让我解释一下。接下来会发生的是:

The compiler will write out everything as branches. As an optimization step, the compiler will do data flow analysis in an attempt to remove the strange more variable that only happens to be used in control flow. If succesful, the variable more will be eliminated from the program, and only branches remain. These branches will be optimized, so you will get only a single branch out of the inner loop. If unsuccesful, the variable more is definitely used in the inner-most loop, so if the compiler won't optimize it away, it has a high chance to be allocated to a register (which eats up valuable register memory).

因此,总结一下:编译器中的优化器会遇到很多麻烦,以确定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:

// ...

我个人对此的看法很简单:如果这是我们一直以来的意图,那么让我们让编译器和可读性都变得更容易,并立即编写它。

tl; diana:

底线:

如果可能的话,在for循环中使用一个简单的条件。尽可能地使用您所掌握的高级语言结构。 如果一切都失败了,只剩下goto或bool类型,选择前者。