Почему выполнение двух последовательных циклов for более эффективно, чем выполнение одного цикла for, выполняющего те же ⇐ JAVA

[Anonymous]

При ежедневном решении сегодняшнего LeetCode
я изначально нашел решение 1 в следующем коде, но обнаружил, что лимит времени превышен
и после проверки редакционной статьи и внесения одного изменения разница в скорости была огромной.
Примечание: для пояснения проверка постановки задачи здесь не имеет значения, я сослался на нее только на тот случай, если кто-то захочет самостоятельно проверить разницу в производительности.

Код: Выделить всё

public class Main
{
public static void main(String[] args) {

final int m=1 ,n=100000;
int[][] guards  = new int[50000][2];
for (int i=0;i=0 && (grid[row-1][col]==0|| grid[row-1][col]==-1)){
grid[--row][col] = -1;
}
row =guard[0];
col =guard[1];
while (col-1>=0 && (grid[row][col-1]==0 || grid[row][col-1]==-1)){
grid[row][--col] = -1;
}
}
System.out.println("    marked unguarded in: " + (double)(System.nanoTime()-start)/1000000000 + " s");start = System.nanoTime();
int ans =0;
for (int[] row : grid){
for (int cell : row){
ans+= cell==0? 1 : 0;
}
}
System.out.println("    counted in: " + (double)(System.nanoTime()-start)/1000000000 + " s");start = System.nanoTime();
return ans;
}
}

public static class Solution2 {

public static int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
int[][] grid = new int[m][n];
long start = System.nanoTime();

//changed part begins here
for (int[] guard : guards) {
grid[guard[0]][guard[1]] = 1;
}
//end here

System.out.println("    looped over guards in: " + (double)(System.nanoTime()-start)/1000000000 + " s");start = System.nanoTime();
for (int[] wall : walls){
grid[wall[0]][wall[1]] = 2;
}
System.out.println("    marked walls in: " + (double)(System.nanoTime()-start)/1000000000 + " s");start = System.nanoTime();

for (int[] guard : guards){
int row =guard[0] ,col =guard[1];
//removed assignment statement from here
while (row+1 < m && (grid[row+1][col]==0||grid[row+1][col]==-1)){
grid[++row][col] = -1;
}
row =guard[0];
col =guard[1];
while (col+1 < n && (grid[row][col+1]==0|| grid[row][col+1]==-1 )){
grid[row][++col] = -1;
}
row =guard[0];
col =guard[1];
while (row-1 >=0 && (grid[row-1][col]==0|| grid[row-1][col]==-1)){
grid[--row][col] = -1;
}
row =guard[0];
col =guard[1];
while (col-1>=0 &&  (grid[row][col-1]==0 || grid[row][col-1]==-1)){
grid[row][--col] = -1;
}
}
System.out.println("    marked unguarded in: " + (double)(System.nanoTime()-start)/1000000000 + " s");start = System.nanoTime();
int ans =0;
for (int[] row : grid){
for (int cell : row){
ans+= cell==0? 1 : 0;
}
}
System.out.println("    counted in: " + (double)(System.nanoTime()-start)/1000000000 + " s");start = System.nanoTime();
return ans;
}
}

}

Если это не очевидно:
решение 1:
как присваивание, так и вложенные циклы были выполнены в то же самое для цикла.

Код: Выделить всё

for (int[] guard : guards) {
grid[guard[0]][guard[1]] = 1;
//nested while loops
}

solution2:
присвоение Grid[row][col] было выполнено в отдельном цикле for

Код: Выделить всё

for (int[] guard : guards){
grid[row][col] = 1;
}

затем остальная часть кода выполнялась в отдельном цикле:

Код: Выделить всё

for (int[] guard : guards) {
//while loops here
}

Теперь, когда вы запускаете эту программу для проверки производительности, вот результат:

Код: Выделить всё

     marked walls in: 3.745E-6 s
marked unguarded in: 2.484305858 s
counted in: 0.001637169 s
execution time of algo1: 2.512722404 s
looped over guards in: 0.001219871 s
marked walls in: 4.66E-7 s
marked unguarded in: 0.005228443 s
counted in: 2.87943E-4 s
execution time of my  algo2: 0.008547069 s

Отмечено как незащищенное (так называемый цикл for с вложенными циклами while) в первом решении заняло 2,5 секунды, однако во втором решении потребовалось 0,005.
Что такое Меня сводит с ума то, что буквально единственная разница заключается в том, что я назначил массив сетки в решении 1 в цикле for, специально предназначенном для присвоения 1, а в другом коде я выполнил назначение так же, как и другой код.
Один привел к TLE и другой нет?

Подробнее здесь: https://stackoverflow.com/questions/792 ... -doing-a-s