Сегодня на контесте(Крок мвту финал) решал задачу Ц. Написал решение, прошло претесты, я был в нем уверен.
После финального тестирования оно упало на 36 тесте с вердиктом wa. Долго не мог понять в чем косяк, потом появился разбор, оказалось, что я так и решал. Никак не мог понять в чем ошибка. В итоге решил в поиске найти, кто тоже упал на этом же тесте. Нашел вот такую попытку — http://mirror.codeforces.com/contest/250/submission/2660008 . Сверил со своим, все так же. Посмотрел историю посылок, увидел, что задача в итоге сдалась. http://mirror.codeforces.com/contest/250/submission/2663690 . Проблема крылась в сравнении Integer (надо было equals вместо =).
Решаю уже где-то год на яве. Никогда с этим не сталкивался, пару раз на хабре видел, что бывает такая проблема, но благополучно забил на это. И вот сегодня столкнулся с такой проблемой все-таки.
Вроде бы нашел, почему такое происходит(https://www.owasp.org/index.php/Java_gotchas#Immutable_Objects_.2F_Wrapper_Class_Caching). Но остался вопрос, насколько лишний вызов метода может замедлять программу? И вообще, почему я раньше с этим не сталкивался, всегда писав == вместо equals, вроде бы эта проблема должна часто проявляться.
Спасибо.
p.s. весьма обидно, что так получилось, решил сегодня 3 задачи(одна по глупости слетела из торопливости и еще вот эта, а до финальных тестов был в топ50=( )
Проблема тут в том, что метод ArrayList.get() возвращает ссылку на объект типа Integer, так что сравнение через оператор == сравнивает именно ссылки, а не сами объекты. Почему Вы не сталкивались с этим раньше? А потому, что при сравнении вида
al.get(i) == 0
в левой части происходит распаковка типа Integer в int.Насчет замедления программы: в данном случае оно явно пренебрежимо мало в сравнении с замедлением от упаковки-распаковки.
Да, почему Вы не смогли отловить этот баг на простых тестах? А потому, что для целых чисел меньше какой-то небольшой константы Java заранее создает объекты и при попытке упаковать маленькое число просто возвращает уже существующий объект.
ясно, спасибо
верно. я видел в коде какой-то реализации дипазон -128..127 т.е. char сиплюсплюсный.
В C++ разрешается как наличие, так и отсутствие знака у
char
, это implementation-defined.И вообще у char недетерминированный размер, да-да
Т.е. java-нский byte — говоря проще ;-)