Как я олимпиаду на Java писал или почему лучше не пользоваться Scanner

Вчера завершился Региональный этап Всероссийской олимпиады школьников. Я участвовал в нем и выбрал для этого язык Java. Основной причиной, почему я решил писать олимпиаду именно на Java заключался в том, что на тот момент я довольно хорошо ее знал и понимал то, как в ней реализовано большинство основных структур данных и функций. Также IntellijIDEA очень сильно способствовала плодотворному кодингу, в ситуациях, когда время является решающим фактором. Да, среды разработки от JetBrains есть и для многих других языков, но среди этих языков нет тех, что обычно используются в спортивном программировании, не считая Python, но использовать здесь его я побаивался из-за того, что этот язык известен прожорливостью.

Однако наш друг, носящий имя индонезийского острова, оказался в некоторых ситуациях еще медленнее, чем прожорливый змей.

Не буду сильно вникать в условия задачи, в решении которой я столкнулся с тем, что программа не успевает справится с задачей за предоставленное время, но отмечу один факт: то решение, которое я написал, являлось эталонным (то есть судьи в пакете с тестами предоставили идентичное решение, но на C), не имело бесконечных циклов и прочего, а его сложность была O(n).

При ограничениях, что n <= 20000, а для работы программы доступна одна секунда, встал вопрос о том, кто же съел время.

И по итогу можно с точностью сказать, что виновником являлся Scanner и его функция nextInt().

А теперь более подробно разберемся с тем, как же эта функция работает.

Сама функция состоит всего из одной строчки return nextInt(defaultRadix);.
А вот то, что творится уже внутри этой функции нам гораздо интереснее.

Первым делом идет проверка if ((typeCache != null) && (typeCache instanceof Integer)
&& this.radix == radix)
и здесь очень важно понять, чем же является typeCache и откуда он берется. И тут все вполне просто. Он является ничем иным, как строкой нашей консоли, записанной в форме Object и если этот объект (читать как строка, которую мы ввели) является инстансом Integer, то Scanner делает вывод о том, что введенная строка это и есть искомое число и возвращает его.
Тут все хорошо и сложность этой операции О(1). Отсюда можно заключить, что вводя в строчку только одно число мы практически не тратим время на преобразование ввода в число.
Значит едем дальше.

А вот тут-то и появляется виновник торжества.

Если в строке, которую получил Scanner не int или же если там несколько таковых, то вызывается вот такая строка кода:

String s = next(integerPattern());

А под ней скрыто вот что:

public String next(Pattern pattern) {
        ensureOpen();
        if (pattern == null)
            throw new NullPointerException();

        // Did we already find this pattern?
        if (hasNextPattern == pattern)
            return getCachedResult();
        clearCaches();

        // Search for the pattern
        while (true) {
            String token = getCompleteTokenInBuffer(pattern);
            if (token != null) {
                matchValid = true;
                skipped = false;
                return token;
            }
            if (needInput)
                readInput();
            else
                throwFor();
        }
    }

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

Первые три строчки это просто защита от дурака.

А дальше, как нам подсказывают комментарии тех, кто писал этот код идет проверка «а мы случаем не нашли уже такой паттерн?», но в нашем случае эта проверка всегда будет возвращать ложь, поскольку мы на прошлом этапе уже проверили, что полученная нами строка не int.

И что мы видим в конце? Понимая, что быстрых способов поиска больше нет, Scanner сдается и запускает бесконечный цикл который завершится только, если перебором будет найдено что-то, что нам подходит.

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

Можете меня поправить, но я вижу там О(n^2), поскольку иначе я не могу объяснить куда могло уйти столько времени.

Итог: в случае, когда вам нужно, чтобы программа действительно быстро считала целые числа из консоли, не доверяйте это делоScanner.nextInt(). Даже банальное Scanner.nextLine и разбиение String в String[] и превращение каждого из членов данного массива в int окажется значительно быстрее.
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 35

    +2
    Можете меня поправить, но я вижу там О(n^2), поскольку иначе я не могу объяснить куда могло уйти столько времени.

    Уйти оно могло на аллокацию тонны маленьких String'ов, коих даже в приведенном куске кода предостаточно.

    Я помню свой школьный проект на C++Builder, в котором одна простая оптимизация — замена класса AnsiString сишным char* дала прирост производительности раз в 10.
      –2

      Стандартная либа джавы — это огромное количество ОЧЕНЬ плохо, буквально на отстаньте написанного кода, который работает С ОГРОМНЫМИ затратами. Взять тот же Stream API, который заявлен как удобный инструмент для работы с коллекциями в функциональном стиле и ленивыми операциями. Загляните в код — и найдете там огромную кучу мусора в виде конвейерных массивов, которые генерятся после КАЖДОЙ операции, будь то filter(), map() или что-то еще.
      В общем, к чему я — не доверяйте Джаве, прости господи, ни в чем и уж точно не пишите на ней олимпиады.
      Хотя вообще-то проблема автора этой статьи была даже не в сканнере, потому что обычно олимпиадные бенчмарки реализованы с учетом спецификаций языка. Скорее всего, в его случае была очень плохая система проверки.

        +2
        Среди топов много джавистов.

        Вот Egor: codeforces.com/profile/Egor
        Вот одно из его решений недавних: codeforces.com/contest/853/standings/participant/13695075#p13695075, даблклик на любом из его решений.

        Он использует свой плагин для Idea, CHelper: plugins.jetbrains.com/plugin/7091-chelper

          +1
          TBH, я не говорю, что Джава плохой язык для олимпиадного программирования, как могло показаться. На ней вполне можно гриндить рейтинг на КФ, но проблема большого количества олимпиадников (по крайней мере, ВСОШ-а) это то, что этапы олимпиады проводятся НЕ на КФ, а на каких-то идиотских, иногда самописных платформах. Именно об этом я и говорю — лучше дважды перестраховаться и использовать прозрачный с точки зрения низкого уровня язык, на который к тому-же рассчитывают организаторы — Паскаль или Си. Умалчивая вообще о том, что участие в ВСОШ это неблагодарный труд, потому что организована она наиболее низкосортно.
          +1
          На самом деле ситуация заключается в том, что Java входит в список разрешенных, но не основных языков на Всероссийской Олимпиаде школьников.
          В ее использовании организаторы вообще могут отказать.
          И тесты соответственно были сделаны без учета данной проблемы.

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

            Не знаю что было у автора, а у нас (в Москве) ограничение по времени одинаково для посылок по задаче и не зависит от языка. И в регламенте тоже сказано, что ТЛи на все языки общие.
            Иначе не совсем честно будет.

              0

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

                +1

                Перепутал уровни комментариев. Верхний предназначен для GeorgWarden.


                Вот в том и дело, что ограничения одни и те же.
                Да вот только разные языки за это время делают разное количество операций.

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


                Причем это не значит, что микроскоп надо выкидывать. Например, задача F с длинного отборочного тура открытой олимпиады. На джаве, питоне и паскале решалась на полный балл программой строк от силы на 20. И я, как C++-ник, страдал, пытаясь написать длинную арифметику, а затем страдал, изучая Java.

                  0
                  Да я и не говорю ничего против того, что условия равные.
                  Более того, в одной из комментариев выше я даже писал, что входные данные в этом задании были написаны именно таким образом специально, чтобы показать людям с микроскопами, что стоило прихватить молоток.
              +6
              Стандартная либа джавы — это огромное количество ОЧЕНЬ плохо, буквально на отстаньте написанного кода, который работает С ОГРОМНЫМИ затратами.

              Здесь вы сильно драматизируете.


              в виде конвейерных массивов, которые генерятся после КАЖДОЙ операции, будь то filter(), map() или что-то еще.

              А это просто враньё.

                0
                А у вас пруфов, случаем, нет? В текущем варианте заявления звучат как-то диванно.
              +3
              Ты просто не подготовился к олимпиаде.

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

              Просто берешь любой и в первых трёх сотнях любого контеста на codeforces любого джависта — там не будет сканнера.

              Вот например мой шаблон: codeforces.com/contest/549/standings/participant/4846847#p4846847

              Я понимаю когда интернет был доступен мало кому в начале 2000-ых, но сейчас у школьников есть все ресурсы чтобы проводить самостоятельную работу.

              Никто не обязан объяснять эти приколы, хотя на некоторых соревнованиях реально раздают примеры как писать на джаве не через сканнер. Это не единственный прикол, их много. Только тренировка может помочь избежать проблем, и это верно для всех языков а не только для джавы.
                0
                В каком-то смысле да, не подготовился.
                Но я в принципе отношусь к спортивному программированию довольно пренебрежительно. Так что и не думал настолько углубляться в тонкости при подготовке.
                ВСОШ для меня это просто возможность показать себе на что я способен. Именно поэтому я не сталкивался с тем, что ява подъедает на считывании стандартными библиотеками, потому что в моих основных проектах не только мало используется стандартная библиотека, но и ввод из консоли не используется.
                0
                Python, но использовать здесь его я побаивался из-за того, что этот язык известен прожорливостью

                А вот это кстати зря. Python действительно очень известен своей прожорливостью и неторопливостью, и поэтому почти во всех наборах тестов (в том числе и на регионе) это учитывается.
                  0
                  Почти, да не во всех.
                  Факт, что на Python можно и даже в некоторых случаях нужно писать олимпиады из-за того, что код в нем написать банально быстрее, но делать это нужно крайне осторожно, а подчас и вообще иметь другой язык в запасе.
                    0
                    На простых задачах, где можно сделать действительно линейное решение без структур — может и да. На сложных задачах на структуры данных подгонят под питон смерти подобно — линия на питоне может работать дольше квадрата на C++.
                      0

                      Это стереотип. Python не такой медленный и линия будет быстрее квадрата С++.


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

                    0
                    Основной причиной, почему я решил писать олимпиаду именно на Java заключался в том, что на тот момент я довольно хорошо ее знал и понимал то, как в ней реализовано большинство основных структур данных и функций.


                    Странно, не использовать Scanner говорят практически на любом форуме где идет речь про чтение чего-то там из консоли/файоа.
                    Даже банальное Scanner.nextLine и разбиение String в String[] и превращение каждого из членов данного массива в int окажется значительно быстрее.


                    в java же есть токенайзеры, которые под это заточены
                      +2
                      Да, среды разработки от JetBrains есть и для многих других языков, но среди этих языков нет тех, что обычно используются в спортивном программировании, не считая Python, но использовать здесь его я побаивался из-за того, что этот язык известен прожорливостью.

                      CLion?

                        0

                        Я как-то упустил момент его появления видимо.
                        Спасибо.

                        –1

                        Почему C++ — не "спортивный" язык? И быстрый, и код понятный, и заморочек с платформами нет, а если человек знает стандарты (да, бывает, что скобочки способны ускорить программу или убрать переполнение), то всегда будет в выигрыше по сравнению с другими языками. Питон жрёт уж меньше Java, там свой оптимизирующий костыль можно написать быстрее, чем целое решение на "индонезийском друге".


                        Понятно, что организация плохая (последние два года мне вообще в блокноте приходится писать на C++ вслепую за отсутствием каких бы то ни было IDE, компилятора или интерпретатора для какого-нибудь языка), тестовая платформа не очень и т.д. В данном случае Java — ну очень плохой выбор.


                        Я сам работал с проектами на Java, на Kotlin перешёл с радостью, хотя все проблемы платформы туда перекочевали, синтаксис стал лучше и понятнее, безопаснее. Теперь ничто не заставит меня вернуться...


                        Сайт Oracle был на Java и являлся полной тормозной туфтой, а если вы запустите крупный продукт на основе Java, будьте готовы, что тот же Oracle будет судиться, как это было с Гуглом. То ли она сама по себе плохая, то ли попала в плохую компанию.

                          0
                          и код понятный

                          Очень легко написать непонятный код. Или, что хуже — код с undefined behavior.


                          и заморочек с платформами нет

                          Расскажите это вводу-выводу 64-битных целых чисел (вроде long long) и 80-битных вещественных (long double). Не все компиляторы умеют (даже через iostream), те, что умеют — делают это по-разному. А ещё иногда от ключей компиляции могут менять поведение. И предупреждения компилятора, разумеется, тоже не всегда соответствуют действительности.


                          (последние два года мне вообще в блокноте приходится писать на C++ вслепую за отсутствием каких бы то ни было IDE

                          Это вы про региональный этап всероссийской олимпиады школьников по информатике? А что за регион?

                            0
                            Очень легко написать непонятный код. Или, что хуже — код с undefined behavior.
                            Ладно, значит, надо иметь опыт в C++, чтобы писать безопасно, просто есть такая удобная STL, есть итераторы и встроенные алгоритмы, ссылки очень полезны. Это уже вопрос к тому, насколько логичен программист и как он отдаёт себе отчёт в потенциально небезопасных действиях.

                            Расскажите это вводу-выводу 64-битных целых чисел (вроде long long) и 80-битных вещественных (long double). Не все компиляторы умеют (даже через iostream), те, что умеют — делают это по-разному. А ещё иногда от ключей компиляции могут менять поведение. И предупреждения компилятора, разумеется, тоже не всегда соответствуют действительности.
                            С такими проблемами я не встречался, их решения наверняка есть в справочниках (которые можно брать с собой) или в интернете, можно перед олимпиадой повторить, как и флаги компиляторов (хотя бы для g++ любой так или иначе знает), считывание 80-битного вещественного числа задача намного более специфическая, чем считывание простого целого числа. В Java почему-то нет unsigned, это к слову.

                            Это вы про региональный этап всероссийской олимпиады школьников по информатике? А что за регион?
                            В Москве, отчасти я сам виноват, свои данные забывал, но бывает, что ставят Visual Studio и забывают плагины загрузить (по умолчанию только C#), но это уже не регион, а раньше. Под плохой организацией можно понимать и плохой дизайн, и медленную работу.
                              +1
                              С такими проблемами я не встречался, их решения наверняка есть в справочниках

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


                              В Москве

                              А вот это неожиданно. В Москве, мне казалось, с организацией должно быть всё очень на уровне. Про Visual Studio неудобная проблема.

                                +1

                                Вы явно не были на регионе ВСоШ в Москве)
                                Итак (ВМК МГУ):
                                1) Первый тур начался с задержкой в 50 минут (10.20)
                                2) Возможно из-за того, что минут тридцать звонила сирена))
                                3) Разбор первого тура отложили на второй тур из-за проблемы с микрофоном
                                4) Которая, видимо, оказалась такой серьезной, что разбор второго тура делали без микрофона
                                5) В середине тура из списка языков вырезали php, т.к. какой-то участник взломал на пхп(!) тестирующую систему))
                                6) А потом, сервер просто упал минут на 30 (ну или его уложили)


                                Субъективно, в прошлом году было лучше.

                                  0
                                  Да уж, у нас тут во Владивостоке все полегче.
                                  Во-первых тестирующая система за долгие годы уже защищена от большинства методов взлома (ага, только когда рядом с тобой компьютер, в котором профессор залогинился под админской учеткой и открыл редактор кода, после чего ушел пить кофе, думаю взломать все крайне просто, но я не поддался искушению).
                                  Во-вторых, как сказал профессор «тестирующую систему ломать не пытаться, вернее пытаться, но не во время олимпиады, потому что иначе дисквалификация».
                                  В-третьих, в соседней аудитории всегда дежурит 1-3 человека, умеющих работать с системой и даже если кто-нибудь загрузит программу, которая на всех 100 тестах даст TL, ее проверку смогут отменить по ходу.
                                    0

                                    P. S.
                                    Если кому-то показалось, что регион провели ужасно — это не так.
                                    ИМХО, данные проблемы были довольно мелкими и все равно нам было лучше, чем школьникам из других регионов, которым Яндекс.Контест тестировал посылки по 30-40 минут.
                                    Регион провели хорошо. Но смешность инцидентов это не отменяет.

                                    0
                                    Многое зависит от местных организаторов. Бывает, что в аудитории есть несколько человек, которые быстро исправляют все технические проблемы и знают языки и особенности сред, чтобы помочь на пробном туре (если это разрешено правилами). А бывает, что там сидит девочка, которой просто сказали следить, чтобы никто не списывал. Тогда начинаются проблемы.

                                    Вообще, несколько лет назад на одной олимпиаде в Москве перепутали наборы заданий. После замены выяснилось, что они частично пересекались. Кому-то повезло, а кому-то нет.
                              0

                              В свое время поднялись в рейтинге на ACM PCT, когда решение на жаве не проходило по времени и в последние три минуты турнира оно было с ловкостью переписано на сях, с довольно-таки хитрыми манипуляциями на указателях. В кратце — задача была в обработке большого количества строк и то ли в поиске подстрок то ли в сравнении строк (уж простите, было это лет 8 тому).


                              Но в топике я ожидал-таки увидеть как именно обнаружилось, что виновник — Scanner или хотя бы условие задачи, чтобы на примере было видно почему в данном конкретном случае он не подходит.

                                0
                                А что именно непонятно в том, как был найден виновник? Я же писал в топике, что у меня было сдано эталонное решение со сложностью O(n). Соответственно здесь и возник сразу вопрос, если решение правильное, то в чем проблема? Проверил программу на возможные бесконечные циклы и просто баги. Ошибок не было обнаружено.
                                Тут и стало ясно, что дело в in-out коде. Тут то и лег глаз именно на Scanner, поскольку больше ожидать таких проблем не от кого. Ну и пошел разбирать его код по кусочкам.
                                Если знаете, что можно добавить в топик, буду рад помощи.

                                А что касается задачи, то это не имеет особого значения. Scanner плох не в конкретной задаче, а в любой ситуации, когда в одну строку записано много чисел.
                                Собственно это был тот самый случай.
                                Плюс ко всему, не уверен, что выкладывание сюда одного из заданий до того, как оно появилось на официальном сайте ВСОШ, является хорошей идеей.
                                0
                                Да, можно код?
                                Чтоб мы поняли, зачем там вообще был сканер.
                                  0

                                  Видимо, автор имеет в виду задачу 3 второго дня (7 в официальной нумерации) (условия). Считывать числа "в строчку" в этой задаче в любом случае надо.

                                    0
                                    Да. Речь именно об этой задаче.
                                  0
                                  Вот такой код предлагают авторы курса «Алгоритмы и структуры данных» на coursera.org
                                  class FastScanner
                                  import java.io.*;
                                  import java.util.*;
                                  
                                  public class FastRead {
                                      public static void main(String[] args) {
                                          FastScanner scanner = new FastScanner(System.in);
                                          int n = scanner.nextInt();
                                      }
                                  
                                      static class FastScanner {
                                          BufferedReader br;
                                          StringTokenizer st;
                                  
                                          FastScanner(InputStream stream) {
                                              try {
                                                  br = new BufferedReader(new InputStreamReader(stream));
                                              } catch (Exception e) {
                                                  e.printStackTrace();
                                              }
                                          }
                                  
                                          String next() {
                                              while (st == null || !st.hasMoreTokens()) {
                                                  try {
                                                      st = new StringTokenizer(br.readLine());
                                                  } catch (IOException e) {
                                                      e.printStackTrace();
                                                  }
                                              }
                                              return st.nextToken();
                                          }
                                  
                                          int nextInt() {
                                              return Integer.parseInt(next());
                                          }
                                      }
                                  }
                                  

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

                                  Самое читаемое