4

我正在尝试创建一个邻接列表来存储图形。该实现在存储 100,000 条记录时运行良好。但是，当我尝试存储大约 100 万条记录时，我遇到了 OutofMemory 错误：

线程“主”java.lang.OutOfMemoryError 中的异常：java.io.BufferedReader 的 java.lang.String.(String.java:215) 处的 java.util.Arrays.copyOfRange(Arrays.java:3209) 处的 Java 堆空间.readLine(BufferedReader.java:331) 在 java.io.BufferedReader.readLine(BufferedReader.java:362) 在 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如果您使用 a代替，它会更容易和更有效。new Scanner(new File(inputFilename))和next(), 和nextInt()是你所需要的。

int为每个名称分配一个唯一的（提示：） Map<String, Integer>，并存储更小的名称int。

于 2010-04-19T04:02:51.493 回答
0

谢谢回答我的问题。是的，你猜对了，代码是关于什么的。

我认为是的，使用字符串到整数的映射将为我节省一些空间请求用于邻接列表。从这个意义上说，可以消除上述错误。

但是，我使用了 java -jar -Xmx1024M。这提供了一种使用更多堆内存运行程序的方法，并且由于它允许在给定的问题中使用它，因此这不是我提交失败的原因。

尽管我不确定，但性能可能是机器人失败的原因之一。

关于您的解决方案，

如果我创建一个 Map ，然后将数字存储在邻接列表中，它将为我节省一些空间，但它也会在我每次需要在我的 bfs/dfs 遍历期间访问一个节点时添加一个额外的查找。这让我很困扰。你是说我根本不应该创建邻接列表吗？我是否理解您要正确说的内容。

谢谢。

于 2010-04-21T21:38:06.200 回答