邻接表创建，内存不足错误。

Question

我正在尝试创建一个邻接表来存储图形。在存储100,000条记录时，实现工作正常。然而，当我尝试存储大约1百万条记录时，我遇到了内存溢出错误：

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.util.Arrays.copyOfRange(Arrays.java:3209) at java.lang.String.(String.java:215) at 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

我在想，是否有更好的方法来实现邻接表。此外，我知道节点数目在一开始就确定了，并且在访问节点时我会将列表展开。你有什么建议吗？

谢谢！

- codeObserver

Answer 1

我似乎有不公平的优势，因为我认识这个问题的名称（liarliar）和输入的确切性质。

我可以告诉你，这个OutOfMemoryError是设计上的。你需要找到一个更好的算法，不要将整个图的邻接信息存储在内存中。

我会克制给出太多算法洞察力，但我可以告诉你，在这个阶段，你需要坐下来思考比编程更多。也许读一本好的算法和数据结构书会有所帮助。

---

你现在正在将输入文件中的字符串不必要地存储到你的HashMap<String,ArrayList<String>>中。考虑到问题的性质，这非常浪费空间。

如果你使用java.util.Scanner会更容易和高效。只需要使用new Scanner(new File(inputFilename))、next()和nextInt()即可。

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

- polygenelubricants

Answer 2

感谢您回答我的问题。是的，您猜对了代码的含义。

我认为使用字符串到整数的映射可以节省邻接表所需的空间。从这个意义上说，上述错误可以被解决。

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

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

关于您的解决方案，

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

谢谢。

- codeObserver

---

Map<String，Integer>查找是便宜的(O(1));除非已经证明是问题，否则不应该被打扰。过早优化是万恶之源。在这种情况下更是如此，因为你还没有发现一个_BIG_优化。你理解得对：你根本不需要创建邻接表。你可以用 O(V) 的空间解决这个问题。你可以在 O(V+E) 的时间内处理输入(这是最优的，因为这是输入的大小)，在读完输入后，你可以立即以 O(1) 的时间产生输出。 - polygenelubricants

另一种节省空间的方法是使用.intern()来代替Map<String,Integer>。输入中会有很多重复的名称，它们在内存中被多次冗余存储。如果只存储这些名称的.intern()，那么冗余副本将被垃圾回收。而且，如果您始终.intern()这些名称，就可以使用==和!=而不是equals()。了解字符串驻留的工作原理。虽然这只是一个小的时间优化，但真正重要的是上面评论中提到的那个。 - polygenelubricants

我知道这与测试二分图/图着色有关...但我仍在脑海中思考如何在创建了所有节点的Map（name，int）之后以O（1）的时间复杂度得出答案！Map（name，int）中的int可以根据距离而改变，所有偶数都归为一组，奇数则归为另一组。所有这些方法的问题是，它需要一个邻接表:(来确保以BFS或DFS格式跟踪图。否则，你会得到一个新节点不知道属于哪个组的节点..所以很难知道子节点将去哪些节点。 我可能漏掉了什么，我走在正确的轨道上吗？ - codeObserver