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

• D. Jurcau: How big of an array are you actually aiming for? Multidimensional with Integer.MAX_VALUE each dimension would be huge
• Ashish Pawar: Yes Im trying create array of size larger than Integer.MAX
• Carcigenicate: Is it not an option to just use streams for the challenge? It doesn't seem practical to try and have that much stored at once.

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.

• Ashish Pawar: Any Idea how to configure? is it by means configurations or java code ?
• Adam: First hit on google. It's a standard command-line feature for all JVMs (e.g. "-Xms"). But if you're using an IDE, your IDE will have a setting for this. If you're using an unusual JVM, it will have a custom setting for this. You need to read your JVM docs.

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.