Search on the blog

2011年8月28日日曜日

A few Tips for Multidimensional Arrays in C/C++

A couple of questions about multidimensional arrays has occurred to my mind.
  1. memory set of multidimensional arrays
  2. abstract method of dealing indices corresponding to dimensions
The first one is simple. I got a little confused when I was doing something like this:

int dp[2][64][64];
int main() {
    /*
     * some procedures here
     */

    memset(dp[1], 0, sizeof(dp[1]));
}


So you want to set dp[1][i][j], i=0,1,..,63, j = 0,1,..,63, to zeros. Does this really work? what is the size of dp[1]?? A multidimensional array are actually a One-dimensional array. More specifically, memories are allocated to a multidimensional array as if it were a one-dimensional array. So dp[1] represents the address of dp[1][0][0]. So the size is 16384byte(64*64*8byte). It makes sense.

But how's about when you want to reset dp[0][i][j], i=0,1,..,63, j=0,1,..,63, leaving dp[1][i][j] unchanged? Does memset(dp[0], 0, sizeof(dp[0])) work? It's confusing this time.
What is the size of dp[0]? 16384byte? or 32768byte? The former is correct. Which reminds me that I sometimes do this kind of thing:

int buf[8][16];
int main() {
    cout << sizeof(buf) / sizeof(buf[0]) << endl; // 8
    cout << sizeof(buf[0]) / sizeof(buf[0][0]) << endl; // 16
}


The second question is difficult to describe. So I've prepared a simple, original problem to get the essence.

You are given a 6-dimensional array A[8][8][8][8][8][8]. Each element of A has an integer. You are given an integer n, an integer between 0 and 5, inclusive, which is the index of a moving dimension, and six integers (d0, d1, d2, d3, d4, d5), all of whom are integers between 0 and 7, inclusive. Calculate the sum A[d0'][d1'][d2'][d3'][d4'][d5'], where di' = {0,1,2,...,7} if i =n, otherwise di. (Sorry this statement may be awkward. In that case, see the example below.)

Here's an example. n = 1, (d1, d2, d3, d4, d5, d6) = (0,1,2,3,4,5).
You are to calculate A[0][0][2][3][4][5] + A[0][1][2][3][4][5] + A[0][2][2][3][4][5] + A[0][3][2][3][4][5] + A[0][4][2][3][4][5] + A[0][5][2][3][4][5] + A[0][6][2][3][4][5].

I first wrote a source code like this:

int A[8][8][8][8][8][8];

void init() {
    REP(d0, 8)REP(d1, 8)REP(d2, 8)REP(d3, 8)REP(d4, 8)REP(d5, 8)
        A[d0][d1][d2][d3][d4][d5] = d0 + d1 + d2 + d3 + d4 + d5;
}

int main() {
    int n;
    int d0, d1, d2, d3, d4, d5;

    init();

    cin >> n;
    cin >> d0 >> d1 >> d2 >> d3 >> d4 >> d5;

    int ans = 0;
    switch (n) {
    case 0:
        REP(i, 8) ans += A[i][d1][d2][d3][d4][d5];
        break;
    case 1:
        REP(i, 8) ans += A[d0][i][d2][d3][d4][d5];
        break;
    case 2:
        REP(i, 8) ans += A[d0][d1][i][d3][d4][d5];
        break;
    case 3:
        REP(i, 8) ans += A[d0][d1][d2][i][d4][d5];
        break;
    case 4:
        REP(i, 8) ans += A[d0][d1][d2][d3][i][d5];
        break;
    default:
        REP(i, 8) ans += A[d0][d1][d2][d3][d4][i];
    }

    cout << ans << endl;
}

Talk about a terrible code. Once you notice that a address is linear, you can write this cool code -- a friend of mine taught this implementation --. In this case, the size of each dimension is 8, imagine the base 8 number system, which will help you understand the code.

int A[8][8][8][8][8][8];

void init() {
    REP(d0, 8)REP(d1, 8)REP(d2, 8)REP(d3, 8)REP(d4, 8)REP(d5, 8)
        A[d0][d1][d2][d3][d4][d5] = d0 + d1 + d2 + d3 + d4 + d5;
}

int main() {
    int n;
    int d[6];

    init();

    cin >> n;
    REP(i, 6) cin >> d[i];
    d[n] = 0;

    int ans = 0;
    int *p = (int *)A;
    int base = 1, move = 0;
    REP(i, 6) {
        if (6-1-i == n)
            move = base;
        p += d[6-1-i] * base;
        base *= 8;
    }

    REP(i, 8)
        ans += *(p + move * i);

    cout << ans << endl;
}

0 件のコメント:

コメントを投稿