Java creating augmented array of size 400,000,000

Question

I was solving one competitive coding question having integer bounds 2^100. Fortunately, it was a dp question and I didn't need an array of that size. Practically we cannot create an array of size more than Integer.MAX_VALUE.

But I was thinking of creating a multidimensional array and treat it as a one-dimensional array.

what I need was a very large array with O(1) retrieval time. So Internally it will be a multidimensional array but I will treat it as a one-dimensional array.

So the size of the resultant array will be n*n.

if n is Integer.MAX_VALUE then the resultant augmented array will be of Integer.MAX * Integer.MAX

Here what I did to implement this idea.

BigArray class

public class BigArray
{
    
    private int[][] arr;
    private int row=0;
    private int col = 0;
    private int size;
    public BigArray(int size)
    {
        arr = new int[size][size];
        this.size = size;
    }
}

add method

public void add(int data)
    {
     if(row > size-1)
        {
            col++;
            row=0;
            this.arr[col][row] = data;
            row++;
        }
        else
        {
            this.arr[col][row] = data;
            row++;
        }
    }

get method

public int get(int pos)
    { //get value in O(1)
        if((int) Math.sqrt(pos) > size)
            return -1;
        int col1 = pos/(size);
        int row1 = pos%(size);
        return arr[col1][row1];     
    }

But If I pass Integer.MAX_VALUE in BigArray it throws Exception in thread "main" java.lang.OutOfMemoryError: Requested array size exceeds VM limit maximum size I've tried is 20,000 so resultant size will be 20,000 x 20,000 = 400,000,000.

But if add one more dimension to this array I'll get more space.

if BigArray has arr[][][] resultant size will be n x n x n; if BigArray has arr[][][][] resultant size will be n x n x n x n; and so on.

I know I had to implement necessary methods as I add a new dimension to the base array.

But I would like a review on this type of storage class. I don't know

what's the maximum dimensions java array can have?

Also, do tell me

• if can use this approach to create arrays size more than the traditional array size
• Future scope such as generic BigArray of character will create string greater size
• other opinions/suggestions on this approach

Answer 1

An int is 32 bits? Then your 400,000,000 array requires ...

... 1,600,000,000 bytes == 1,600,000 KB == 1,600 MB == 1.6 GB

Have you configured your JVM to have that much RAM? You need some overhead for the application, so I'd probably configure 1.76 GB or so.

Answer 2

The biggest problem I can see with this approach, is that a user can't add or get any index higher than Integer.MAXVALUE. You might need to parse Strings or use a BigInteger type instead of int for those methods.

Answer 3

Have you increased the size of your VM? If not, you will not get past java.lang.OutOfMemoryError: Requested array size exceeds VM limit without doing something creative like storing the array in a file.

Do you need 4-byte integers, or would 2-byte shorts be sufficient?

This is allocating all the memory in one chunk:

arr = new int[size][size];

Perhaps you should use:

arr = new int[size][];
arr[0] = new int[size];

to allocate one chunk to hold the columns, one chunk to hold the first column, and then as data is being added, allocate new columns on demand:

public void add(int data) {
    if (row >= size) {
        arr[++col] = new int[size];
        row = 0;
    }

    arr[col][row]  = data;
    row++;
}

Using a variable size, or even Integer.MAX_VALUE to partition data into rows, columns, and higher dimensions is inefficient. I’d use a hard-coded power of 2, to allow efficient module arithmetic.

Answer 4

In addition to the answer @tinstaafl provided, I think that your class doesn't behave like arrays are implemented: namely, it is allocated in different places in the program's memory space. You can't, for instance, call System.arraycopy() to make a copy out of it.

I think that you implement here a specific Map, with keys as integers (or longs, as mentioned), and values as integers.