Алгоритм фильтрации большой последовательности чисел

44. Отфильтровать большую последовательность чисел

Условие задачи:
Необходимо обработать последовательность чисел размером до 1 Гб и получить только значения больше 5.

Доступно 1.1 Гб памяти, поэтому нельзя загружать всю последовательность и результат целиком в память.

Спойлеры к решению

Подсказки

💡 Обрабатывай данные последовательно, по одному элементу.
💡 Не создавай промежуточный список с результатами.
💡 Результат можно сразу записывать в выходной поток.
💡 Для файла удобно использовать BufferedReader и BufferedWriter.
💡 Потребление памяти должно оставаться постоянным и не зависеть от размера входных данных.

Решение

Если числа записаны построчно, можно читать и фильтровать их на лету:

public void filter(
        InputStream input,
        OutputStream output
) throws IOException {
    BufferedReader reader = new BufferedReader(
            new InputStreamReader(input)
    );

    BufferedWriter writer = new BufferedWriter(
            new OutputStreamWriter(output)
    );

    String line;

    while ((line = reader.readLine()) != null) {
        int value = Integer.parseInt(line.trim());

        if (value > 5) {
            writer.write(Integer.toString(value));
            writer.newLine();
        }
    }

    writer.flush();
}

Метод не хранит исходную последовательность и результат в коллекциях. В памяти одновременно находится только текущая строка и буферы чтения и записи.

Если источник представлен как Iterable<Integer>, можно вернуть ленивый результат:

public Iterable<Integer> filter(Iterable<Integer> source) {
    if (source == null) {
        throw new IllegalArgumentException(
                "Source must not be null"
        );
    }

    return () -> new Iterator<Integer>() {

        private final Iterator<Integer> iterator = source.iterator();
        private Integer nextValue;
        private boolean nextReady;

        @Override
        public boolean hasNext() {
            if (nextReady) {
                return true;
            }

            while (iterator.hasNext()) {
                Integer value = iterator.next();

                if (value != null && value > 5) {
                    nextValue = value;
                    nextReady = true;
                    return true;
                }
            }

            return false;
        }

        @Override
        public Integer next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            Integer result = nextValue;
            nextValue = null;
            nextReady = false;

            return result;
        }
    };
}

Такой результат вычисляется только во время обхода:

for (Integer value : filter(source)) {
    System.out.println(value);
}

Временная сложность — O(n), дополнительная память — O(1), без учёта внутренних буферов ввода и вывода.