Mfcttrf

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

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.

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.

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.