0

私のアルゴリズムは、数値 0...n の順列を生成します。ここで、n は 1 から 9 までの任意の数値です。1 から 8 までの数値に対しては完全に機能します。ただし、9 で実行すると、しばらく実行されます。その後、突然プロセスを中止して終了します...エラーメッセージなどはありません! 私はかなり長い間Javaでコーディングしてきましたが、このエラーを経験したことはありません.

私のアルゴリズム:-

package utils;

import java.util.ArrayList;

class Lexicography {

    static ArrayList<Long> perms = new ArrayList<Long>();

    public static void main(String[] args){
        long time = System.currentTimeMillis();
        getPermutations(Integer.valueOf(args[0]));

        System.out.println("\nSize:-"+perms.size()+"\nTime:-"+(System.currentTimeMillis()-time));
        //This println is never printed... java aborts before that
    }

    public static ArrayList<Long> getPermutations(int num){
        int[] n = new int[num+1];
        for(int i=0; i<=num; i++) n[i]=i;
        perms.add(getLong(n));
        for(int i=num; i>=0; i--) permutate(n[i],n);
        return perms;
    }

    private static void permutate(int k, int[] n){
        if(k>n.length) return;
        int p=0;
        for(int i:n){ if(i==k) break; p++;}

        for(int i=0; i<n.length; i++){
            if(i==p || n[i]<k) continue;
            n=swap(p,i,n);
            perms.add(getLong(n));
            System.out.println("i:"+(i+1)+" k:"+k+"    n:"+getLong(n));//this prints all permutations till the last one and then poof!

            for(int j=k-1; j>=0; j--) permutate(j,n);
            n=swap(p,i,n);
        }
    }

    private static int[] swap(int i, int f, int[] a){
        int t=a[f];
        a[f]=a[i]; a[i]=t;
        return a;
    }

    private static long getLong(int[] n){
        long ten=1, num=0;
        for(int i=n.length-1; i>=0; i--){
            num+=n[i]*ten; ten*=10;
        }
        return num;
    }

}

print ステートメントがない場合、これは 8 までの数値に対してかなり高速に実行されます (8 の場合、280 ミリ秒未満で実行されます)。しかし、9の場合、最後の順列を印刷した後、突然停止します。誰か助けてくれませんか？ありがとうございました！

4

2 に答える 2

1

問題はあなたのコードではなく、System.outあなたが与えているデータの量を妥当な時間内に表示できないため、ヒストリックフィットをスローします。あなたのアプリケーションを実行しようとしたとき、6 分経ってもまだ実行されていたので、キャンセルし、print ステートメントをコメントアウトして、再度実行しました。(私のコンパイラによると) 出力に 2 秒かかりました。

Size:-3628800
Time:-962

そこで、代わりにデータをファイルに出力するようにコードを変更して再度実行したところ、実行に 4 秒かかり、出力の 83.1 MB の優れたテキスト ファイルが作成されました。これが私が使用したコードです（ただし、静的なものを使用しないように変更します）：

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;

class Lexicography
{
    static ArrayList<Long> perms = new ArrayList<>();
    private static BufferedWriter out;

    public static void main(String[] args) throws IOException
    {
        File outputFile = new File("output.txt");
        if(!outputFile.exists())
        {
            outputFile.createNewFile();
        }
        out = new BufferedWriter(new FileWriter(outputFile.getAbsolutePath()));
        long time = System.currentTimeMillis();
        getPermutations(Integer.valueOf("9"));
        System.out.println("\nSize:-" + perms.size() + "\nTime:-" + (System.currentTimeMillis() - time));
        out.close();
    }

    public static ArrayList<Long> getPermutations(int num) throws IOException
    {
        int[] n = new int[num + 1];
        for(int i = 0; i <= num; i++)
        {
            n[i] = i;
        }
        perms.add(getLong(n));
        for(int i = num; i >= 0; i--)
        {
            permutate(n[i], n);
        }
        return perms;
    }

    private static void permutate(int k, int[] n) throws IOException
    {
        if(k > n.length)
        {
            return;
        }
        int p = 0;
        for(int i : n)
        {
            if(i == k)
            {
                break;
            }
            p++;
        }

        for(int i = 0; i < n.length; i++)
        {
            if(i == p || n[i] < k)
            {
                continue;
            }
            n = swap(p, i, n);
            perms.add(getLong(n));
            out.write("i:" + (i + 1) + " k:" + k + "    n:" + getLong(n) + "\n");
            for(int j = k - 1; j >= 0; j--)
            {
                permutate(j, n);
            }
            n = swap(p, i, n);
        }
    }

    private static int[] swap(int i, int f, int[] a)
    {
        int t = a[f];
        a[f] = a[i];
        a[i] = t;
        return a;
    }

    private static long getLong(int[] n)
    {
        long ten = 1, num = 0;
        for(int i = n.length - 1; i >= 0; i--)
        {
            num += n[i] * ten;
            ten *= 10;
        }
        return num;
    }
}
于 2012-12-26T11:22:24.903 に答える
1

リソースが制限された JVM を使用していて、メモリ量の制限に非常に近づいていると思われます。印刷せずに実行してみますが、-verbosegc 作成するList<Long>とメモリの割り当てが消費されますが、十分な空きメモリがある場合にのみ問題ありません。

ところで、-負の数のように見える可能性があるため、正の数の前に a を付けて印刷しません。私のマシンで実行すると、（なしで-）表示されます

Size: 3628800
Time: 18645

印刷なし

Size: 3628800
Time: 1420

と-mx128m

Size: 3628800
Time: 1894

-mx100m投げるのに非常に長い時間がかかります

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
at java.lang.Long.valueOf(Long.java:577)
at Lexicography.permutate(Lexicography.java:31)
at Lexicography.permutate(Lexicography.java:34)
at Lexicography.permutate(Lexicography.java:34)
at Lexicography.permutate(Lexicography.java:34)
at Lexicography.permutate(Lexicography.java:34)
at Lexicography.permutate(Lexicography.java:34)
at Lexicography.getPermutations(Lexicography.java:19)
at Lexicography.main(Lexicography.java:9)

これを効率的に実行するには、少なくとも 128 MB のヒープ サイズが必要です。

于 2012-12-26T11:33:04.177 に答える