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

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 に答える
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 に答える
1

メモリ消費を減らすために、セットをビットフィールドとして保存できます。たとえば、要素を含むセットは次の3, 9, 14ように表され10110000000000000000ます。したがって、サブセットごとに1つだけ必要です。int

于 2012-11-27T08:37:24.387 に答える