конкурентное программирование и вклад

Question

привет всем
Я готовлюсь к соревновательному турниру, который будет на моем факультете через несколько недель, и поэтому я столкнулся с небольшой проблемой.
Конкурс ограничил использование java.io. * (кроме IOException ...)
Мне нужно прочитать (из стандартного ввода) ввод, каждый тестовый случай отделен пустой строкой. конец тестовых случаев - когда EOF найден.
Мне нужно найти способ получить данные из ввода-вывода без использования java.io.
до сих пор я получил это (что работает) - он возвращает строку, содержащую каждый тестовый случай, и ноль, когда я вне тестовых случаев.

public static String getInput() throws IOException {
    int curr=0;
    int prev=0;
    StringBuilder sb = new StringBuilder();
    while (true) {
        curr = System.in.read();
        if (curr == -1) { 
            return null; //end of data
        }
        if (curr == '\r') {
            curr = System.in.read();
        }
        if (curr == prev && curr == '\n') {
            return sb.toString(); //end of test case
        } //else:
        sb = sb.append((char)curr);
        prev = curr;
    }
}

Производительностью

(для ввода-вывода) пренебрегают, поэтому мне все равно, что я читаю только один байт каждый раз.
вопрос: есть ли более изящный (что означает - короче и быстрее для кода) способ добиться того же?

Answer 1

На самом деле, есть несколько способов обработки входных данных в Java в конкурентном программировании.

Подход 1: Использование java.util.Scanner

Это самый простой способ чтения для ввода, и он также очень прост в использовании.Это может быть медленно, если у вас есть огромное количество ввода.Если ваша программа продолжает получать TLE (превышено ограничение по времени), но ваша программа имеет правильную временную сложность, попробуйте прочитать ввод с помощью второго или третьего подхода.

Инициализация Scanner sc = new Scanner(System.in);

Чтение целого числа: int n = sc.nextInt();

Подход 2: Использование java.io.BufferedReader

Используйте это, если есть огромныйколичество входных данных, и когда срок проблемы является строгим.Это требует дополнительной работы, включая разделение ввода пробелами или использование Integer.parseInt(str); для извлечения целых чисел из ввода.

Сравнение скорости можно найти здесь https://www.cpe.ku.ac.th/~jim/java-io.html

Инициализация: BufferedReader reader = new BufferedReader(System.in);

Чтение целого числа: int n = Integer.parseInt(reader.readLine());

Подход 3: Чтениенепосредственно из FileDescriptor с использованием специального считывателя

Этот подход является самым быстрым из возможных в Java.Это требует много работы, включая реализацию читателя, а также отладку в случае возникновения проблем.Используйте этот подход, если срок строгий, и если вам разрешено вносить код в соревнование.Этот метод проверен на скорость намного быстрее, чем второй подход, но обычно он не дает вам преимущества, так как он только в 2 раза быстрее подхода BufferedReader.

Это одна из реализаций такого подхода, написанного моим другом: https://github.com/jackyliao123/contest-programming/blob/master/Utils/FastScanner.java

Использование читателя действительно зависит от вашей реализации читателя.Рекомендуется сохранить одну копию программы чтения, которая в некоторой степени гарантированно будет работать, потому что последнее, что вам нужно в конкурсе, - это нефункциональная программа чтения и отладка остальной части вашей программы, думая, что там есть некоторые ошибки.

Надеюсь, это поможет и наилучшие пожелания на вашем конкурсе!

Answer 2

Вы можете попробовать использовать класс java.util.Scanner, если разрешено java.util. Он имеет полезные методы для чтения в строке, токене или даже числа по мере необходимости. Но это медленнее, чем BufferedReader и, возможно, медленнее, чем использование System.in.read() напрямую.

Так как System.in реализует интерфейс InputStream, может также быть некоторое ускорение при использовании System.in.read(byte[] b) для чтения на входе. Таким образом, вы можете читать несколько байтов за раз, а не только один, который должен быть быстрее. Но дополнительная сложность необходимости кодировать и отлаживать его во время конкурса может не стоить этого.

Edit: В Интернете я обнаружил, что кто-то обсуждал использование System.in.read(byte[] b) на форуме UVa , когда у UVa была ужасная поддержка Java.

Answer 3

Вы можете попробовать следующее и сделать его эффективным, обернув System.in.

public static String readLine() throws IOException {
    StringBuilder sb = new StringBuilder();
    for (int ch; (ch = System.in.read()) > 0;)
        if (ch == '\r') continue;
        else if (ch == '\n') break;
        else sb.append(ch);
    return sb.toString();
}

РЕДАКТИРОВАТЬ: В Oracle JVM System.in является BufferedInputStream, который упаковывает FileInputStream, который упаковывает FileDescriptor. Все это в java.io.