Java- Mapping multi-dimensional arrays to single

Question

I am posting this in relation to another open question i have, however I thought that this deserved it's own question.

Alternate question (for reference): Java Proxy Discovering Bot

Basically, I need to store a very large amount of data and have it accessible very quickly. This would work ideally in an unlimited memory situation:

boolean[][][][] sets = new boolean[256][256][256][256];
boolean get(byte[] a) {
    return sets[a[0]][a[1]][a[2]][a[3]];
}

However, this uses around 16gb of ram which is too much for my application. I figure that if using bits instead of booleans (stores as 4 bytes in Java) it would cut the memory usage to around 512MB. However, I can't seem to wrap my head around how to access the bits correctly. For example if you mapped each address something like this: position = a * b * c * d then it would map to the same bit as d * c * b * a etc.

I found this thread covering how to convert 2D arrays into 1D arrays, but I can't seem to wrap my head around how to extend that to a 4D array. Can anyone explain this? Map a 2D array onto a 1D array C

The solution for 2D -> 1D arrays:

int array[width * height];
int SetElement(int row, int col, int value)
{
  array[width * row + col] = value;  
}

I am just not sure of how to extend it to 4D -> 1D

 int array[256 * 256 * 256 * 256];
 int setElement(int a, int b, int c, int d, boolean value)
 {
    array[?????????] = value;  
 }

You can use the BitSet class in Java. Also, you need not remove any but the last dimension. So a three dimensional array of bit sets, where the fourth dimension of the booleans gets collapsed into a BitSet should work well, I think? — flup, Mar 13 '15 at 00:54
@flup I just tested that, a three dimensional array of BitSet. However it is taking over 5 minutes to initialize them.. (Ongoing, hasn't completed yet) I would rather only use one bit set, it seems that this is possible with the right way to access the bits. — Colby, Mar 13 '15 at 01:10

score 1 · Accepted Answer · answered Mar 13 '15 at 01:13

To answer about mapping 4D to 1D, if you visualize, say, a chess board, you can come up with the formula for 2D to 1D by thinking if every row has width elements, and I first go down row number of rows and then move over to col, then I'm at width * row + col. Now imagine a stack of height number of chess boards and carry out the same exercise to extend it to three dimensions. Four dimensions is harder because you can't really visualize it, but by then you can see the pattern.

This program shows the formula for four dimensions. I ran it for very small numbers for posting here, but you can play with the dimensions and see how it works.

class Dim
{
    // dimensions
    static int d1 = 2 ;   // "rows"
    static int d2 = 2;    // "cols"
    static int d3 = 3;    // "height"
    static int d4 = 2;    // the fourth dimension!

    public static void main(String[] args) {
        for (int i=0; i<d1; i++) {
            for (int j=0; j<d2; j++) {
                for (int k=0; k<d3; k++) {
                    for (int m=0; m<d4; m++) {
                        int oneD = fourDtoOneD(i, j, k, m);
                        System.out.printf("(%d, %d, %d, %d) -> %d\n", i, j, k, m, oneD);
                    }
                }
            }
        }
    }

    static int fourDtoOneD(int i, int j, int k, int m) {
        return ((d2*d3*d4) * i) + ((d2*d3) * j) + (d2 * k) + m;
    }
}


$ java Dim
(0, 0, 0, 0) -> 0
(0, 0, 0, 1) -> 1
(0, 0, 1, 0) -> 2
(0, 0, 1, 1) -> 3
(0, 0, 2, 0) -> 4
(0, 0, 2, 1) -> 5
(0, 1, 0, 0) -> 6
(0, 1, 0, 1) -> 7
(0, 1, 1, 0) -> 8
(0, 1, 1, 1) -> 9
(0, 1, 2, 0) -> 10
(0, 1, 2, 1) -> 11
(1, 0, 0, 0) -> 12
(1, 0, 0, 1) -> 13
(1, 0, 1, 0) -> 14
(1, 0, 1, 1) -> 15
(1, 0, 2, 0) -> 16
(1, 0, 2, 1) -> 17
(1, 1, 0, 0) -> 18
(1, 1, 0, 1) -> 19
(1, 1, 1, 0) -> 20
(1, 1, 1, 1) -> 21
(1, 1, 2, 0) -> 22
(1, 1, 2, 1) -> 23

Thank you, very clearly written and explained. If you would like to also post this answer in a format answering the previous question (in order to make it easier to find for future users) I linked to I would be happy to award you the answer there as well. — Colby, Mar 13 '15 at 01:20
Glad it helped! I think it's fine to have the code in the other question with the link back here for more information, just as you've done. Btw, for your case with the IPs, another way to think about it is to consider the four sections of the IP as four "digits" in base 256 that you want to convert to base 10. I.e.: `256^3(i) + 256^2(j) + 256^1(k) + 256^0(m)`. — jas, Mar 13 '15 at 01:57
Here is one problem. 256^4 is larger than Integer.MAX_VALUE. This means that when attempting to access higher range ips the bit pointer (fourDtoOneD) actually goes into the negative. I'm sure I could get around this by using an array of 256 bit sets or something, but that doesn't seem very elegant. Although there is no real elegant way to do this. However this works perfectly up until the integer limit is reached. That is more of a problem for my other thread though not this one. Ironically, new BitSet(256 * 256 * 256 * 256) returns a set with length 0 :X — Colby, Mar 13 '15 at 02:03
how about you leave one dimension in place then, and create 256 BitSets? — flup, Mar 13 '15 at 08:36

Java- Mapping multi-dimensional arrays to single

1 Answers1

Linked