how to solve Java heap space Exception for ArrayList Size?

Question

When i run the below program which displays subsets of a given array, where array size is <=19 , it works fine. But if array size >19 it throws Java Heap Space Exception. How to overcome this problem in order to get subsets where array size > 19?

import java.lang.*;
import java.util.*;
class def
{
    static List<List<Integer>> subset(int ele,List<List<Integer>>  w)
    {
        if(w.size()==0)
        {
            List<Integer> temp=new ArrayList<Integer>();
            temp.add(ele);
            w.add(temp);
        }
        else
        {
            int i,len=w.size();
            for(i=0;i<len;i++)
            {
                List<Integer> temp=new ArrayList<Integer>();
                for(Integer agh:w.get(i))
                {
                    temp.add(agh);
                }
                temp.add(ele);
                w.add(temp);
            }
            List<Integer> ghi=new ArrayList<Integer>();
            ghi.add(ele);
            w.add(ghi);
        }
        return w;
    }
    static void sub(int set[])
    {
        List<List<Integer>> ints = new ArrayList<List<Integer>>();
        int len=set.length,i;
        for(i=0;i<len;i++)
        {
            ints=subset(set[i],ints);
        }
        int count=0;
        for(List<Integer> temp:ints)
        {
            System.out.println("SET---"+count++);
            for(Integer agh:temp)
            {
                System.out.println(agh);
            }
        }

    }
    public static void main(String args[])
    {
        int a[]={3,4,9,14,15,19,28,37,47,50,54,56,59,61,70,73,78,81,92,95,97,99};
        sub(a); 
    }
}

Here is the exception: C:\Program Files (x86)\Java\jdk1.6.0_07\bin>javac def.java

C:\Program Files (x86)\Java\jdk1.6.0_07\bin>java def
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:2760)
    at java.util.Arrays.copyOf(Arrays.java:2734)
    at java.util.ArrayList.ensureCapacity(ArrayList.java:167)
    at java.util.ArrayList.add(ArrayList.java:351)
    at def.subset(def.java:22)
    at def.sub(def.java:39)
    at def.main(def.java:55)

But according to my knowledge, Arrays don't have dynamic memory allocation capability where as list can do that. — vij, Nov 27 '12 at 08:28
One solution is to not store all the subsets at once, but rather generate and process them one at a time. Check out all the answers to http://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java — NPE, Nov 27 '12 at 08:38

score 2 · Answer 1 · answered Nov 27 '12 at 08:34

It seems that you are making too much instance of ArrayList. You can increase the heap size. but I think you can make a small modification in your code

else
    {
        int i,len=w.size();
        List<Integer> temp=new ArrayList<Integer>();   ///reuse this arraylist
        for(i=0;i<len;i++)
        {

            for(Integer agh:w.get(i))
            {
                temp.add(agh);
            }
            temp.add(ele);
            w.add(temp);
            temp.clear();
        }
        List<Integer> ghi=new ArrayList<Integer>();
        ghi.add(ele);
        w.add(ghi);
    }
    return w;

Though this may not solve your problem fully. But obviously it will help the garbage collector to take some rest. :D

score 2 · Answer 2 · answered Nov 27 '12 at 08:36

2

The reason you are getting a heap error is because you are creating billions of lists. Do not create sublists just display them.

public static void sub(int[] input){
    sub(new int[0],input);
}

public static void sub(int[] current, int[] remaining){
    System.out.println(Arrays.toString(current));
    int[] newCurrent = Arrays.copyOf(current, current.length+1);

    for(int i = 0;i < remaining.length;i++){
        newCurrent[newCurrent.length-1] = remaining[i];
        sub(newCurrent , Arrays.copyOfRange(remaining, i + 1, remaining.length));
    }

}

otherwise you will need a smarter data structer than a list of lists.

answered Nov 27 '12 at 08:36

BevynQ

8,089
4
25
37

In the code snippet i've posted above, i am using the previous sub set list to calculate new subset list (even for displaying also you need that). – vij Nov 27 '12 at 08:40
No you don't need to. if you get your recursion method right all you have to do is provide a prefix and the set of remaining numbers. The prefix will always be at most n and the remainder set will always be at most n. there is still an overhead or arrays on the stack which could be reduced. – BevynQ Nov 27 '12 at 08:52

score 1 · Answer 3 · answered Nov 27 '12 at 08:37

1

To reduce memory consumption you can store sets as bit fields, for example set with elements 3, 9, 14 will be represented as 10110000000000000000 - so for each subset you will need only one int

answered Nov 27 '12 at 08:37

ice

777
1
4
19

how to solve Java heap space Exception for ArrayList Size?

3 Answers3