Comments 35
Можете меня поправить, но я вижу там О(n^2), поскольку иначе я не могу объяснить куда могло уйти столько времени.
Уйти оно могло на аллокацию тонны маленьких String'ов, коих даже в приведенном куске кода предостаточно.
Я помню свой школьный проект на C++Builder, в котором одна простая оптимизация — замена класса AnsiString сишным
char* дала прирост производительности раз в 10.
Стандартная либа джавы — это огромное количество ОЧЕНЬ плохо, буквально на отстаньте написанного кода, который работает С ОГРОМНЫМИ затратами. Взять тот же Stream API, который заявлен как удобный инструмент для работы с коллекциями в функциональном стиле и ленивыми операциями. Загляните в код — и найдете там огромную кучу мусора в виде конвейерных массивов, которые генерятся после КАЖДОЙ операции, будь то filter(), map() или что-то еще.
В общем, к чему я — не доверяйте Джаве, прости господи, ни в чем и уж точно не пишите на ней олимпиады.
Хотя вообще-то проблема автора этой статьи была даже не в сканнере, потому что обычно олимпиадные бенчмарки реализованы с учетом спецификаций языка. Скорее всего, в его случае была очень плохая система проверки.
Вот Egor: codeforces.com/profile/Egor
Вот одно из его решений недавних: codeforces.com/contest/853/standings/participant/13695075#p13695075, даблклик на любом из его решений.
Он использует свой плагин для Idea, CHelper: plugins.jetbrains.com/plugin/7091-chelper
В ее использовании организаторы вообще могут отказать.
И тесты соответственно были сделаны без учета данной проблемы.
П.с или возможно с учетом и как раз проверкой того, как мы решим данную проблему. Ибо вероятно не даром в других задачах данные вводились в столбик, а там где 20000 интов подряд, они даются в строчку.
Но это уже конспирология.
Не знаю что было у автора, а у нас (в Москве) ограничение по времени одинаково для посылок по задаче и не зависит от языка. И в регламенте тоже сказано, что ТЛи на все языки общие.
Иначе не совсем честно будет.
Вот в том и дело, что ограничения одни и те же.
Да вот только разные языки за это время делают разное количество операций.
Вообще, не очень понимаю того, что именно вы хотели донести своим комментарием.
Перепутал уровни комментариев. Верхний предназначен для GeorgWarden.
Вот в том и дело, что ограничения одни и те же.
Да вот только разные языки за это время делают разное количество операций.
ИМХО это правильно. Условно говоря, вы пришли на олимпиаду по забиванию гвоздей с микроскопом, и жалуетесь что вам не дают преференций, и ставят в равные условия с молоточниками.
Причем это не значит, что микроскоп надо выкидывать. Например, задача F с длинного отборочного тура открытой олимпиады. На джаве, питоне и паскале решалась на полный балл программой строк от силы на 20. И я, как C++-ник, страдал, пытаясь написать длинную арифметику, а затем страдал, изучая Java.
Стандартная либа джавы — это огромное количество ОЧЕНЬ плохо, буквально на отстаньте написанного кода, который работает С ОГРОМНЫМИ затратами.
Здесь вы сильно драматизируете.
в виде конвейерных массивов, которые генерятся после КАЖДОЙ операции, будь то filter(), map() или что-то еще.
А это просто враньё.
grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/stream/ReferencePipeline.java#ReferencePipeline
Можно было посмотреть исходники программ любых папок которые пишут на джаве. Можно было бы хотя бы посмотреть блог Пети Митричева, я уверен что у него тоже где-нибудь такой шаблон виден.
Просто берешь любой и в первых трёх сотнях любого контеста на codeforces любого джависта — там не будет сканнера.
Вот например мой шаблон: codeforces.com/contest/549/standings/participant/4846847#p4846847
Я понимаю когда интернет был доступен мало кому в начале 2000-ых, но сейчас у школьников есть все ресурсы чтобы проводить самостоятельную работу.
Никто не обязан объяснять эти приколы, хотя на некоторых соревнованиях реально раздают примеры как писать на джаве не через сканнер. Это не единственный прикол, их много. Только тренировка может помочь избежать проблем, и это верно для всех языков а не только для джавы.
Но я в принципе отношусь к спортивному программированию довольно пренебрежительно. Так что и не думал настолько углубляться в тонкости при подготовке.
ВСОШ для меня это просто возможность показать себе на что я способен. Именно поэтому я не сталкивался с тем, что ява подъедает на считывании стандартными библиотеками, потому что в моих основных проектах не только мало используется стандартная библиотека, но и ввод из консоли не используется.
Python, но использовать здесь его я побаивался из-за того, что этот язык известен прожорливостью
А вот это кстати зря. Python действительно очень известен своей прожорливостью и неторопливостью, и поэтому почти во всех наборах тестов (в том числе и на регионе) это учитывается.
Факт, что на Python можно и даже в некоторых случаях нужно писать олимпиады из-за того, что код в нем написать банально быстрее, но делать это нужно крайне осторожно, а подчас и вообще иметь другой язык в запасе.
Основной причиной, почему я решил писать олимпиаду именно на Java заключался в том, что на тот момент я довольно хорошо ее знал и понимал то, как в ней реализовано большинство основных структур данных и функций.
Странно, не использовать Scanner говорят практически на любом форуме где идет речь про чтение чего-то там из консоли/файоа.
Даже банальное Scanner.nextLine и разбиение String в String[] и превращение каждого из членов данного массива в int окажется значительно быстрее.
в java же есть токенайзеры, которые под это заточены
Да, среды разработки от JetBrains есть и для многих других языков, но среди этих языков нет тех, что обычно используются в спортивном программировании, не считая Python, но использовать здесь его я побаивался из-за того, что этот язык известен прожорливостью.
CLion?
Почему C++ — не "спортивный" язык? И быстрый, и код понятный, и заморочек с платформами нет, а если человек знает стандарты (да, бывает, что скобочки способны ускорить программу или убрать переполнение), то всегда будет в выигрыше по сравнению с другими языками. Питон жрёт уж меньше Java, там свой оптимизирующий костыль можно написать быстрее, чем целое решение на "индонезийском друге".
Понятно, что организация плохая (последние два года мне вообще в блокноте приходится писать на C++ вслепую за отсутствием каких бы то ни было IDE, компилятора или интерпретатора для какого-нибудь языка), тестовая платформа не очень и т.д. В данном случае Java — ну очень плохой выбор.
Я сам работал с проектами на Java, на Kotlin перешёл с радостью, хотя все проблемы платформы туда перекочевали, синтаксис стал лучше и понятнее, безопаснее. Теперь ничто не заставит меня вернуться...
Сайт Oracle был на Java и являлся полной тормозной туфтой, а если вы запустите крупный продукт на основе Java, будьте готовы, что тот же Oracle будет судиться, как это было с Гуглом. То ли она сама по себе плохая, то ли попала в плохую компанию.
и код понятный
Очень легко написать непонятный код. Или, что хуже — код с undefined behavior.
и заморочек с платформами нет
Расскажите это вводу-выводу 64-битных целых чисел (вроде long long) и 80-битных вещественных (long double). Не все компиляторы умеют (даже через iostream), те, что умеют — делают это по-разному. А ещё иногда от ключей компиляции могут менять поведение. И предупреждения компилятора, разумеется, тоже не всегда соответствуют действительности.
(последние два года мне вообще в блокноте приходится писать на C++ вслепую за отсутствием каких бы то ни было IDE
Это вы про региональный этап всероссийской олимпиады школьников по информатике? А что за регион?
Очень легко написать непонятный код. Или, что хуже — код с undefined behavior.Ладно, значит, надо иметь опыт в C++, чтобы писать безопасно, просто есть такая удобная STL, есть итераторы и встроенные алгоритмы, ссылки очень полезны. Это уже вопрос к тому, насколько логичен программист и как он отдаёт себе отчёт в потенциально небезопасных действиях.
Расскажите это вводу-выводу 64-битных целых чисел (вроде long long) и 80-битных вещественных (long double). Не все компиляторы умеют (даже через iostream), те, что умеют — делают это по-разному. А ещё иногда от ключей компиляции могут менять поведение. И предупреждения компилятора, разумеется, тоже не всегда соответствуют действительности.С такими проблемами я не встречался, их решения наверняка есть в справочниках (которые можно брать с собой) или в интернете, можно перед олимпиадой повторить, как и флаги компиляторов (хотя бы для g++ любой так или иначе знает), считывание 80-битного вещественного числа задача намного более специфическая, чем считывание простого целого числа. В Java почему-то нет unsigned, это к слову.
Это вы про региональный этап всероссийской олимпиады школьников по информатике? А что за регион?В Москве, отчасти я сам виноват, свои данные забывал, но бывает, что ставят Visual Studio и забывают плагины загрузить (по умолчанию только C#), но это уже не регион, а раньше. Под плохой организацией можно понимать и плохой дизайн, и медленную работу.
С такими проблемами я не встречался, их решения наверняка есть в справочниках
Сомневаюсь. Слишком сильно зависит от причуд конкретного компилятора. Надо знать несколько стандартных решений и пробовать, какое работает в конкретной тестирующей системе.
В Москве
А вот это неожиданно. В Москве, мне казалось, с организацией должно быть всё очень на уровне. Про Visual Studio неудобная проблема.
Вы явно не были на регионе ВСоШ в Москве)
Итак (ВМК МГУ):
1) Первый тур начался с задержкой в 50 минут (10.20)
2) Возможно из-за того, что минут тридцать звонила сирена))
3) Разбор первого тура отложили на второй тур из-за проблемы с микрофоном
4) Которая, видимо, оказалась такой серьезной, что разбор второго тура делали без микрофона
5) В середине тура из списка языков вырезали php, т.к. какой-то участник взломал на пхп(!) тестирующую систему))
6) А потом, сервер просто упал минут на 30 (ну или его уложили)
Субъективно, в прошлом году было лучше.
Во-первых тестирующая система за долгие годы уже защищена от большинства методов взлома (ага, только когда рядом с тобой компьютер, в котором профессор залогинился под админской учеткой и открыл редактор кода, после чего ушел пить кофе, думаю взломать все крайне просто, но я не поддался искушению).
Во-вторых, как сказал профессор «тестирующую систему ломать не пытаться, вернее пытаться, но не во время олимпиады, потому что иначе дисквалификация».
В-третьих, в соседней аудитории всегда дежурит 1-3 человека, умеющих работать с системой и даже если кто-нибудь загрузит программу, которая на всех 100 тестах даст TL, ее проверку смогут отменить по ходу.
P. S.
Если кому-то показалось, что регион провели ужасно — это не так.
ИМХО, данные проблемы были довольно мелкими и все равно нам было лучше, чем школьникам из других регионов, которым Яндекс.Контест тестировал посылки по 30-40 минут.
Регион провели хорошо. Но смешность инцидентов это не отменяет.
Вообще, несколько лет назад на одной олимпиаде в Москве перепутали наборы заданий. После замены выяснилось, что они частично пересекались. Кому-то повезло, а кому-то нет.
В свое время поднялись в рейтинге на ACM PCT, когда решение на жаве не проходило по времени и в последние три минуты турнира оно было с ловкостью переписано на сях, с довольно-таки хитрыми манипуляциями на указателях. В кратце — задача была в обработке большого количества строк и то ли в поиске подстрок то ли в сравнении строк (уж простите, было это лет 8 тому).
Но в топике я ожидал-таки увидеть как именно обнаружилось, что виновник — Scanner или хотя бы условие задачи, чтобы на примере было видно почему в данном конкретном случае он не подходит.
Тут и стало ясно, что дело в in-out коде. Тут то и лег глаз именно на Scanner, поскольку больше ожидать таких проблем не от кого. Ну и пошел разбирать его код по кусочкам.
Если знаете, что можно добавить в топик, буду рад помощи.
А что касается задачи, то это не имеет особого значения. Scanner плох не в конкретной задаче, а в любой ситуации, когда в одну строку записано много чисел.
Собственно это был тот самый случай.
Плюс ко всему, не уверен, что выкладывание сюда одного из заданий до того, как оно появилось на официальном сайте ВСОШ, является хорошей идеей.
Чтоб мы поняли, зачем там вообще был сканер.
Видимо, автор имеет в виду задачу 3 второго дня (7 в официальной нумерации) (условия). Считывать числа "в строчку" в этой задаче в любом случае надо.
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());
}
}
}
Как я олимпиаду на Java писал или почему лучше не пользоваться Scanner