なぜbreak関数はforループに余分な処理時間を追加しますか？

Question

私は現在、単純な最適化に関する本を読んでいます。 た図示アルゴリズムのいずれかを：

プリント + B = C + D、B、C、Dが 未満で（のすべてのソリューション1000）

（それは私の遅いネットブック上で迅速に実行しますので、私は100と一緒に行きました）

I programmed up their solution（その解決法とその最初に提供された最適化が含まれています）しかし、提案されたブレーク最適化は実際にアルゴリズムをかなり遅くしました。

public static void doUnoptimised() { 
    for(int a = 1; a < 100; a++) 
    { 
     for(int b = 1; b < 100; b++) 
     { 
      for(int c = 1; c < 100; c++) 
      { 
       for(int d = 1; d < 100; d++) { 
        if(Math.pow(a, 3) + Math.pow(b, 3) == Math.pow(c, 3) + Math.pow(d, 3)) 
        { 
         System.out.println("A:" + a + " B:" + b + " C:" + c + " D:" + d); 
        } 
       } 
      } 
     } 
    } 
} 

public static void doFirstOptimised() { 
    for(int a = 1; a < 100; a++) 
    { 
     for(int b = 1; b < 100; b++) 
     { 
      for(int c = 1; c < 100; c++) 
      { 
       for(int d = 1; d < 100; d++) { 
        if(Math.pow(a, 3) + Math.pow(b, 3) == Math.pow(c, 3) + Math.pow(d, 3)) 
        { 
         System.out.println("A:" + a + " B:" + b + " C:" + c + " D:" + d); 
         break; 
        } 
       } 
      } 
     } 
    } 
} 

なぜですか？これは私の解決策ではないことに注意してください。これは本に示されたものですが、後でさらに最適化が行われますが、この最適化がなぜこのような壮大な失敗であったかに興味があります。

編集 - おそらく私はここで十分に明確ではない。私はこれがほとんど目に見えない変化であることを知っています。なぜこれが改善であるのかを理解しており、本で提供されているより良い最適化を既に行っています。 （しかし、より良い最適化を与えてくれてくれてありがとう、努力を感謝する）しかし、この特定のステップ1は全く働かないし、なぜか分かっている。しかし、この段階で私のjvmはちょっと変わったようです。

Answer 1

この最適化では、a,bおよびcのいずれの組み合わせに対しても可能なのは1つのみであるという仮定があります。

break;が実行するのは内側のループを止めることで解決策が見つかると、別のものを探すことをあきらめることができ、作業が節約され、時間が短縮されます。

このようにbreak;を使用する方がはるかに優れた最適化がたくさんありますが、それほど工夫が必要な状況ではreturnが一般的な最適化です。

例えば、nullの値を無視してArrayList.indexOfを実装するとどうでしょうか。

public int indexOf(Object o) { 
    int index = -1; 
    for (int i = 0; i < size; i++) 
     if (o.equals(elementData[i])) 
      if (index == -1) 
       index = i; 
    return index; 
} 

注：これは、最初のエントリであってもすべてのエントリをスキャンする必要があります。より速い方法はbreakを使って言うことです。解決策があれば繰り返しをやめてください。それがない次の事を考慮にnull値をとるreturn

public int indexOf(Object o) { 
    for (int i = 0; i < size; i++) 
     if (o.equals(elementData[i])) 
      return i; 
    return -1; 
} 

あるので

public int indexOf(Object o) { 
    int index = -1; 
    for (int i = 0; i < size; i++) 
     if (o.equals(elementData[i])) 
      index = i; 
      break; 
     } 
    return index; 
} 

しかし、ブレークはここでは必要とされていない、実際の実装は

public int indexOf(Object o) { 
    if (o == null) { 
     for (int i = 0; i < size; i++) 
      if (elementData[i]==null) 
       return i; 
    } else { 
     for (int i = 0; i < size; i++) 
      if (o.equals(elementData[i])) 
       return i; 
    } 
    return -1; 
}