using 2-dimensional arrays is faster than two of 1-dimensional arrays?

Question

static int ud[] = new int[] { 0, 0, 1 };

static int lr[] = new int[] { -1, 1, 0 };

static int dirs[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 } };

public static int solve(int r, int c, int dir) {
    if (r == n - 1 && c == m - 1)
        return v[r][c];

    if (dp[r][c][dir] != -INF)
        return dp[r][c][dir];

    visited[r][c] = true;
    int ans = -200000;

    for (int i = 0; i < 3; i++) {
        int nr = r + dirs[i][0]; # no time out
        int nc = c + dirs[i][1]; # no time out

        // int nr = r + ud[i]; # time out 
        // int nc = c + lr[i]; #  time out 
        if (nr < 0 || nc < 0 || nr >= n || nc >= m)
            continue;

        if (visited[nr][nc])
            continue;

        ans = Math.max(ans, solve(nr, nc, i) + v[r][c]);

    }
    visited[r][c] = false; 
    return dp[r][c][dir] = ans;
}

I wanted to move row,col to up,left,right in 2-dimensional arrays so I declared two of 1-dimensional arrays as usually and I submitted my code but the answer is fail and I declared 2-dimensional arrays instead of two of 1-dimensional and I submitted my code and the answer is passed, I don't know the why 2-dimensional arrays is faster than two of 1-dimensional arrays?

score 0 · Accepted Answer · answered May 31 '21 at 03:39

It depends on how did you use your one dimensional arrays.

Two dimensional array elements stored in memory consequently, while two one dimensional arrays may start at different memory addresses.

If you are accessing two dimensional array many times, it will be faster, because most of its values are already in cache. This is called "Spatial locality". On the other hand, if you are accessing two one dimensional arrays one by one, it will force your computer to load data from memory into cache, which is way slower.

Anyway, it would be better, if you post both versions of your code.

using 2-dimensional arrays is faster than two of 1-dimensional arrays?

1 Answers1