Ява и МЛ. - Codeforces

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

В этом году моя команда и, как следствие я, решили перейти с плюсов на Яву.
Как следствие - я стал получать МЛ в весьма неожиданных(для меня) местах.
Например МЛ - вот по этому решению задачи D сегодня.
http://pastebin.com/EDvva5p4
Вопрос к людям с богатым опытом использования Явы на контестах, что именно не так я делаю?
На данный момент - после вердикта МЛ - я обычно стремлюсь избавиться от структур/локальных переменных в циклах, упорядачиваю индексы в массивах от меньшего к большему, но после подобных преобразований читать код становится действительно сложно.
Нет ли более простых тактик избежания МЛ?

P.S. Спасиюо udalov - на дорешивании АС по этой задаче я-таки получил. Однако память все равно кушается совершенно(для меня) не предсказуемо. Исправленное решение заняло 259000 килобайт памяти, то есть вписалось тютелька-в-тютельку.
Хотелось бы услышать больше конструктивной критики/советов по поводу укращения аппетитов Явы.

int answerX = 0;
int answerY = 0;

/* тонна кода */

for (...) {
    /* еще много чего */
    answerX += something1 * somethingElse2;
    answerX += something2 * somethingElse1;
}

out.printf("(%d; %d)%n", answerX, answerY);

Комментарии (38)

Показать архивные | Написать комментарий?

udalov

14 лет назад, # |

+13

Да, не нужно писать "new ArrayList<Integer>()", т.к. по умолчанию в нём будет 10 элементов (null). Нужно писать "new ArrayList<Integer>(0)"

→ Ответить

adavydow

14 лет назад, # ^ |

Спасибо за совет. Полное решение 259000 КБ памяти=). Но все равно не айс=(

OSt

ИМХО весьма "сомнительный (в общем случае) полезный совет".

ArrayList внутри себя вроде как содержит обычный массив для хранения элементов.

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

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

Я до сих пор не понимаю, как оценивать израсходованную память в Яве.

На мой взгляд - массив ребер (10^6 * 10 * 4 ~ 40mB), TreeSet пар - (10^6)* (8 + c) - где c - константа TreeSet'a - вряд ли она гигантская, ну, скажем 50 байт на одну запись.
Итого - примерно 100 mB.
Так я думал до System test'a =)
Понятно, что всегда можно запустить макс тест - посмотреть память, получить более точные оценки. Уже который раз обещаю себе впредь быть умнее=)
Однако куда Ява кушает память - для меня по прежнему загадка.

OSt	14 лет назад, # ^ \| 0 А рекурсия, думаете, на халяву будет? ) → Ответить

← Rev. 2 →

Глубина рекурсии на макстесте (1000000 провинций, 0 дорог - именно там я упал) - нулевая. Да, мне кажется естественным, чтобы она была "нахаляву".

-15

Понятно в чем проблема .

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

← Rev. 3 →

Это я понимаю прекрасно, вектор в плюсах реализован так же, и вообще это единственный адекватный способ реализовать массив с возможностью добавления в конец. Вся фишка в том, что в макс тесте ребер нет вообще, т.е. все ArrayList - вообще пусты (имеют размер 10, как правильно заметил мне udalov).

(Double Post)

Разумеется, как и любой полезный совет, в общем случае он не верен. С другой стороны, ваш последний аргумент тоже не до конца верен: авторы всё-таки вряд ли думали об олимпиадных программистах, когда/если искали эту самую "золотую середину"...

SkorKNURE

А какие были предпосылки для такого решения - перейти на Java?

У меня несколько раз возникала такая идея, главным образом из-за возможности отловки многих багов на этапе компилляции (типизация, строгий синтаксис), проверки попадания в память (dp[-1]) и немаловажной причины под названием "как-то надоело на плюсах" :) Но писать контесты на Java как праймари-языке немножко "стремает" из-за TL-ей, ML-ей и того факта, что на С++ зачастую можно "пропихнуть" менее интеллектуальный код за счет быстродействия... Ну и STL производит лучшее впечатление, чем встроенные в Java коллекции и алгоритмы.

У кого-нибудь есть какие-то мысли по этому поводу?)

MaxBuzz

Я как джавер могу сказать, что встроенные в Java коллекции и алгоритмы сделаны весьма хорошо. Просто у них с STL несколько разные парадигмы.

Для сравнения, в C#, в то время, когда я им был вынужден заниматься, коллекции были весьма "отвратные" (например, ассоциирование с уже существующим ключом в Dictionary бросало эксепшен, да и эквивалента Set не было), а про косяки в алгоритмах, я думаю, все уже наслышаны (тогда там в качестве сортировки был легко убиваемый quicksort).

Java-специфичные TL и ML появляются на довольно редких извращенных задачах. Например, удалить дубликаты в списке из десятка миллионов треугольников за 2 секунды получается непросто, от объекта "треугольник" приходится отказываться, как и от алгоритмов и структур стандартной библиотеки.

Ну и есть плюсы в виде умных IDE, умеющих находить множество таких ошибок, которые в C++ научатся автоматически находить еще очень нескоро (если вообще научатся).

На мой взгляд, и я в этом не одинок, как главный язык для контеста Java очень хороша.

Мне достаточно часто приходилось отказываться от структур. Например порой приходилось отказываться от структуры Edge при хранении графа и заменять ее на массив интов. После того, как наступил пару раз на эти грабли строчки вида edge[TO] = b; edge[INV] = edges[b].size(); стали для меня стандартом.
И хотя из-за использования более продвинутый среды результаты контестов скорее улучшились, подобные места меня печалят и заставляют задуматься, что же я делаю не так.

Urbanowicz

А можно перечислить множество «таких» ошибок, которые в C++ научатся находить нескоро?

Выход за пределы массива, присваивания long long в int не подумав, неинициализированная переменная, забытый return в одной из веток if в функции... Кроме того, сам факт того, что ошибки компиляции отображаются мгновенно, во время набора кода, ускоряет время набора + компиляции.

По-моему, Буздалов говорил о чем-то другом. Все перечисленные ошибки (кроме выхода за пределы массива), насколько я помню, MSVC ловит. Могу ошибаться, давно не работал в студии. А для компиляции на лету и даже во время дебага есть LLVM Clang. Правда, не знаю, какие IDE его поддерживают, кроме Xcode.

Может быть и о чем-то другом, я говорю за себя.
Плюсы - вполне приятный язык и на нем можно вполне комфортно разрабатывать программы. Однако на онсайтах большей частью плагинов и сред пользоваться нельзя, что несколько затрудняет эффективное программирование на котнесте. Так, например, к VC есть очень приятный плагин Visual Assist, который нельзя использовать на контестах. Тоже самое касается LLVM Clang - не встречал ни на одном из онсайтов. Вообще на онсайтах редко встречается что-то кроме Visual Studio. Эта среда - вполне удобна для разработки под .net, но как среда разработки под плюсы, без плагинов - на мой взгляд слабовата.

> LLVM Clang - не встречал ни на одном из онсайтов.

Этот компилятор научился нормально работать с C++ только прошлым летом, так что неудивительно.

← Rev. 4 →

+17

Было в практике такое: геометрический код, грубо говоря, такого вида:

ну или что-то похожее.

Eclipse нашел и подсветил ошибку, что-то вроде: переменная answerY может быть заинлайнена. Подсветку я заметил перед сабмитом, место показалось "странным". Я нашел и исправил ошибку, заслал, AC. До конца контеста оставались считанные секунды.

Если бы мне было не влом, я бы порылся в петрозаводских архивах и нашел бы точно исходник, а также точно указал бы место ошибки и "вердикт" Eclipse.

В общем и целом, control flow в Java проверяется тщательнее, чем в C++, даже стандартным компилятором (хотя компиляторы C++ к этому уровню подбираются). А уж IDE, анализирующие все дерево разбора целиком, проверяют все еще более доскональным образом.

Кроме того, в Java IDEA (ну и в Resharper заодно) есть intentions, они подсказывают, как можно улучшить код. Иногда такие подсказки также выявляют баги кодирования.

P.S.: Парсер - лох :-(

Scalar

Студия выход за пределы массива частично ловит: в режиме DEBUG при выходе из его области видимости сообщает, что стек возле данного массива поврежден.

Причины более-менее те же. Ловля багов(даже не на этапе компиляции, а на этапе написания кода - эклипс, с этой точки зрения - чудо), проверки попадания в память, удобная среда(eclipse). На очных турах из нормальных IDE для плюсов регулярно стоит только Visual Studio, которая на мой взгляд не очень удобна.
Кроме того Ява - основной язык одново одного из моих сокомандников.

В эклипсе, насколько я знаю, отдельный этап компилляции редко используют. Среда "подкомпилливает" код по ходу написания, это я и имел в виду. Что касается алгоритмов - какая бы ни была парадигма, отсутствие реализованных вещей вроде next_permutation(), nth_element() и иже с ними не очень нравится. Еще напрягает излишняя "словестность" джавы - код не выглядит компактным. Ну ясно, повода для холиваров тут нет, и разводить их не стоит. Из оставшихся актуальных вопросов - кто-нибудь использует IDEA для контестов? Стоит ли? Где-то слышал, что там лучше дебаггер, хотя она платная и на онсайтах ее вряд ли повстречаешь...

Идея уже давно как есть бесплатная - Community Edition.
А вот на онсайтах ее почему то нет=(

pascal

-13

А по мне Python лучше всех! Python = Java.add(C++)

riadwaw

А еще он прям такой скоростной..

Ну, на питоне я бы подобную задачу решать не стал впринципе, т.к. по мне - очевидный TL.

-dp-	14 лет назад, # ^ \| ← Rev. 4 → +16 А вот фиг :Р 4560 мс → Ответить

madkite

> Хотелось бы услышать больше конструктивной критики/советов по поводу укращения аппетитов Явы.

В данном случае проблема больше не в яве, а в том как этот сайт меряет используемую память (на topcoder-е вон ограничение 64 метра, но проблем с ML в ява с десять раз меньше). Судя по всему на этом сайте память меряется тем же методом как и для C/C++... а ява - это чуть другая технология, тут сборщик мусора есть. Т.е. тут нельзя просто взять и освободить память... память освободится когда в ней будет надобность - для практических задач это очень хорошо подходит, местами даже имеет выигрыш в производительности по сравнению с С/С++... но не здесь. Если вы напишете byte a[] = new byte[200*1024*1024]; a = null; a = new byte[200*1024*1024]; a = null;, то вроде бы прога не использует больше 200МБ памяти, но на этом сайте вы вероятно получите ML exceed, поскольку память освобождается исключительно сборщиком мусора, а он запускается по таймеру или при достижении лимита указанного виртуальной машине, но вот незадача - тут java запускается с параметром -Xmx256m, т.о. виртуальная машина контролирует, чтобы ваша прога не юзала больше 256МБ, но вот сайт то меряет объем памяти процесса средствами ОС как и для решений на С/С++, и как можно догадаться существуют накладные расходы и процесс в ОС занимает чуть больше. А контестант не может указать параметр запуска, чтобы задать более жесткое ограничение, например -Xmx200m - это бы часто решило проблему.

Иногда может помочь возможность запускать сборщик принудительно (System.gc()), но во-первых это очень тормознуто, т.к. запускается полный сборщик, во-вторых в большинстве случаев это не поможет - контестант, как я сказал, не может задавать параметры виртуальной машине, т.е. и тип/параметры сборки мусора. А на некоторых этапах и для некоторых участков памяти сборщик мусора запускается копирующий - а как вы понимаете из названия для его работы временно надо в два раза больше памяти. Я не знаю как тут оно точно меряется... но на ява лучше писать решения, которые не будут выделять более 200МБ, иначе вам не сюда.

Спасибо за развернутый ответ. Я понимаю эту особенность явы, потому и писал про избавления от локальных переменных в циклах. Как я понимаю, как участник - бороться с таким поведением явы я не могу, с этим можно только смириться. Однако многие участники пишут на яве, а МЛ отхватил, видимо я один. Поэтому хотелось бы узнать, почему конкретно мой код так неэффективен по памяти, и как можно его соптимизировать.
Просто это уже не первый случай когда я вот-так спотыкаюсь и хотелось бы как-нибудь прервать череду подобных неудач.

yaro

10^6 * 10 * 4 - заведомо неправильная оценка из-за неминуемого автобоксинга в стандартных коллекциях. И еще стоит умножить на два из-за мусора, получающегося при расширении.
Казалось бы, самое разумное - посмотреть оптимальные решения, которые разбираются с первой частью лучше (либо с графом без объектов, либо вообще без графа, который тут ни при чем), а со второй частью гораздо лучше (выводом ответа сразу, как только получены размеры компонент связности).

Если бы моей целью было получение АС по данной задаче, Ваш совет действительно был бы самым разумным. Как я уже писал - проблемма с МЛ -не в первый раз, и хотелось бы научиться бороться с МЛ впринципе.

Да, про автобоксинг я забыл. Спасибо.

А что касается оптимальности решения - то Ваше работает практически аналогично, за исключением того, что связные компоненты в графе Вы ищите с помощью СНМ, а не ДФС, что, на мой взгляд, странно. Хотя решение действительно более оптимально по памяти, т.к. СНМ написан не на ArrayList, а на нативных массивах, что позволяет избежать боксинга.

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

Что ж, повторюсь. С первым более-менее разобрались. Второй.
Мой совет заключался в том, что не надо задавать вопрос "как соптимизировать", когда поленились посмотреть уже написанные оптимальные. И кажется, я нигде не упоминал то, что сам написал. Посмотрите у Egor'a (disjoint sets + вывод ответа вместо ненужной эмуляции), посмотрите у niyaznigmatul (как искать компоненты в графе, если disjoint sets чем-то не угодили).

> потому и писал про избавления от локальных переменных в циклах.

Вот это спорный вопрос... Оба компилятора в яве (в байт-код и JIT) не такие уж и тупые, особенно последний. Локальная переменная в небольшом цикле может быть оптимизирована до регистровой (если она не объявлена volatile, разумеется). А вот оптимизировать глобальную переменную оно может уже не догадаться.

Egor	14 лет назад, # ^ \| 0 Вообще-то память меряется тупо выставлением ключа -Xmx256m при запуске. Так что сборщик мусора отлично прорабатывает, когда память заканчивается → Ответить

Egor	14 лет назад, # ^ \| +8 Беру свои слова назад. Был уверен, что никакой дополнительной проверки на память нету - ан нет Тогда это вправду очень большая проблема этой тестирующей системы → Ответить

Ripatti

Да... Перл на тему. Только что заметил.
Я в своем АС решении D на С++ ошибся ноликом в 3х местах.

В итоге я мог хранить граф на 10^7 вершин и 10^7 ребер.

Такое решение съело 246,5 Мб. Еще чуть чуть - и привет ML.

Посылка 375577 если кому интересно))

Vasya.V

Посмотрел Ваше решение - скорее всего много памяти кушается при чтении данных.

Каждый токен считывается сначала как String, а потом уже конвертится.

Можно попробовать использовать StreamTokenizer или взять шаблон у Egor'a

ivan.popelyshev

А не надо создавать сотню тысяч эррэйлистов. Используй односвязные списки:

Edge[] first;

class Edge
{
int from, to;
Edge next;
void add() {next = first[from];first[from]=this;}
public Edge(int x, int y) { from = x ; to = y; add();}
}

добавление - new Edge(x, y)
проход - for (Edge e = first[x]; e!= null; e = e.next)

UPD: можно добавить remove() который удаляет ребро если оно первое в списке. Удобно для эйлерова цикла.

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