排序期间的 Java OutOfMemory

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

Answer 1

请注意，在列表中创建通过Collections.nCopies(Integer.MAX_VALUE - 1, 0)使用一个微小的内存量是不变的。文档说“返回一个由指定对象的 n 个副本组成的不可变列表。新分配的数据对象很小（它包含对数据对象的单个引用）”。如果您查看实现，您会发现它完全符合人们对该描述的期望。它返回一个假装很大的List对象，只保存一次大小和元素，并在询问任何索引时返回该元素。

Collections.sort那么问题有两个：

• 该列表不能是不可变的，但该列表是。顺便说一句，这也解释UnsupportedOperationException了您尝试时得到的结果set()。
• 出于性能原因，它“获取一个包含此列表中所有元素的数组，对数组进行排序，[并写回列表]”。所以在这一点上，这个小小的假装列表确实会被炸毁并导致你的记忆问题。

所以你需要找到一些其他的排序方式。一个就地工作并且不为此输入交换任何内容（这是正确的，因为列表已经排序）。例如，您可以使用冒泡排序，它在此输入上花费 O(n) 时间和 O(1) 空间，并且不会在此处尝试任何交换。

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