Почему функция break добавляет дополнительное время обработки для циклов for?

Question

В настоящее время я работаю над книгой по простой оптимизации. Один из показанных алгоритмов был:

Вывести все решения для a³ + b³ = c³ + d³ (где a, b, c, d меньше 1000)

(Я пошел с 100, чтобы он работал быстрее на моем медленном нетбуке)

Я запрограммировал их решение (их решение и их первая предложенная оптимизация включены), однако предложенная оптимизация прерывания фактически сделала алгоритм немного медленнее.

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

Примечание: это должно сканировать каждую запись, даже если это первая найденная запись. Более быстрый способ - использовать перерыв, чтобы сказать; прекратить итерации, если у меня есть решение.

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

Однако, перерыв здесь не нужен, потому что следующая вещь, которую он делает, это 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;
}