java break语句是否使我的代码更快？

Question

我本来应该写一段代码来说明数组是否有重复项。运行时间并不重要。我认为我下面的代码将有O(n²)，因为我使用了嵌套的for循环。我知道有比我写的代码更好更快的代码，但是我的问题是，我在if语句中做的break语句是否会使我的代码（稍微）更快它应该会让它更快，因为程序知道“嘿，我们找到了一个副本，我们可以停止搜索更多”。我曾经听一位同学说，如果我避免使用像return或break这样的语句，代码会更好/更稳定。可惜那时我没有足够的关心去问为什么。也许你能告诉我这是不是真的

如果他是对的，并且这些语句“伤害”了我的代码，那么还有更好的解决方法吗

public class FindDuplicate{
    public static void main(String[] args){
        int[] A={1,2,3,4,5,6,7,8,4};
        boolean bool=false;
        for(int i=0; i<A.length; i++){
            for(int j=0; j<A.length; j++){
                if(A[i]==A[j] && i!=j){
                    bool=true;
                    break;
                }
            }
        }
        if(bool==true){
            System.out.print("Duplicate found");
        }else{
            System.out.print("No duplicate found");
        }
    }
}

Answer 1

my question is if the break statement I made inside the if-statement will make my code (a bit) faster?

然而，并不是在所有情况下，在大多数情况下，考虑到你不必在找到你想要的东西后不断迭代，它确实会让你的代码更快

---

下面的算法包含两个嵌套循环。外部循环遍历数组的所有N项，因此需要O(N)个步骤。 对于通过外循环的每次行程，内循环也会迭代数组中的N项，因此它也会执行takes O(N)步。 因为一个循环嵌套在另一个循环中，所以组合的性能是O(N × N) = O(N2)

for(int i = 0; i < A.length; i++){
    for(int j=0; j < A.length; j++){
       if(A[i] == A[j] && i != j){
           bool = true;
           break;
       }
    }
}

通过在外循环的每次迭代中不返回j = 0，我们可以使算法更快一些

for(int i = 0; i < A.length; i++){
  for(int j = i+1; j < A.length; j++){
     if(A[i] == A[j]){
         bool = true;
         break;
     }
  }
}

注意，在这种情况下，我们不需要检查^{，因为它们永远不会相等

---

I once heard from a fellow student that the code is better / more stable if I avoid statements like return or break

当使用break时，JVM规范没有说明是否存在性能损失。简单地说，没有任何证据表明使用break或return会使代码不稳定（据我所知并非如此）。我唯一会说“哦，这不是一个好的做法”的情况是当你过度使用break这个词时。然而，在许多情况下break是更快完成任务的唯一可能，例如您当前的解决方案。基本上，当你找到你想要的东西时，为什么还要继续迭代呢？。我认为^ {CD11}}也不是“坏的实践”，因为类似于{{CD9}}，为什么在不需要的时候继续执行代码，这肯定会使代码更快。p>

---

我们能让查找重复算法更快吗

当然，我们可以考虑java中的不允许重复的^{}接口，它是基于哈希表数据结构的，所以在平均情况下插入^ ^ }时间。通过使用^{}，一种通用的^{}实现，我们可以在O(n)时间内找到重复项。由于^{}只允许唯一的元素，因此^{}方法在尝试添加重复项时将失败并返回false

解决方案：

public static boolean hasDuplicate(int[] array) {
      Set<Integer> dupes = new HashSet<Integer>();
      for (Integer i : array) {
          if (!dupes.add(i)) {
             return true; // we have found a duplicate
          }
      }
      return false; // no duplicate
}

Answer 2

实际上，您不需要bool标志变量，也不需要使用breakreturn将停止迭代，如果未找到重复项，则返回false：

private static boolean findDuplicateOriginal(int[] A) {
    for(int i=0; i<A.length; i++){
        for(int j=0; j<A.length; j++){
            if(A[i]==A[j] && i!=j){
                return true;
            }
        }
    }
    return false;
}

只需要指出，性能不应该是编码时的唯一目标。您应该像担心性能一样担心可维护性或编写更少/干净的代码。 它取决于上下文（调用该函数的频率、应该进行多少次迭代、是否使用并行流运行？…）你的应用程序运行是为了选择一种或另一种做事方式

很多帖子都在讨论循环性能与流性能，以及支持和反对的观点：

• https://blog.jooq.org/2015/12/08/3-reasons-why-you-shouldnt-replace-your-for-loops-by-stream-foreach/
• Java 8 Iterable.forEach() vs foreach loop
• http://endoflineblog.com/benchmarking-java8-streams

我只是想让你看看有多干净（1行！）正在为相同的purpouse使用Java8语法：

import java.util.Arrays;

public class test {

public static void main(String[] args) {
    int[] A = {1,2,3,4,5,6,7,8,9};
    System.out.println(Arrays.toString(A) + " using findDuplicate >> " + findDuplicate(A));
    System.out.println(Arrays.toString(A) + " using findDuplicateOriginal >>" + findDuplicateOriginal(A));

    int[] B = {1,1,3,4,5,6,7,8,4};
    System.out.println(Arrays.toString(B) + " using findDuplicate >> " + findDuplicate(B));
    System.out.println(Arrays.toString(B) + " using findDuplicateOriginal >> " + findDuplicateOriginal(B));
}

// using streams
private static boolean findDuplicate(int[] items) {
    return !(Arrays.stream(items).distinct().count() == items.length);
}

// refactored original version
private static boolean findDuplicateOriginal(int[] A) {
    for(int i=0; i<A.length; i++){
        for(int j=0; j<A.length; j++){
            if(A[i]==A[j] && i!=j){
                return true;
            }
        }
    }
    return false;
}
}

输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9] using findDuplicate >> false
[1, 2, 3, 4, 5, 6, 7, 8, 9] using findDuplicateOriginal >>false
[1, 1, 3, 4, 5, 6, 7, 8, 4] using findDuplicate >> true
[1, 1, 3, 4, 5, 6, 7, 8, 4] using findDuplicateOriginal >> true