Оптимизировать код, чтобы работал быстрее

Question

Написал программу для решения задачи на простую последовательность на Java. Данные программа выдаёт правильно, однако при тестировании возникает ошибка time-limit-exceeded. В условии стоит лимит 3 секундны. Если кого не затруднит, то посмотрите код, как его лучше оптимизировать, чтобы уложится в лимит.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long m = scanner.nextLong();

        boolean hasNumbers = false;
        for (long i = 1; i <= n; i++) {
            if (i % m == 0) {
                System.out.print(i + " ");
                hasNumbers = true;
            }
        }
        if (!hasNumbers) {
            System.out.println("NO");
        }
    }
}

Answer 1

Можно убрать взятие модуля, просто перечислив числа в цикле с шагом m.

for (long i = m; i <= n; i+=m)

Однако думаю, что больше времени занимает вывод. У вас же в Java есть StringBuilder какой-нибудь или join? Вот и соберите строчку и выведите её одной операцией.

Answer 2

Проблема не совсем понятна, и действительно может заключаться в том, что для большого N и малого M простая печать в консоль достаточно ресурсоемкая, в худшем случае потребуется вывести на печать порядка 2 млрд. чисел (M = 1, N = 2³¹ - 1).

Числа long применяются в исходном коде, чтобы избежать целочисленного переполнения, хотя если входные данные по условию меньше 2³¹ - 1, т.е. Integer.MAX_VALUE. Однако, достаточно проверить, что в процессе вычислений все числа больше 0, согласно условий задачи.

Следует попробовать как минимум выводить пробел отдельно от числа, чтобы избежать ненужных конкатенаций:

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();

boolean f = false;
for (int i = m; i <= n && i > 0; i += m) {
    if (f) {
        System.out.print(" ");
    }
    System.out.print(i);
    f = true;
}
if (!f) {
    System.out.println("NO");
}

Или же построить строку при помощи StringBuilder и вывести её целиком:

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();

StringBuilder sb = new StringBuilder();
boolean f = false;
for (int i = m; i <= n && i > 0; i += m) {
    if (f) {
        sb.append(" ");
    }
    sb.append(i);
    f = true;
}
if (!f) {
    System.out.println("NO");
} else {
    System.out.println(sb.toString());
}

Более навороченный вариант для больших входных данных -- использовать буферизированный вывод BufferedWriter, так как максимальный размер StringBuilder не может превышать уже упоминавшейся константы 2 ГиБ Integer.MAX_VALUE и соответственно с его помощью можно напечатать последовательность длиной порядка 250 млн чисел. Буферизованный же вывод позволит распечатать все 2 млрд целых чисел, однако, не факт что и такой способ уложится в ограничение по времени.

private static void printSeq(int m, int n) throws IOException {
    final int bufSize = 65_536;
    boolean f = false;
    int len = 0;
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out), bufSize);
    for (int i = m; i <= n && i > 0; i += m) {
        if (f) {
            bw.append(" ");
            len++;
        }
        String num = Integer.toString(i);
        int ll = num.length();
        if (len +  ll > bufSize) {
            bw.flush();
            len = 0;
        }
        len += ll;
        bw.append(num);
        f = true;
    }
    if (!f) {
        System.out.println("NO");
    } else {
        bw.newLine();
        bw.flush();
    }
}

Тест:

public static void main(String[] args) throws IOException {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int m = scanner.nextInt();
    printSeq(m, n);
}

Answer 3

Буфер из StringBuilder на миллион символов:

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long m = scanner.nextLong();

        final int size = 1000000;
        StringBuilder sb = new StringBuilder(size + 100);

        if (m <= n) {
            sb.append(m);
            for (long i = 2 * m; i <= n; i += m) {
                sb.append(' ');
                sb.append(i);
                if (sb.length() > size) {
                    System.out.print(sb);
                    sb.setLength(0);
                }
            }
            System.out.print(sb);
        } else {
            System.out.print("NO");
        }
        System.out.println("");
    }
}

За три секунды этот код порождает 643 миллиона символов. Я их не записываю, только считаю. С записью дольше. Так или иначе этот код надо разогнать в 35 раз чтобы уложиться в ограничения задачи:

$ javac Main.java && time echo 2147483647 35 | java Main | wc -c
643177398

real  0m2.989s
user  0m3.064s
sys   0m0.416s

Я умею делать примерно в три раза быстрее. Всё равно непонятно как записать за три секунды 21Gb текста.

БЛОГ НА HUSL

Оптимизировать код, чтобы работал быстрее

Ответы (3 шт):