Java Memory limit exceeded на олимпиадном программировании?

Question

[fh]

Решая задачу Преобразование последовательности, столкнулся с превышением памяти на 23 тесте. Решал двумя способами:

1 способ (Используя словарь, прошёл 23 теста, 23 мб)

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class SequenceTransform {
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(new File("input.txt"));
        PrintWriter pw = new PrintWriter(new File("output.txt"));
        List<Integer> seq = new ArrayList<>(); // сама последовательность
        Map<Integer, Integer> eachCount = new HashMap<>(); // словарь ( число - кол-во)
        int n = scan.nextInt(); // кол-во чисел
        int num;
        for(int i = 0; i < n; i++) {
            num = scan.nextInt();
            seq.add(num);
            if (!eachCount.containsKey(num)){ // добавление в словарь числа, либо увеличение его кол-ва
                eachCount.put(num,1);
            } else {
                eachCount.put(num, eachCount.get(num) + 1);
            }
        }
        // сортировка словаря и получение самого частого числа
        List<Map.Entry<Integer, Integer>> sorted = new ArrayList<>(eachCount.entrySet()); 
 
        int max = sorted.stream().sorted((a,b) -> {
            if (a.getValue() != b.getValue())
                return b.getValue() - a.getValue();
            else
                return a.getKey() - b.getKey();
        }).limit(1).collect(Collectors.toList()).get(0).getKey();
        int max_count = eachCount.get(max);
        // удаление(как и сказано в условии) max'a и вставка в конец
        seq.removeIf(a -> a == max);
        for (int i = 0; i < max_count; i++)
            seq.add(max);
 
        seq.forEach(pw::println);
        pw.close();
    }
}

2 способ (Используя массив для подсчета кол-ва, прошел 13 тестов, 22 мб)

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;

public class SequenceTransform {
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(new File("input.txt"));
        PrintWriter pw = new PrintWriter(new File("output.txt"));
        int N = scan.nextInt();
        List<Integer> seq = new ArrayList<>();
        final int million = 1000000;
        int[] count = new int[million * 2 + 1]; // два миллиона эл-ов, так как в условии сказано, что числа в диапазоне [-10^6; 10^6]
        for (int i = 0; i < N; i++){
            int num = scan.nextInt();
            seq.add(num);
            count[million + num]+=1;
        }
        int[] max = {0,0};
        for (int i = 0; i < count.length; i++){
            if (max[1] < count[i]){
                max[0] = i;
                max[1] = count[i];
            }
        }
        int max_num = max[0] - million;
        seq.removeIf(a -> a == max_num);
        for (int i = 0; i < max[1]; i++)
            seq.add(max_num);
        seq.forEach(pw::println);
        pw.close();
    }
}

Текущая попытка( 16 мб, 23 теста)

import java.util.*;
import java.io.*;

public class SequenceTransform {
    static int nexInt(Reader reader) throws  IOException{
        String c = Character.toString( (char) reader.read());
        String Int = "";
        while (!c.equals(" ") && !c.equals("\n") && !c.equals("\uFFFF")){
            if (!c.equals("\r")) Int = Int.concat(c);
            c = Character.toString( (char) reader.read());
        }
        return Integer.valueOf(Int);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader (new FileReader("input.txt"));
        PrintWriter pw = new PrintWriter(new File("output.txt"));
        Map<Integer, Integer> eachCount = new HashMap<>();
        int n = nexInt(br);
        int[] seq = new int[n];
        for(int i = 0; i < n; i++) {
            int num = nexInt(br);
            seq[i] = (num);
            if (!eachCount.containsKey(num)){
                eachCount.put(num,1);
            } else {
                eachCount.put(num, eachCount.get(num) + 1);
            }
        }
        List<Map.Entry<Integer, Integer>> sorted = new ArrayList<>(eachCount.entrySet());
        Map.Entry<Integer, Integer> max = sorted.get(0);
        Map.Entry<Integer, Integer> el;
        for (int i = 0; i < sorted.size(); i++){
            el = sorted.get(i);
            if (max.getValue().compareTo(el.getValue()) <= 0){
                if (max.getValue().compareTo(el.getValue()) != 0)
                    max = el;
                else if (max.getKey().compareTo(el.getKey()) > 0)
                        max = el;
            }
        }
        int maxkey = max.getKey();
        int maxvalue = max.getValue();
        int[] ans = new int[n];
        int j = 0;
        for (int i = 0; i < n; i++){ // Новый массив, в котором самый частый элемент находится в конце.
            if (maxkey != seq[i]){
                ans[j] = seq[i];
                j++;
            }
        }
        for (int i = n - maxvalue; i < n ; i++){
            ans[i] = maxkey;
        }
        for (int x : ans)
            pw.print(x + " ");

        pw.close();
    }
}

Возникли вопросы:
Как сервер подсчитывает память?
Как сократить расходы памяти, потому что первое решение не особо затратное?

Comments

[Samarkand]

А если в последовательности все числа кроме одного встречаются одинаковое количество раз? Что тогда?

[fh]

Samarkand, выбирается наименьшее из них(если кол-во каждого из этих чисел больше кол-ва этого одного). Но дело не в этом, у меня нет wrong answer ошибок.

[Samarkand]

И в первом, и во втором решении Вы храните полный список чисел. Это неправильные решения. Думайте дальше. Либо могу подсказать, но не бесплатно :)
Какой уровень? Это школа, институт?

[fh]

Samarkand, уровень чего, заданий? уровень новичок, а я - школьник

Answer 1

[StainlessDespair]

В первом способе слишком много абстракций. Когда речь заходит о критической экономии памяти нужно сразу забывать про существовании Stream API, стараться не использовать autoboxing и пытаться эффективней использовать ресурсы. На то они и олимпиадные задачки, чтобы писать все сортировки руками вместо однострочных стримов и пр.

Что можно сделать:

• закрывать сканер после чтения (не закрыв он так и будет висеть у тебя в памяти, которой может не хватить допустим в середине алгоритма)
  
• открывать writer в самом конце (тоже самое что и со сканером, тем более что он тебе абсолютно не нужен в начале выполнения)
  
• заменить мапу на массив, убрать использование объекта Integer (со списком тоже желательно, но боттлнек твоего первого способа именно её использование, поэтому если заменишь правильно не сломав логику, то должно хватить.)
  
• не использовать стримы
  

По поводу подсчёта памяти сервером скорее всего просто запускают виртуалку с -Xmx16m параметром и реагируют на OutOfMemoryError, но это не точно.

ps Ты не можешь сравнивать Integer таким образом a.getValue() != b.getValue(). Integer суть объект, нужно использовать equals. А ещё в задании сказано разделять числа в output пробелами, а не переходами на новую строку, но это так, к слову.

Comments

[fh]

Поставив BufferReader вместо Scanner'a, сократил расход памяти до 18 мб(было 23 мб). Также избавился от стрима, заменив сортировку просто на поиск макс значения в sorted(не изменило потребление памяти). Printwriter перед выводом тоже ничего не поменял. Думаю заменить мапу на двумерный лист(не представляю на что еще можно заменить словарь), не уверен, что это будет сильно эффективнее обычной мапы. От Integer'a избавиться не получится никак, так как словарь(или что-то на подобии) невозможно реализовать, используя только фиксированные массивы(а для динамичных(пример List) примитивный тип int использовать нельзя).

[StainlessDespair]

Одномерный массив и есть своеобразный словарь где индекс - ключ. То что он у тебя фиксированный и будет на 2ккк размера суть не страшно. В этом плане можешь посмотреть на свой же второй способ. По поводу не сильно эффективней, я ещё когда давал ответ на коленке собирал твой первый способ и заменив мапу и объекты на массив с примитивами, даже без дополнительных манипуляций с убиранием стримов, решил проблему OOME (ошибка падает на строчке с new ArrayList<>(eachCount.entrySet()), но конечно смотри сам.

Answer 2

[Динар Зарипов]

Scanner убери и юзай BufferedReader