4

グラフを格納する隣接リストを作成しようとしています。100,000 レコードを格納している間、実装は正常に動作します。ただし、約 100 万件のレコードを保存しようとすると、OutofMemory エラーが発生しました。

スレッド「メイン」での例外 java.lang.OutOfMemoryError: java.util.Arrays.copyOfRange(Arrays.java:3209) の Java ヒープ領域 (java.lang.String.(String.java:215) の java.io.BufferedReader) .readLine(BufferedReader.java:331) at java.io.BufferedReader.readLine(BufferedReader.java:362) at liarliar.main(liarliar.java:39)

以下は私の実装です

HashMap<String,ArrayList<String>> adj = new HashMap<String,ArrayList<String>>(num);


        while ((str = in.readLine()) != null)
        {

            StringTokenizer Tok = new StringTokenizer(str);
            name = (String) Tok.nextElement();
            cnt = Integer.valueOf(Tok.nextToken());
            ArrayList<String> templist = new ArrayList<String>(cnt);

            while(cnt>0)
             {
                    templist.add(in.readLine());
                    cnt--;
             }
            adj.put(name,templist);

        } //done creating a adjacency list

隣接リストを実装するためのより良い方法があるかどうか疑問に思っています。また、最初からノードの数を知っており、将来、ノードにアクセスするときにリストをフラット化します。助言がありますか ？

ありがとう

4

2 に答える 2

1

liarliar問題の名前（ ）と入力の正確な性質の両方を認識しているので、ここでは不公平な利点があるようです。

これOutOfMemoryErrorは仕様によるものです。グラフの隣接情報全体をメモリに保存しない、より優れたアルゴリズムを見つける必要があります。

アルゴリズムに関する洞察をあまり与えないようにしますが、この段階でプログラムする必要がある以上に、座って考える必要があると言えます。たぶん、アルゴリズムとデータ構造に関する良い本を読んでください。

あなたが今していることは、あなたが実際に入力ファイルからの文字列HashMap<String,ArrayList<String>>をあなたのに不必要に保存しているということです。問題の性質を考えると、これは非常にスペース効率が悪いです。

java.util.Scanner代わりに使用すると、はるかに簡単で効率的です。new Scanner(new File(inputFilename))とnext()、そしてnextInt()あなたが必要とするすべてです。

それぞれの名前に一意の名前を割り当てint（ヒント:) Map<String, Integer>、代わりにはるかに小さい名前を保存しintます。

于 2010-04-19T04:02:51.493 に答える
0

私の質問に答えてくれてありがとう。はい、あなたはそれを正しく推測しました、コードが何であるか。

はい、文字列から整数へのマッピングを使用すると、隣接リストに必要なスペースを節約できます。その意味で、上記のエラーは削除できます。

ただし、java -jar -Xmx1024M を使用しました。これにより、より多くのヒープメモリでプログラムを実行する方法が提供されます。また、特定の問題でそれを使用することが許可されているため、提出が失敗する理由にはなりません。

よくわかりませんが、パフォーマンスがボットの失敗の理由の 1 つになる可能性があります。

あなたの解決策に関して、

Map を作成し、隣接リストに番号を保存すると、スペースが節約されますが、bfs/dfs トラバーサル中にノードにアクセスする必要があるたびに、余分なルックアップが追加されます。それは私を悩ませます。隣接リストをまったく作成すべきではないと言っているのですか？あなたが言おうとしていることが正しく理解できましたか。

ありがとう。

于 2010-04-21T21:38:06.200 に答える