java - 为什么break函数会给for循环增加额外的处理时间？

Question

我目前正在阅读一本关于简单优化的书。显示的算法之一是:

Print all solutions to a³ + b³ = c³ + d³ (where a, b, c, d are less than 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;
                    }
                }
            }
        }
    }
}

这是为什么呢？请注意，这不是我的解决方案，这是书中所示的解决方案，他们稍后会继续进行更多优化，但我感兴趣的是为什么这种优化如此失败。

编辑-也许我在这里还不够清楚。我知道这是一个几乎不明显的变化，我理解为什么这是一个改进，并且已经完成了书中提供的更好的优化。 (感谢那些提供更好优化的人，感谢您的努力)但是，这个特定的步骤根本不起作用，我试图找出原因。但在这个阶段，我的 jvm 似乎很奇怪。

Answer 1

此优化中有一个假设，即只有一种可能的 d对于 a 的任意组合, b和c .

什么是break;所做的就是停止内部循环，因此一旦我们有了解决方案，我们就可以放弃寻找另一个解决方案，这样可以节省工作，从而减少时间。

还有很多更好的优化，但是使用break;像这样，或者 return是在不太人为的情况下使用的常见优化。

例如，您如何实现 ArrayList.indexOf 天真地忽略 null值。

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来表示；如果我有解决方案，请停止迭代。

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

但是，这里不需要break，因为它接下来要做的是return

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

考虑到null值，实际实现是

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