Java OutOfMemory во время сортировки - PullRequest
Новая
       4

Java OutOfMemory во время сортировки

6 голосов
/ 22 января 2020

У меня есть задача построить пирамиду, используя список чисел, но есть одна проблема с одним тестом. В моей задаче мне нужно отсортировать список. Я использую 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 (он будет брошен в другой метод после сортировки). Я понимаю, что это из-за TimSort в методе Collections.sort (). Я пытался использовать HeapSort, но я даже не мог поменять местами элементы, потому что мой список ввода был инициализирован как Arrays.asList (), и когда я использую метод set (), я получаю UnsupportedOperationException. Затем я попытался преобразовать мой список в обычный ArrayList 

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

, но я снова получил OutOfMemoryError. Не разрешено редактировать тесты. Я не знаю, что делать с этой проблемой. Я использую Java8 и IntelliJIdea SDK

Ответы [ 2 ]

7 голосов
/ 10 февраля 2020

Обратите внимание, что список, созданный Collections.nCopies(Integer.MAX_VALUE - 1, 0), использует крошечный объем памяти и является неизменным . Документация говорит "Возвращает неизменный список, состоящий из n копий указанного объекта. Недавно выделенный объект данных является крошечным (он содержит одну ссылку на объект данных)" . И если вы посмотрите на реализацию , вы увидите, что она делает именно то, что можно ожидать из этого описания. Он возвращает List объект, который только притворяется большим, содержит только размер и элемент один раз и возвращает этот элемент при запросе о любом индексе.

В этом случае проблема с Collections.sort имеет две стороны:

Так что вам нужно найти другой способ сортировки. Тот, который работает на месте и ничего не меняет для этого ввода (что правильно, так как список уже отсортирован). Например, вы можете использовать пузырьковую сортировку, которая занимает O (n) время и O (1) место на этом входе и не пытается здесь поменяться местами.

Кстати, о проблеме с памятью " из-за TimSort ": Timsort действительно не виноват. Вы даже не попадаете в часть Timsort, поскольку именно предварительное копирование в массив вызывает проблему с памятью. А кроме того, Тимсорт умен и обнаружит, что данные уже отсортированы, а затем ничего не сделает. Так что, если вы действительно добрались до части Timsort, или если бы вы могли напрямую применить ее к списку, Timsort не вызовет проблемы.

2 голосов
/ 22 января 2020

Этот список слишком велик! Collections.nCopies(Integer.MAX_VALUE - 1, 0); дает нам список из 2 ^ 31-1 элементов (2147483647), каждый из которых занимает около 4 байтов в памяти (это «упрощенный» размер Integer). Если мы умножим его, у нас будет около 8,59 ГБ памяти, необходимой для хранения всех этих чисел. Вы уверены, что у вас достаточно памяти для ее хранения?

Я считаю, что этот тест написан очень плохо - никогда не пытайтесь создать такой огромный List.

...