排序期间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)
    }

使用内存错误而不是我自己的无法构建金字塔例外（排序后将以另一种方法抛出）。我知道这是因为蒂姆索特在收集.sort（）方法。我试图使用堆排序，但我甚至无法交换元素，因为我的输入列表被初始化为 Arrays.asList（），当我使用 set（） 方法时，我得到了不受支持的操作例外。然后我试图将我的列表转换为常见的数组列表

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

但我再次出现OutOfMemoryError错误。不允许编辑测试。我不知道该怎么处理这个问题。我正在使用Java8和IntelliJIdea SDK

Answer 1

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

我认为这个测试写得很糟糕——不应该试图创建这么大的< code >列表。

Answer 2

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

< code>Collections.sort的问题有两个方面:

< li >该列表不能是不可变的，但该列表是可变的。该btw还解释了当您尝试< code>set()时出现的< code > UnsupportedOperationException 。 < li >出于性能原因，它“获取包含该列表中所有元素的数组，对该数组进行排序，[并写回该列表]”。所以在这一点上，这个小小的假装列表确实被放大了，导致了你的记忆问题。

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

顺便说一句，关于“因为蒂姆索特”而得到的记忆问题：蒂姆索特真的不怪。您甚至无法进入 Timsort 部分，因为正是准备复制到数组导致了内存问题。此外，Timsort很聪明，会检测到数据已经排序，然后什么都不做。因此，如果您确实到达了 Timsort 部分，或者您可以直接将其应用于列表，Timsort 就不会造成问题。