Какой цикл более эффективен? - PullRequest
Новая
       33

Какой цикл более эффективен?

0 голосов
/ 06 июля 2019

Я хочу знать, какой код более эффективен, и у меня есть два варианта. Что бы вы сказали, что это более эффективно и почему? Спасибо.

Вариант A 

array1 size is 1000
array2 size is 2000

for(int i = 0; i < array1.size(); i++)
{
    for(int j = 0; j < array2.size(); j++) {
        if(array1[i].method() == array2[j].method()) // CHECKS IF THERE'S AN EQUAL IN BOTH ARRAYS
        {
            doSomething();
            break;
        }
        if(j == array2.size()-1) // CHECKS IF ARRAY1 DID NOT FIND A MATCH
        {
            doSomething();
            break;
        }
        for(k = 0; k < array1.size(); k++)
        {
            if(array1[k].method() == array2[j].method()) // CHECKS IF THERE'S AN EQUAL IN BOTH ARRAYS
            {
                // BUT DOES NOTHING BECAUSE IT WAS DONE ALREADY UPSIDE
                break;
            }
            if(k == array1.size()-1) // CHECKS IF ARRAY2 DID NOT FIND A MATCH
            {
                doSomething();
                break;
            }
        }
    }
}

Вариант B 

array1 size is 1000
array2 size is 2000


    for(int i = 0; i < array1.size(); i++)
    {
        for(int j = 0; j < array2.size(); j++) {
            if(array1[i].method() == array2[j].method()) // CHECKS IF THERE'S AN EQUAL IN BOTH ARRAYS
            {
                doSomething();
                break;
            }
            if(j == array2.size-1)  // CHECKS IF ARRAY1 HAS NO ARRAY2 MATCH
            {
                doSomething();
                break;
            }
        }
    }

    for(int j = 0; j < array2.size(); j++)
    {
        for(int i = 0; i < array1.size(); i++) {
            if(array2[j].method() == array1[i].method()) // CHECKS IF THERE'S AN EQUAL IN BOTH ARRAYS
            {
                // BUT DOES NOTHING BECAUSE IT WAS DONE ALREADY UPSIDE
                break;
            }
            if(i == array1.size-1) // CHECKS IF ARRAY2 HAS NO ARRAY1 MATCH
            {
                doSomething();
                break;
            }
        }
    }

В настоящее время у меня реализована ОПЦИЯ B, и мне интересно, стоит ли мне переходить к ВАРИАНТУ A, потому что, хотя для Вариантов A может потребоваться больше времени, я не знаю, займет ли это больше времени, выполняя оба цикла, или один, выполняющий все итерации , Или, может быть, то же самое, я действительно не знаю об этом.

Ответы [ 3 ]

1 голос
/ 06 июля 2019

Как сказал @ Sploder12, но вы также много выиграете, принимая вызовы функций в цикле, например 

int n= array.size()
for(int i=0; i<n; i++)

вместо 

 for(int i=0; i<array.size(); i++)

Если вы не изменяете размер массива в цикле, повторные вызовы функций являются пустой тратой.

1 голос
/ 06 июля 2019

Опция A - это O (x ^ 2 * y) Вариант B - это O (x * y) в вашем случае вариант A будет занимать до 2 000 000 000 итераций, а B - до 4 000 000 итераций. Это не включает перерывы или продолжается, конечно. Я бы, наверное, придерживался B.

0 голосов
/ 07 июля 2019

Что касается комментария @ Turing85, я действительно задавался вопросом, может ли существовать какой-либо механизм компилятора, который мог бы обнаружить тот факт, что возвращаемое значение size () в инициализациях цикла может быть постоянным и, следовательно, может быть заменено на постоянное " окончательно " Поэтому я запустил следующие два цикла, первый без оптимизации констант вручную: 

int n1=a1.size();
for(int i=0; i<a1.size(); i++) {
    int n2=a2.size();
    for(int j=0; j<a2.size(); j++) {
        int n3=a3.size();
        for(int k=0; k<a3.size(); k++) {
            int candidate=a1.get(i)*a2.get(j)*a3.get(k);
            candidate+=n1*n2*n3;
            func(candidate);
        }//k
    }//j
}//i

Второй с ручной постоянной оптимизацией: 

int n1=a1.size();
for(int i=0; i<n1; i++) {
    int n2=a2.size();
    for(int j=0; j<n2; j++) {
        int n3=a3.size();
        for(int k=0; k<n3; k++) {
            int candidate=a1.get(i)*a2.get(j)*a3.get(k);
            candidate+=n1*n2*n3;
            func(candidate);
        }//k
    }//j
}//i

Затем я выполнил эти циклы 10 раз с a1.size () = 100, a2.size () = 200 и a3.size () = 300, чтобы получить время, и рассчитал среднее и стандартную ошибку 100 раз для каждый вариант цикла с порядком 200 прогонов рандомизирован.

Весь этот процесс повторялся 10 раз в рамках одного задания (то есть одного вызова JVM) для получения 10 парных средних и стандартных ошибок (один член пары из оптимизированных прогонов, а другой из неоптимизированных прогонов). Во всех 10 случаях оптимизированное среднее время было значительно быстрее, чем неоптимизированное среднее время. В каждом случае разница между средними значениями была более чем в 6,9 раза больше стандартной ошибки, а в 7 из 10 случаев разница между средними составляла более 15 стандартных ошибок. Данные приведены ниже. Байт-код, сгенерированный для циклов, был другим, и хотя я не претендую на то, чтобы произносить байт-код, были дополнительные вызовы invokevirtual для * .size (), которые, как я полагаю, ответственны за различия в производительности двух версий цикла.

Итак, принимая во внимание комментарий @ Turing85, мне интересно, при каких условиях оптимизацию «на этом уровне» можно игнорировать?

openjdk версия "11" 2018-09-25 Среда выполнения OpenJDK 18.9 (сборка 11 + 28) OpenJDK 64-битный сервер VM 18.9 (сборка 11 + 28, смешанный режим)

====== Данные ======

100 прогонов оптимизированного цикла занимали в среднем 6,412 с каждый, стандартная ошибка 0,013; 100 циклов неоптимизированного цикла заняли в среднем 6,502 с каждый, стандартная ошибка 0,013

100 прогонов оптимизированного цикла занимали в среднем 5,143 с каждый, стандартная ошибка 0,004; 100 циклов неоптимизированного цикла заняли в среднем 5,232 с каждый, стандартная ошибка 0,005

100 прогонов оптимизированного цикла занимали в среднем 6,090 с каждый, стандартная ошибка 0,006; 100 циклов неоптимизированного цикла занимали в среднем 6,175 с каждый, стандартная ошибка 0,006

100 прогонов оптимизированного цикла занимали в среднем по 5,739 с каждый, стандартная ошибка 0,005; 100 циклов неоптимизированного цикла заняли в среднем 5,827 с каждый, стандартная ошибка 0,005

100 прогонов оптимизированного цикла занимали в среднем 5,613 с каждый, стандартная ошибка 0,005; 100 циклов неоптимизированного цикла заняли в среднем по 5,687 с каждый, стандартная ошибка 0,004

100 прогонов оптимизированного цикла занимали в среднем 6,045 с каждый, стандартная ошибка 0,004; 100 циклов неоптимизированного цикла заняли в среднем 6,121 с каждый, стандартная ошибка 0,004

100 прогонов оптимизированного цикла занимали в среднем 5,333 с каждый, стандартная ошибка 0,003; 100 циклов неоптимизированного цикла заняли в среднем 5,415 с каждый, стандартная ошибка 0,003

100 прогонов оптимизированного цикла заняли в среднем 5,903 с каждый, стандартная ошибка 0,009; 100 циклов неоптимизированного цикла заняли в среднем 5,972 с каждый, стандартная ошибка 0,007

100 прогонов оптимизированного цикла занимали в среднем 5,770 с каждый, стандартная ошибка 0,005; 100 циклов неоптимизированной петли занимали в среднем 5,851 с каждый, стандартная ошибка 0,005

100 прогонов оптимизированного цикла занимали в среднем 4,975 с каждый, стандартная ошибка 0,004; 100 циклов неоптимизированного цикла занимали в среднем 5,052 с каждый, стандартная ошибка 0,004

...