CODEWITHSUNDEEP
java
JulieK
JulieK

Reputation: 19

Two-dimensional array iteration approach is faster than another approach

I know that the results are same, but the first loop is faster than the second loop. Why is that?

int[][] values = new int[10][20];

int sum = 0;
int count = 0;
for (int j = 0; j < 20; j++) {

    for (int i = 0; i < 10; i++) {
        count++;
        values[i][j] = count;

        sum += values[i][j];
    }

}
System.out.println(sum);

int[][] values = new int[10][20];

int sum = 0;
int count = 0;
for (int i = 0; i < 10; i++) {

    for (int j = 0; j < 20; j++) {
        count++;
        values[i][j] = count;

        sum += values[i][j];
    }

}
System.out.println(sum);

Upvotes: 0

Views: 126

Answers (2)

Makoto
Makoto

Reputation: 106508

This is a loop interchange.

While I can't exactly observe the same results as your machine (mine is quite beefy with an Intel i7-4770K, and the code is in a very simple class I use for Stack Overflow questions), in general this sort of loop has the propensity to be more performant.

The primary reason that it's more performant is due to the locality of the elements it's iterating over. It is more efficient to iterate over contiguous memory than it is non-contiguous memory.

Let's consider a typical array:

int[] anArray = new int[5];

In memory, Java will reserve* five contiguous blocks of that are capable of holding an int.

int[5] -> [][][][][]

*: Or at least try to.

For a two-dimensional array, Java will do the same operation, with the catch that instead of it appearing like a grid in memory (as C does), you will have an array that points to arrays.

int[2][3] -> [ ] [ ]
              |   |
              v   v
             [ ] [ ]
             [ ] [ ]
             [ ] [ ]

In terms of memory layout, the second-tier arrays (that is, those of length 20) are likely closer in memory to each other than they are with the first-tier arrays (that is, those of length 10). It's more efficient to iterate over contiguous memory than it is non-contiguous memory, which is why you're noticing a speed improvement.

Upvotes: 3

joshstrike
joshstrike

Reputation: 1823

Because you forgot to switch [i][j] in values when you push them into that array.

Upvotes: 0

Related Questions