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

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

Здраствуйте!Когда пишу программу на java для контеста всегда использую вот такой шаблон:

.............................
import java.util.*;
import java.io.*;
public class Eml {
 public static void main (String argv[]) throws IOException {
 new Eml ().run ();
 }
 PrintWriter out;
 Scanner in;
 public void run() throws IOException {
in=new Scanner (System.in);
// in  = new Scanner (new File("input.txt"));
 //out = new PrintWriter(new File("output.txt"));
.................................
Вроде как такая штука не быстро работает при большом объеме данных! Но вот в чем дело ,как можно сократить этот кусок кода не потеряв производительность программы?? Или привести свои шаблоны. 
  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

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

Ява никогда не отличалась особой "лаконичностью" в выражениях )

Эту программу можно "сократить", но вряд ли ты после этого она будет такой-же удобной для работы (например позволить с минимальными модификациями запустить программу с бОльшим объемом стека). Лично я всегда в main вызываю конструктор главного класса с методом запуска (программа становится более структурированной) в то время как некоторые прямо в main пишут основной код.

Кстати, в некоторых тест. системах запрещен вызов new File, т.к. он позволяет сканить директории сервера. Я использую такую конструкцию

in = new Scanner(new FileReader("input.txt"))

В общем у меня большие сомнения, что укоротив этот код ты увеличишь скорость работы программы. Об удобстве использования такой программы я вообще промолчу.

В добавок некоторые тест. системы например система, которая используется на 1/4 NEERC в центральном регионе  из-за паранойи соображений безопасности внаглую переименовывают главный класс решений на Java и поэтому приходится ещё чуток поднапрячься, чтобы всё работало

И "прокидывать" IOException из main - это ИМХО не есть гуд. Все исключения, которые возникают в программе должна ловить сама программа (исключения составляют только непроверяемые исключения).

Если интересно - можете посмотреть болванки для Java, которые используют студенты ИТМО.

Там куча всяких вещей написано.

Вот пример болванки, который я использую по дефолту

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

public class Main{

Scanner in;
PrintWriter out;

/**
Вызывается для работы с файлами/потоками.
*/
void run() {
/*
Для работы с файлами.
*/
try{
in = new Scanner(new FileReader("input.txt"));
out = new PrintWriter("output.txt");
}catch(IOException e){
throw new Error(e);
}
/*
Для работы с консолю.
*/
in = new Scanner(System.in);
out = new PrintWriter(System.out);
try {
solve();
} finally {
// правила хорошего тона рекомендуют закрыть выходной поток, даже если решение нафигнулось.
out.close();
}
}

/**
Тут пишем решение
*/
void solve(){

}

public static void main(String[] args) {
new Main().run();
}
}

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

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

Этот шаблон скорее надо немного расширить,добавив ввод побыстрее.

Вот мой шаблон

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

Интересно бы было посмотреть на результаты работы этих шаблонов на разных типах данных:) 

  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Хороший шаблон. Приблизительно такой же я взял в качестве прототипа и развил идею:
    Solution
    SolutionTest
    Последний файл добавляет junit4 тесты в приложение. В эклипсе одним нажатием кнопки можно разом прогнать все Ваши тесты, проверив их результат и время исполнения. Важно, что наличие этих тестов во втором файле никак не сказывается на файл с решением, который можно прямо так отправлять на проверку.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Из моих личных экспериментов конструкция
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int n = Integer.parseInt(tokenizer.nextToken());
работает быстрее, чем Scanner при чтении большого объема данных. Так же статические функции вызываются быстрее, и финальные функции, возможно, пройдут инлайн-подстановку.
Однако, на мой взгляд, тщательный подбор алгоритма сказывается на производительности значительнее, чем мелкие оптимизации кода.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Не совсем понял строчку

    int n = Integer.parseInt(tokenizer.nextToken());

    В документации к nextToken() написано, что это "Returns:the value of the ttype field." 

    В свою очередь ttype :"After a call to the nextToken method, this field contains the type of the token just read". Возможно в конце концов оно и работает, но почему бы не использовать предназначенные переменные sval, nval для получения результата? Вроде их использование более логичное. Или причина в другом?

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Документация говорит, что возвращается String.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это StringTokenizer, а не StreamTokenizer. И вообще StreamTokenizer лучше не использовать, т.к. там непонятно как читать 64-битные числа
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        А что с ними не так? Просвятите, если можно.

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          StreamTokenizer.nval типа double, если их приводить к long-ам, теряется точность
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Вот видите, с StreamTokenizer-ом нужны дополнительные шаманства
          (коммент не туда ушел)
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Согласен, что это не плюс. Но как то приучили писать именно через StreamTokenizer. А сравнивать по скорости чтения эти 2 класса не пробовали? По гибкости настройки для чтения всяких изощренных вводов или ещё как-нибудь?
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              1. Не тормозит, думаю, скорость не сильно различается. Во всяком случае, почти все пишут через StringTokenizer.
              2. Можно в методе nextToken указать разделители лексем, иногда бывает удобно.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    На Тимусе есть парочка задачек, где решние на Яве протащить в ограничения тяжеловато. Особенно по памяти. Так что знание некоторых оптимизационных вещей может быть полезным, когда ,само собой, алгоритм абсолютно корректен.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Те задачки, про которые Вы говорите, протащить в ограничения вообще невозможно. Вот тут три штуки указаны: http://acm.timus.ru/help.aspx?topic=java.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Да что Вы говорите? :-)
        У меня сдана "Медиана последовательности" на Java, а мой тренер сдал Stacks на Java
        Для меня пока что составляет проблему сдать Pascal vs C++ на Java.
        А вторая версия этой задачи ещё сложнее.
        • 13 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          Хорошо, признаюсь в своей плохой осведомленности :). Вопрос тогда такой: при помощи каких извращений задачи были сданы? Я так понимаю, что-то стандартно подгружаемое умышленно не подгружалось. Я прав?

          UPD. Вообще, я сказал по поводу невозможности сдать на Яве по той причине, что невозможно сдать на C#, а последний традиционно все-таки менее прожорливый по отношению к памяти :).
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вообще, вот:
http://codeforces.net/blog/entry/218#comment-2495
http://codeforces.net/blog/entry/218#comment-2498

А шаблон можно у Петра скопировать, например - источник надежный.
13 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

Решил написать через токен! взял шаблон с тимуса!вот:
import java.io.*;
import java.util.*;

public class Main
{
   public static void main(String[] args) throws IOException
   {
      new Main().run();
   }

   StreamTokenizer in;
   PrintWriter out;

   int nextInt() throws IOException
   {
      in.nextToken();
      return (int)in.nval;
   }

   void run() throws IOException
   {
      in = new StreamTokenizer(new BufferedReader(new InputStreamReader("input.txt")));
      out = new PrintWriter(new OutputStreamWriter("output.txt"));
      solve();
      out.flush();
   }

   void solve() throws IOException
   {
      int a = nextInt();
      int b = nextInt();
      out.print(a + b);
      out.close();
}
  }
Но на acmp.ru выдает сообщения comp.error!:
Main.java:22: cannot find symbol
symbol  : constructor InputStreamReader(java.lang.String)
location: class java.io.InputStreamReader
      in = new StreamTokenizer(new BufferedReader(new InputStreamReader("input.txt")));
                                                  ^
Main.java:23: cannot find symbol
symbol  : constructor OutputStreamWriter(java.lang.String)
location: class java.io.OutputStreamWriter
      out = new PrintWriter(new OutputStreamWriter("output.txt"));
                            ^
2 errors
Помогите устранить ошибку! в чем проблема?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну написано же:
    cannot find constructor InputStreamReader(java.lang.String)
    cannot find constructor OutputStreamWriter(java.lang.String)
    что неясно?

    Самому надо разбираться в таких проблемах. Вот тебе уже готовый шаблон: http://pastebin.com/PeeZkVjV
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Потому что нету такого конструктора. Есть с помощью потока, к примеру
    input = new BufferedReader(new InputStreamReader(System.in));

    или 

    input = new BufferedReader(new FileReader("input.txt"));