3

当我运行以下程序时，它显示给定数组的子集，其中数组大小为 <=19 ，它工作正常。但如果数组大小 >19，则会引发 Java 堆空间异常。如何克服这个问题以获得数组大小> 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); 
    }
}

这是一个例外：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)
4

3 回答 3

2

您收到堆错误的原因是您正在创建数十亿个列表。不要创建子列表，只是显示它们。

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));
    }

}

否则，您将需要一个比列表列表更智能的数据构造器。

于 2012-11-27T08:36:55.027 回答
2

看来您正在制作太多的 ArrayList 实例。您可以增加堆大小。但我认为您可以对代码进行一些小修改

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;

虽然这可能无法完全解决您的问题。但显然它会帮助垃圾收集器休息一下。:D

于 2012-11-27T08:34:39.783 回答
1

为了减少内存消耗，您可以将集合存储为位字段，例如带有元素的集合3, 9, 14将表示为10110000000000000000- 因此对于每个子集，您只需要一个int

于 2012-11-27T08:37:24.387 回答