3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ How big of an array are you actually aiming for? Multidimensional with Integer.MAX_VALUE each dimension would be huge \$\endgroup\$ – D. Jurcau Oct 5 '19 at 16:14
  • \$\begingroup\$ Yes Im trying create array of size larger than Integer.MAX \$\endgroup\$ – Aashish Pawar Oct 5 '19 at 16:54
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Carcigenicate Oct 6 '19 at 0:13
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Any Idea how to configure? is it by means configurations or java code ? \$\endgroup\$ – Aashish Pawar Oct 6 '19 at 3:33
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Adam Oct 6 '19 at 18:39
6
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.