Когда на ACM ICPC отменили Pascal, мы всей командой перешли на С++ и в течение последних двух лет олимпиадной "карьеры" писали именно на нём. За это время мы неплохо освоили STL.
Кроме того, сейчас на работе я также пишу на С++ (а также использую Qt). Так что могу сказать, что с С++ я знаком неплохо.
Но я решил освоить Java. В олимпиадах мы применяли её только для задач на длинную арифметику, так что представление о ней есть неплохое. Кроме того, я прочитал книгу Джошуа Блоха "Effective Java", поэтому я могу сказать, что я даже в курсе некоторых особенностей этого языка.
Но чего я не знаю, так это основных классов Java SE. Вот у меня и возникла следующая идея. Неплохо было бы, если б кто-то из тех, кто в олимпиадах активно использует/использовал Java, описал "джентельменский" набор классов и их основных методов, которые регулярно приходится применять на контестах. Это будет полезно не только мне, но и всем, кто собирается переходить с, например, Pascal на Java.
Причём я хочу подчеркнуть, что хотелось бы иметь описание классов именно с точки зрения олимпиадного программирования с указанием соответствующих особенностей. Конечно, можно отправить меня к какой-нибудь документации или книге по Java SE. Но там не учтён опыт многочисленных соревнований.
P.S. Сам я подумываю о том, чтобы описать "джентельменский набор" С++-олимпиадника.
"P.S. Сам я подумываю о том, чтобы описать "джентельменский набор" С++-олимпиадника."
хорошая инициатива; думаю будет, чему поучиться
я думаю, что ты неправильно понял идею автора поста
к примеру, в c++ stl есть stack, но им лучше не пользоваться, потому что он динамически выделяет память и, поэтому, медленнее работает обычного стека на массиве; а в олимпиадных задачах хорошо бы иметь стек с малым временем работы операций pop и push
одну и ту же вещь можно реализовать сотнями способов, но здесь речь идёт именно об олимпиадных задачах, где важны такие параметры, как малое количество кода и быстродействие
Я сам припоминаю пару таких случаев, но кажется что это скорее исключение чем правило :о
для стека да, есть; например, когда ограничения порядка 107-108.
а вектора - это же вообще катастрофа: из-за них бывает TLE очень часто
Честно говоря, не помню, сталкивался ли я с тормознутосью std::stack - помнится, мы всегда в качестве стэка использовали std::vector.
Но что, в С++ STL реально тормозит, так это std::queue, сделанная на основе std::deque. Я не знаю, как реализованы эти классы, случаи, когда замена queue на массив меня на TL на AC я помню отчётливо.
индексация в векторе в с++ на гнутом компиляторе происходит раз в 5-6 медленее, чем индексация в обычном массиве
да, я, пожалуй, погорячился по поводу 5-6 раз
приведённый ниже код выполняется ~5 секунд для обычного массива и ~12 для вектора
vector v[100000]; int a[100000][300]; int main() { memset(a,0,sizeof(a)); for(int i=0;i<100000;i++) for(int j=0;j<300;j++) v[i].pb(0); int ans=0,A=0,B=0; for(int i=0;i<100000000;i++) { ans+=a[A][B]; // ans+=v[A][B]; A++; B++; if (A==100000) A=0; if (B==300) B=0; } cout<<ans; return 0; }vector <int> v[100000];
редактор как-то неправильно воспринимает символ "<"
я натупил
вычти время заполнения массива v и получишь те самые 5-6 раз
В целом, конечно вектора медленнее чем массивы, но я дают в разы больше возможностей. А уж если код одной заменой векторов на массивы дает АЦ вместо ТЛ, то видимо авторы задачи плохие ограничения подобрали, ну или решение с массивами просто
ассимптотически хуже авторского, но проходит на грани из-за того что ограничение по времени чуть выше, чтобы языки типа Java не обидеть.
и что из этого?
если у тебя на реальном контесте TL#32 и программа ненамного дольше работает на макстесте, чем хотелось бы, то частенько бывает достаточно заменить вектора на обычные массивы, потому что вектора тормозят (как показал тест выше)
вот и всё
прошу относиться к моему комментарию выше как к практическому совету, а не как к готовности поспорить непонятно о чём
Вот интересно, как читали мой пост те, кто всё-таки отправил меня к документации. Я же явно подчеркнул, что этого делать не надо: "Конечно, можно отправить меня к какой-нибудь документации или книге по Java SE. Но там не учтён опыт многочисленных соревнований."
Я умею читать и при необходимости могу разобраться с документацией. Но меня интересует именно опыт применения стандартных классов. В документации вряд ли написано, что Scanner тормозит и, когда размер ввода большой, надо использовать StreamTokenizer.
Убедительная просьба, внимательно читайте посты и не давайте тривиальных советов, приводящих автора в бешенство. А то складывается впечатление, что меня принимают за умственно отсталого человека, неспособного догадаться, что существует документация по стандартным классам.
во-первых, автор писал: "Но я решил освоить Java. ...представление о ней есть неплохое. Кроме того, я прочитал книгу Джошуа Блоха "Effective Java", поэтому я могу сказать, что я даже в курсе некоторых особенностей этого языка"
во-вторых, я НИ РАЗУ не столкнулся с тем, чтобы автор делал "вывод, что она (Java) не подходит для олимпиад"
такое впечатление, что идея, которую пытался донести автор, осталась глубоко в тумане, несмотря на несколько очень доступных и прозрачных примеров выше (о стеках, очередях и токенайзерах)
Я знаю три сравнительно простых способа читать входные данные: Scanner, StreamTokenizer и связка BufferedReader + StringTokenizer.
Scanner
Имеет кучу методов для чтения примитивных типов, длинных чисел, строки до разделителя, строки до переноса, строки по регулярному выражению и так далее. Все это богатство основывается на регулярных выражениях, поэтому работает медленно. Когда размер входного файла - примерно мегабайт, с помощью сканера его удастся прочитать примерно за полсекунды-секунду. Поэтому, прежде чем использовать сканер, убедитесь, что размер входного файла небольшой. Подводные камни: конструктор Scanner(String) читает данные из строки, а не из файла, который так назван :-)
StreamTokenizer
Класс, изначально предназначенный для токенизации исходных текстов на Java. По этой причине имеет "слегка" запутанный интерфейс и кучу нетривиальных настроек. Из предложенных вариантов является самым быстрым, но имеет кучу подводных камней:
1) Если вы настраиваете его на чтение чисел, все они хранятся в double после прочтения. Это очень плохо, когда среди входных данных попадаются long'и (64-битные числа) - они теряют точность, если их хранить в double.
2) В одном из своих режимов автоматически распознает бэкслеш-эскейп-последовательности. То есть, "\n" во входном файле превращается в один символ перевода строки. На контестах такое поведение очень мешает, а мы, когда на это наткнулись на Всесибе-2009, не смогли его переконфигурировать и пришлось дополнительно преобразовывать входной поток.
Резюме по StreamTokenizer: его имеет смысл использовать в задачах на парсинг. В таких задачах, решения получаются существенно короче.
BufferedReader+StringTokenizer
Довольно простая по смыслу комбинация: из файла читаем по строкам, далее строку бьем на токены. В итоге получается метод String next(), который читает "следующий токен", поверх которого делаются int nextInt(), long nextLong(), double nextDouble() через соответственно Integer.parseInt, Long.parseLong, Double.parseDouble. Все это работает почти также быстро, как StreamTokenizer, за вычетом того, что строк создается побольше. Тем не менее, файлы порядка десяти мегабайт читаются на ура.
Из перечисленных способов, для этого нужно больше всего кода. Но этот код "без мозгов", поэтому его можно написать один раз в шаблоне - все равно минуты 4 это занимает от силы. Зато удобно пользоваться.
Подводные камни: когда файл кончается, BufferedReader возвращает null из readLine. Если мы хотим с помощью этого способа читать задачи с "input is terminated by end-of-file", то нужно предусмотреть корректный путь этого null в написанных нами методах.
О выводе:
PrintWriter
Это единственный достаточно богатый класс для вывода (есть еще PrintStream, делает то же самое, но работает с byte, а не с char, поэтому, на уровне пользователя, проблемы с кодировками - это вообще отличие всех Stream от всех Reader/Writer). Зато у него есть сразу все - println, print(все примитивы) и так далее. Есть даже printf с семантикой, похожей на то же самое из C, только вот в Java varargs реализованы через массивы, поэтому этот метод - медленный. Зато он полезен, когда хотим вывести, например, вещественное число:
out.printf("%0.4f%n", answer);
Если планируете пользоваться printf (или его идейным аналогом String.format), то внимательно изучите документацию - форматная строка достаточно отличается от сишной, например, здесь нет "префиксов длины" типа "%lld".
В Java есть иерархия наследования коллекций, в отличие от C++. Однако, базовый интерфейс Collection<T> в практике контестов практически никогда не используется. Более специфичные интерфейсы - списки List<T>, множества Set<T>, очереди Queue<T> и Deque<T>, о которых сейчас и поговорим.
ArrayList<T> - примерно эквивалентен std::vector<T>. Операции более-менее те же, асимптотика та же. Разумеется, медленнее массива (за счет лишней проверки границ), особенно если там хранить всякие Integer'ы (тут уже boxing-unboxing тормозит, про него отдельно).
Vector<T> - еще один "аналог", более древний и менее желательный к использованию. Причина в том, что все его методы synchronized, что делает его более-менее безопасным в многопоточном использовании, но на контестах оно нафиг не нужно, да еще и тормозит, а за секунду-две JVM может и не успеть сообразить, что можно убрать synchronized.
Stack<T> - стек, который сделан на Vector<T>. Не рекомендую применять по той же причине, что и Vector<T>.
LinkedList<T> - двусвязный список. Реализует интерфейсы List<T>, Queue<T>, Deque<T>. Реализация более чем каноническая, с дополнительным объектом для каждого хранимого элемента, поэтому тормозит отчаянно.
ArrayDeque<T> - дек на массивах. Добавление и удаление с любого конца - O(1). Работает быстро. Жаль, что на топкодере вроде бы его еще нет (этот класс появился в Java 1.6)
PriorityQueue<T> - название говорит само за себя, в корне наименьший элемент. Правда, это все же коллекция, поэтому манипуляции непосредственно с элементами тут недоступны. В отличие от хипа "из книжек", тут не скажешь произвольному элементу siftUp, потому что поиск или удаление произвольного элемента тут работают за O(N), и с интерфейсом коллекции тут ничего лучше не сделать. Насколько понимаю, та же проблема и в STL. Один из прикольных методов с этим побороться - когда надо "поднимать" элемент, старый не удаляем, а просто добавляем новый, а старый каким-либо образом инвалидируем. Дейкста на такой очереди с этим трюком работает значительно быстрее, чем на TreeSet<T>.
HashSet<T> - тоже по названию все понятно. Достаточно быстр, в частности, быстрее, чем TreeSet<T>.
TreeSet<T> - аналог std::set<T>, множество на красно-черных деревьях. Поддерживает методы first(), last(), removeFirst(), removeLast(), а также тучу subSet'ов, которые являются view на основное множество (т.е. никакого копирования не происходит, все изменения на основном множестве отражаются на всех вьюхах, черех вьюхи тоже можно добавлять и удалять элементы). Единственный их недостаток - размер subSet'ов вычисляется за O(N), поэтому большой халявы от них в задачах на структуры данных ждать не приходится.
Аналоги std::map<K,V> в Java не являются коллекциями - а какие элементы такая коллекция должна содержать? - поэтому для этого заведен отдельный интерфейс Map<K, V>. Две его основных (для контестов) реализации - это HashMap<K, V> и TreeMap<K, V>. Поведение их аналогично соответствующим множествам (на самом деле, *Set именно через *Map и реализованы). Чтобы пройтись по ключам, нужно взять keySet(), по значениям можно пройти с помощью values(), можно также пройтись по парам ключ-значение (которые называются Map.Entry<K, V>) с помощью entrySet().
Итераторы.
Есть базовый интерфейс Iterator<T>, который имеет методы "T next()", "boolean hasNext()" и "void remove()". Такие итераторы возвращаются методами iterator() всех коллекций. Списки дополнительно имеют метод listIterator(), которые возвращают ListIterator<T> для хождения по спискам. Этот итератор довольно сложен, нужно внимательно изучить доки перед тем, как его использовать. Что-то похожее умеет TreeSet<T> с версии 1.6 библиотеки, для чего придуман интерфейс NavigableSet<T>, но с ним я еще не успел поработать.
ConcurrentModificationException. Все "простые", немногопоточные коллекции обладают следующим свойством. Если по ним кто-то итерируется, неважно как, даже с помощью enhanced for loop, а коллекция была изменена (добавлен, удален, заменен какой-либо элемент), то итератор при попытке следующей операции падает именно с этим исключением. Как правило, на контестах такие ситуации хотя и бывают, но быстро исправляются, например, проходом по списку с помощью индексов, а не с помощью итераторов.
В качестве заключения: итерирование по списку с помощью итератора (+enhanced for loop!) всегда создает новый объект (итератор), в то время как итерирование по индексам - нет. Поэтому в совсем уж критичных по времени решениях не пользуйтесь первым из способов в боттлнеках.