Блог пользователя miraina

Автор miraina, 13 лет назад, По-русски

Здравствуйте! Обычно я пользуюсь следующим шаблоном в Java:


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


public class Main {
    
    public BufferedReader input;
    public PrintWriter output;
    public StringTokenizer stoken = new StringTokenizer("");
    
    public static void main(String[] args) throws IOException {
        new Main();
    }
    
    Main() throws IOException{
        input = new BufferedReader(
                  new InputStreamReader(System.in)
        );
        output = new PrintWriter(System.out);
        Long x = nextLong(); 

        input.close();
        output.close();
    }

    private Long nextLong() throws NumberFormatException, IOException {
        return Long.parseLong(nextString());
    }

    private String nextString() throws IOException {
        while (!stoken.hasMoreTokens()){
            String st = input.readLine();
            stoken = new StringTokenizer(st);
        }
        return stoken.nextToken();
    }
    
    
}


Недавно столкнулась со следующей задачей: http://acm.timus.ru/problem.aspx?space=1&num=1001

Как правильно считывать данные, если неизвестно, сколько строк содержится во входном файле? Как усовершенствовать мой шаблон? Заранее спасибо!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

String s;
List<Integer> list = new ArrayList<Integer>();
while ((s = input.readline()) != null) { //считываем строки, пока есть
Scanner sc = new Scanner(s);
//считываем числа из строки
while (sc.hasNext()) {
list.add(sc.nextInt());
}
}

Ну или можно просто Сканнером, если инпут небольшой.

Scanner in = new Scanner(System.in);
List<Integer> list = new ArrayList<Integer>();
while (in.hasNext()) {
list.add(in.nextInt());
}

UPD. Кстати, input.close() лучше убрать. От этого ничего не изменится, но если эту строчку оставить, то некоторые системы ее не пропустят. Например, вчера я попался с этим на CodeChef - там выдает ошибку без номера теста, так что было непонятно, почему Runtime Error. Оказалось, что из-за закрытия BufferedReader'а.

P. S. Как тут код форматировать? Есть какие-нибудь тэги специальные?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Это по-извращенски, но работает.
    < pre class="source prettyprint" >
    (YOUR CODE HERE)
    < /pre >

    Выглядеть видимо так будет.
    1. Scanner in = new Scanner(System.in);
    2. List list = new ArrayList();
    3. while (in.hasNext()) {
    4.     list.add(in.nextInt());
    5. }

    Но отредактировать это будет нереально. Лучше использовать один раз.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно так:

try {
    while (true) {
        // do something
    }
} catch (NullPointerException e) {}

BufferedReader возвратит null, если данных больше нет, поэтому конструктор StringTokenizer выбросит NullPointerException
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Scanner можно использовать лишь при малых данных, всем известно, что он не очень быстрый.
Я обычно изменяю метод nextString:

    private String nextString() throws IOException {
        while (!stoken.hasMoreTokens()){
            String st = input.readLine();
            if (st == null) return null;
stoken = new StringTokenizer(st); } return stoken.nextToken(); }
В таком случае этот метод становится еще больше похожим на input.readLine(), который также выдает null при отсутствии строк в буфере; вот как выглядит ввод:

String s;
while ((s = nextString) != null){
         long x = Long.parseLong(s);
         // do something with x
}
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Не мог бы ты дописать код, который содержит внутри себя nextString() ?
    Есть подозрение, что вызывать конструктор StringTokenizer для каждой строки не самая лучшая идея во всех отношениях.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      И вообще пользоваться классом StringTokenizer - не лучшая идея т.к.

      "StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead."
      (с) API Reference

      P.S. Кстати, кто и когда в последний раз проверял Scanner на тормозность и в сравнении с чем? Я к тому что мне в последнее время не встречались задачи где количество входных данных было бы такое, что Scanner вызывал бы TLE. Если же очевидно что в задаче входных данных порядка 1000 строк/чисел и т.п., то по-моему вообще о заметном "торможении" говорить как-то странно - и использовать мегазадумчивые "паттерны" из источника "одна бабка сказала что так будет лучше" - довольно нелепо. :D

      Например создание PrintWriter вместо PrintStream без выключения автофлашинга неужели действительно так увеличивает удобство и крутизну? Если выводить нужно много отдельных элементов - вообще лучше запишите их в StringBuilder а потом его целиком выдайте в System.out. ;-)
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Эта тема уже много раз поднималась, но зачастую в виде отдельных комментариев, а не постов.

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

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Хотелось бы увидеть способы "выкручиваться". А то использование  кода, приведённого в главном посте, даёт следующие результаты:

          http://www.e-olimp.com/solutions/119720 - для BufferedReader + StringTokenizer

          http://www.e-olimp.com/solutions/224700 - для Scanner

          Время отличается в 2 раза, заметьте. При том, что обе проги содержат тучу вычислений с бигинтами.

          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            В общем "Coming soon ..."

          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Хм. Я правильно понял что у Вас получилось ~300мс с использованием Scanner и ~600мс с использованием BufferedReader+StringTokenizer, т.е. всё наоборот?

            Я к тому что этот пример не показателен. На большинстве платформ по моим наблюдениям Scanner действительно работает медленнее приблизительно в 4 раза, но поскольку на чтение 1 числа типа long он тратит порядка 2-3мкс, я б сказал что вопрос этот актуален только для задач где нужно вводить более 100 тыс чисел.
            • 13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              Для указанной задачи я читаю 500 длииинных строк (порядка 10^4 символов), а остальные действия - идентичны. И раз уж такая сильная разница, при чём не в пользу BufferedReader+StringTokenizer, то по крайней мере, он не "быстрее вообще", а разве что "быстрее для отдельных случаев". Поэтому я хочу узнать у более знающих, чем я, людей, нет ли универсального средства.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        autoflush вообще заслуживает отдельного внимания.

        Помню, в одной задаче я решил использовать следующий подход:

        Грубо говоря, пока решение в задаче есть - в вывод, с отключенным autoflush, кидался ответ (последовательность чисел). Если в какой то момент оказалось, что последовательность (ответ) не правильная, то отдельным объектом писалось, что "решения нет", а содержимое самого буфера не флашилось. Иначе просто флашил буфер.

        Помню, та реализация успешно прошла, но потом, разбираясь с flush, оказалось, что нельзя быть уверенным, что буффер сам не очиститься, не вызывая flush. При переполнении буфера, который вроде 32 кб, данные в любом случае выведутся. Вот такой урок получил на будущее...

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Вообще заниматься въедливой оптимизацией на уровне использования слабодокументированных особенностей реализации API по-моему легкомысленно, т.к. необходимо будет перепроверять достигнутые результаты на различных платформах и различных версиях JRE.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно читать в бесконечном цикле, в какой-то момент выбросится исключение