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

Answer 1

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

我认为这个测试的编写方式非常糟糕 - 永远不要尝试创建如此庞大的 List。

Answer 2

请注意，Collections.nCopies(Integer.MAX_VALUE - 1, 0) 创建的列表使用了极小的内存量，并且 不可变 。 The documentation says "Returns an immutable list consisting of n copies of the specified object. The newly allocated data object is tiny (it contains a single reference to the data object)". And if you look at the implementation，您会发现它完全符合人们对该描述的期望。它returns一个List对象，只是假装很大，只保存大小和元素一次并返回当询问任何索引时该元素。

Collections.sort 的问题有两个方面：

列表不能是不可变的，但那个列表是。顺便说一句，这也解释了当您尝试 set().

UnsupportedOperationException

出于性能原因，"obtains an array containing all elements in this list, sorts the array, [and writes back to the list]"。所以在这一点上，微小的假装列表确实被炸毁并导致你的记忆问题。

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

btw，关于获取内存的问题"because of TimSort"：Timsort 真的不能怪。您甚至没有接触到 Timsort 部分，因为它是导致内存问题的准备性复制到数组。此外，Timsort 很聪明，会检测到数据已经排序，然后不会做任何事情。所以如果你真的接触到 Timsort 部分，或者如果你可以直接将它应用到列表中，Timsort 不会造成问题。

Java 排序期间内存不足

Java OutOfMemory during sorting

java

sorting

exception

out-of-memory