7

是否有一个已经实现的数据结构，我可以使用它来分配一个对象（在我的例子中是一个边缘），一个整数？我正在从文件中读取图形，10 百万个顶点，60 百万条边，我使用地图（cost.put(e,cost)）为每个边分配一个成本。

我以这种方式创建成本图：

costs = new HashMap<Edge,Integer>();

它给出的例外是：

java.lang.OutOfMemoryError: Java heap space
    at java.util.HashMap.resize(Unknown Source)
    at java.util.HashMap.addEntry(Unknown Source)
    at java.util.HashMap.put(Unknown Source)
4

8 回答 8

6

HashMap是基本的正确数据结构Map。您遇到的问题是没有指示 JVM 保留足够的空间来将文件内容保存在内存中。-Xmx使用标志启动 JVM 。例如-Xmx1G参数将允许它使用 1 GB 的内存。

于 2012-10-31T09:17:28.410 回答
6

你有 6e7 边。一个普通的对象需要 24 个字节（64 位 HotSpot），所以那里有 1.44e9 个字节（1.5 GB）。现在您介绍可以想象的最有效的地图，仅添加 6e7 引用和 6e7Integer对象。这是 refs 的另外 2.4e8 字节和Integers 的 1.44e9 字节：另外 1.5 GB，现在总计 3 GB - 这是您的问题的理论下限（模缓存，见下文）。

基于此，我建议您Edge使用另一个int字段扩展您的课程。这将大大减少您的内存占用。

但是，如果这不是一个选项，并且：

  • 你所有的整数很少超过两位数，
  • 你小心不要使用new Integer，但是Integer.valueOf，自动装箱等，
  • 你使用 Java 7，

您将自动受益于内置的小整数缓存。如果整数采用更大范围的值，但仍然有很多重复，则强烈建议使用自定义缓存。

于 2012-10-31T09:24:57.093 回答
3

除了更改 jvms 内存设置之外，您还可以HashMap使用初始容量和负载平衡来调整内存管理。

Javadoc 摘录：

HashMap 的实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是哈希表创建时的容量。负载因子是哈希表在其容量自动增加之前允许达到的程度的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，对哈希表进行重新哈希（即重建内部数据结构），使哈希表具有大约两倍的桶数。

于 2012-10-31T09:20:48.983 回答
3

而不是创建一个HashMap

costs = new HashMap<Edge,Integer>();

您可以将成本存储在Edge对象中。

class Edge
{
    Vertex a;
    Vertex b;
    int cost;
}

这样，您可以在系统中节省一些内存。

于 2012-10-31T09:21:23.257 回答
2

回到最初的问题：你有边，有成本。由于您的图是稀疏的，为什么不使用稀疏矩阵？也许对象到整数的映射不是您真正需要和想要的。您可以查看 apache.commons.math，我认为它们具有稀疏矩阵。此外，您需要考虑如何访问算法中的成本，以选择适当的稀疏格式（基于列的运行长度编码/基于行的 rle 或其他）。或者你不在乎，并使用任何东西，但是你应该在你的算法开始时转换东西。

于 2012-10-31T09:22:59.737 回答
1

您确实意识到这需要大量RAM，对吗？尝试增加堆大小，你会没事的......

并回答您最初的问题：是的，这就是Map的用途...

于 2012-10-31T09:17:00.157 回答
1

您必须为每个项目指定项目需要多少堆空间

我认为您可以按照以下步骤操作：

Right mouse click - Run As - Run Configuration - Arguments - Vm Arguments, then add this -Xmx2048m
于 2012-10-31T09:18:59.300 回答
1

也许您正在寻找的是TObjectIntHashMap 这与它类似，HashMap<Edge, Integer>只是它将 存储int为可能为您节省一些内存的原语。当集合更大时，这个集合也可以稍微快一点（因为它更适合缓存）

TObjectIntHashMap<Edge> costs = new TObjectIntHashMap<Edge>();

costs.put(e, cost); // cost is stored as a primitive not its wrapper object.
于 2012-10-31T09:46:10.433 回答