Java排序时出现内存溢出问题

Question

我有一个关于使用数字列表构建金字塔的任务，但是其中一个测试出现了问题。在我的任务中，我需要对列表进行排序。我使用Collections.sort()：

Collections.sort(inputNumbers, (o1, o2) -> {
            if (o1 != null && o2 != null) {
                return o1.compareTo(o2);
            } else {
                throw new CannotBuildPyramidException("Unable to build a pyramid");
            }
        });

但是这个测试失败了。

@Test(expected = CannotBuildPyramidException.class)
    public void buildPyramid8() {
        // given
            List<Integer> input = Collections.nCopies(Integer.MAX_VALUE - 1, 0);

        // run
        int[][] pyramid = pyramidBuilder.buildPyramid(input);

        // assert (exception)
    }

使用OutOfMemoryError替代我自己的CannotBuildPyramidException(在排序后的另一个方法中抛出)。我明白这是由于Collections.sort()方法中的TimSort。我尝试使用HeapSort，但是我甚至无法交换元素，因为我的输入列表是通过Arrays.asList()初始化的，当我使用set()方法时会得到UnsupportedOperationException。然后我尝试将我的列表转换为普通的ArrayList。

ArrayList<Integer> list = new ArrayList<>(inputNumbers);

但我再次遇到了OutOfMemoryError错误。无法编辑测试。 我不知道该如何处理这个问题。 我正在使用Java8和IntelliJIdea SDK。

- PashaMinigun

---

也许可以捕获OutOfMemoryError并抛出自己的异常？ - Adder

@Adder，捕获Error是一种不好的Java编程实践。当JVM无法继续处理程序执行时，会抛出Error，根据定义，它无法被正确处理。 - Greg Witczak

分配更多的堆空间？ - The Head Rush

我可以建议这个测试的重点可能是检查列表是否被原地排序，而没有被复制？你能问问你的老师关于这个测试吗？ - kutschkem

@kutschkem 这可能是个问题，对吧。但如果是真的，那么...我们就歧视了那些内存少于16 GB的学生？可以用不同的方式解决，例如通过强制学生使用 -XMx=64m 运行 JVM 并将列表大小减小到1000万个元素，或类似的方法。 - Greg Witczak

Answer 1

请注意，由 Collections.nCopies(Integer.MAX_VALUE - 1, 0) 创建的列表使用了极小的内存并且是不可变的。 文档 中写道："返回由指定对象的 n 个副本组成的不可变列表。新分配的数据对象很小（它只包含对数据对象的单个引用）"。如果您查看实现，您会发现它确实符合该描述。它返回一个 List 对象，它只是假装很大，只保留大小和元素一次，在询问任何索引时都返回该元素。 Collections.sort 的问题有两个：

• 列表不能是不可变的，但该列表是不可变的。这也解释了当您尝试 set() 时出现的 UnsupportedOperationException。
• 出于性能原因，它"获取包含此列表中所有元素的数组，对数组进行排序，[并写回到列表中]"。因此，在这一点上，虚拟的小列表会被扩大并导致内存问题。

所以您需要找到其他方法进行排序。其中一种方法是使用冒泡排序，在此输入上需要 O(n) 的时间和 O(1) 的空间，并且不尝试任何交换。

顺便说一下，关于因 TimSort 而出现内存问题的问题："TimSort 不是罪魁祸首。你甚至没有进入 TimSort 部分，因为它是准备复制到数组导致内存问题。此外，Timsort 很聪明，会检测到数据已经排序，然后什么也不做。因此，如果您实际上进入了 Timsort 部分，或者如果您可以直接将其应用于列表，则 Timsort 不会造成问题。"

- Kelly Bundy

Answer 2

这个列表太大了！Collections.nCopies(Integer.MAX_VALUE - 1, 0);会给我们一个由2^31-1（2147483647）个元素组成的列表，每个元素在内存中占用约4个字节（这是Integer的"简化"大小）。如果我们将它们相乘，就需要大约8.59 GB的内存来存储所有这些数字。你确定你有足够的内存来存储它吗？

我认为这个测试写得非常糟糕 - 永远不应该试图创建如此巨大的List。

- Greg Witczak

---

不，我没有足够的内存。 - PashaMinigun

@PashaMinigun 我们无法确定你的老师会同意什么。我建议在作业到期之前联系你的老师，询问他关于这个问题的看法。 - Jordan

如果您确定需要使用这么多数据，那么也许您需要增加Java运行时的最大堆大小？您可以使用参数“-Xmx”来实现。 - user27158

嗯，如果假设一个列表可以放入内存，但是不能有两个，那么我认为测试有些意义。因此，确保一切都在原地完成。在我看来，这是太多的假设了，但也许这就是测试的目的吧？ - kutschkem

我认为你对大小的理解是错误的。文档中写道：“返回一个由指定对象的 n 个副本组成的不可变列表。新分配的数据对象非常小（它只包含对数据对象的单个引用）。” - Kelly Bundy